How to formulate this scheduling problem efficiently?

Question

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 in 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 simultaneously 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.

So, my formulation of the scheduling problem becomes

\begin{alignat}2\max \min&\quad \left\{\frac{s_1}{d_1},\frac{s_2}{d_2},\cdots,\frac{s_N}{d_N}\right\}\\\text{s.t.}&\quad s_n=\sum_{m=1}^MZ(n,m)q_n\\&\quad Z(:,m)^\top{\bf A} Z(:,m)=0\quad&\forall m\in\{1,2,\cdots,M\}\end{alignat}

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

The last constraint is binary quadratic, which is very difficult 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 eigenvalues which are both positive and negative.

Answer 1

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\limits_{n=1}^N z_{nm} \leq P \\ &\forall n=1,\ldots,N: s_n = \sum\limits_{m=1}^M z_{nm}q_n \\ &\forall n=1,\ldots,N: v \leq \dfrac{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} $$