5
$\begingroup$

Let there be $N$ users with individual demands (of some items). Some users can have higher demands while the others can have lower demands. There are exactly $N$ service points. There is a one-to-one mapping between the users and the service points. At any point of time, only $P$ persons can be served, i.e., only $P$ service points are activated. There are a total of $M$ time slots where one time slot is equal to one hour. The $P$ service points that are activated simultaneosly must not be adjacent. A service point can deliver a given number of items in a time-slot. So, a given user can be served during some of the time-slots.

I want to maximise the fairness among the users.

Let $d_1,d_2,\cdots,d_N$ denote the demands of the users.

Let $s_1,s_2,\cdots,s_N$ denote the number of delivered items (over $M$ time slots)

The objective is

$\max \min \left\{\frac{s_1}{d_1},\frac{s_2}{d_2},\cdots,\frac{s_N}{d_N}\right\}$

Let $\bf A$ denote the adjacency matrix of the service points. If $A_{i,j}=1$, then service point $i$ is adjacent to service point $j$.

Let $q_1,q_2,\cdots,q_N$ denote the number of items that are delivered to the users in a time-slot duration.

So, if user $n$ is served in $t_n$ (sum of ones in the $n$th row vector in $\bf Z$) time slots, then $s_n=t_nq_n$

So, I suppose it is not an efficient formaulation.

Does anyone have a better/efficient formulation?

$\textbf {My Approach}$

Let us define a scheduling matrix $\bf Z$ of size $N\times M$. Note that $\bf Z$ is a binary matrix.

The constraint that at each time slot, only $P$ users can be served can be expressed as

$\sum_{n=1}^NZ(n,m)==P\hspace{1mm}\forall m,m=1,2,\cdots,M$

Now, the constraint that says that at any time-slot, the $P$ serving points must not be adjacent, can be expressed as

$Z(:,m)^T{\bf A} Z(:,m)==0\hspace{1mm} \forall m, m=1,2,\cdots,M$ Here, $Z(:,m)$ is the $m$th colomun vector of matrix $\bf Z$.

The delivered amount for user $n$ against its demand $d_n$ is given by

$s_n=\sum_{m=1}^MZ(n,m)q_n$.

So, my formulation of the scheduling problem becomes,

$\max \min \left\{\frac{s_1}{d_1},\frac{s_2}{d_2},\cdots,\frac{s_N}{d_N}\right\}$

subject to

$s_n=\sum_{m=1}^MZ(n,m)q_n$.

$\sum_{n=1}^NZ(n,m)==P\hspace{1mm}\forall m,m=1,2,\cdots,M$

$Z(:,m)^T{\bf A} Z(:,m)==0\hspace{1mm} \forall m, m=1,2,\cdots,M$

Note that the objective, the first and second constraints are convex/linear.

The last constraint is binary quadratic, which is very difficults to solve. Of course we can express it in a different way and linearize it as proposed in How can I linearize or convexify this binary quadratic optimization problem?. With the values I have for $N$ and $M$, the number of resulting linear constraints from the linearization is huge.

Note: $\bf A$ is not a psd. It has Eigen values both positive and negative.

$\endgroup$
  • $\begingroup$ Can you provide your formulation so far, and tell us specifically where you are getting stuck? Currently, your question reads as though you are asking us to formulate the whole problem from scratch, which I assume is not really what you are asking. See also How to ask for help with your model. $\endgroup$ – LarrySnyder610 Jul 9 at 23:57
  • $\begingroup$ @LarrySnyder610, I have provided my formulation. Please have a look. I am looking forward to an efficient formulation. $\endgroup$ – dipak narayanan Jul 10 at 7:21
  • 1
    $\begingroup$ You can reformulate the last constraints: What you want to express is that for all timeslots $m=1,\ldots,M$ two adjacent service points cannot be open. This can be achived by $\forall p_1, p_2\in A\,\forall m: Z(p_1,m) + Z(p_2,m) \leq 1$. Note we only need this for all pairs of adjacent service points, hence slightly abusing notation. $\endgroup$ – JakobS Jul 10 at 11:04
  • 1
    $\begingroup$ @dipaknarayanan Note that if you @-tag someone in a comment, they are not notified unless they have already commented on the same thread. So you can't "ping" someone to a new post just by @-tagging them -- setting aside the etiquette of calling out someone to ask them to answer your question, which in my opinion might also be a little iffy. $\endgroup$ – LarrySnyder610 Jul 10 at 13:36
5
$\begingroup$

I would rephrase the model a bit not using OP's matrix formulation. Instead of a matrix I will use binary variables $z_{st}$ indicating whether a service point $s$ is active in time slot $t$. Using the same two constraints and reformulating the $min$ in the objective function and the last constraint to be linear we arrive at the following model: $$ \begin{array}{ll} \text{maximize} & v \\ \text{subject to}& \forall m=1,\ldots,M: \sum_{n=1}^N z_{nm} \leq P \\ &\forall n=1,\ldots,N: s_n = \sum_{m=1}^M z_{nm}q_n \\ &\forall n=1,\ldots,N: v \leq \frac{1}{d_n}s_n\\ &\forall m=1,\ldots,M \,\forall (n_1, n_2)\in A \text{ where } A_{n_1 n_2}=1: z_{n_1m} + z_{n_2m} \leq 1\\ &\forall m=1,\ldots,M \,\forall n=1,\ldots,N: z_{nm} \in \{0,1\} \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.