# How to model this binary constraint?

I have an optimization problem that has a variable in the matrix form. The variable is a binary matrix. It has size $$M \times N = 10 \times 50$$ where $$M$$ is the number of machines and $$N$$ is the number of resources. The resources are indexed as $$\{1, 2, 3, \dots, 50 \}$$. Also, one resource can be shared by multiple machines and each row corresponds to a machine.

The condition is as follows:

• One user can have maximum of 20 resources.
• The resources assigned to any user must be contiguous.

For example, let us consider user $$5$$. It got $$10$$ resources. If the first resource is being assigned to the index $$10$$, the other $$9$$ resources must be indexed as $$11$$ to $$19$$ so that all the resources assigned to user 5 are contiguous. How can I model this constraint?

• User = machine? Mar 25 at 13:43

Let $$x_{i,j}$$ be your binary decision variable. The “at most 20 resources” constraint is $$\sum_j x_{i,j} \le 20$$ for each row $$i$$. One way to enforce contiguity is to introduce another binary decision variable $$y_{i,j}$$ to indicate whether $$x_{i,j}$$ is the “start” (the first $$1$$) in row $$i$$. You would then impose linear constraints \begin{align} \sum_j y_{i,j} &\le 1 &&\text{for all i} \tag1\label1 \\ x_{i,j} &\le y_{i,j} &&\text{for all i and j=1}\tag2\label2 \\ x_{i,j} - x_{i,j-1} &\le y_{i,j} &&\text{for all i and j>1}\tag3\label3 \end{align} Constraint \eqref{1} enforces at most $$1$$ start per row. Constraint \eqref{2} enforces $$x_{i,1} \implies y_{i,1}$$. Constraint \eqref{3} enforces $$(x_{i,j} \land \lnot x_{i,j-1}) \implies y_{i,j}$$.

If you want to avoid introducing new variables, you can instead replace \eqref{1} through \eqref{3} with $$\binom{N}{3}$$ constraints per row: \begin{align} x_{i,j} + x_{i,\ell} - 1 &\le x_{i,k} &&\text{for all i and 1\le j < k < \ell \le N}\tag4\label4 \end{align} Constraint \eqref{4} enforces $$(x_{i,j} \land x_{i,\ell}) \implies x_{i,k}$$.

• do all the users have same starting point? Would you please explain constraint 2. I think, the users can (more likely) have different starting points.
– KGM
Mar 25 at 23:35
• No, everything here depends on $i$, so each user behaves independently. Constraint \eqref{2} says that if user $i$ is assigned resource $1$, then the first resource assigned to user $i$ is resource $1$. Mar 26 at 0:42
• @RobPratt, I have tried another formulation based on what the questioner mentioned. The binary variable $x_{m,r}$ indicates whether resource $r$ is assigned to the machine $m$. The constraint $x_{m,r} \leq x_{m,r+1} \quad \forall m \in machines, (r+1) \in resources$ can enforce contiguity. Would you please say, is there any force to introduce a new binary variable to do that? Mar 26 at 12:58
• @A.Omidi What you propose is too restrictive. It forces either all zeros or that any contiguous block must appear at the end: $0\dots01\dots1$ Mar 26 at 13:39
• @RobPratt, many thanks. 4th constraints is exactly what I was looking for. 👌 Mar 26 at 14:49

Assuming user is your machine $$m$$ over resource $$r$$ and $$X$$ is your binary matrix
Try
$$N_mx_{m,r-1}-\sum_{k=1}^{r-2} x_{m,k} \le N_mx_{m,r}$$

If you number of resources assigned to a machine is itself a variable then you can try
$$\sum_{k=1}^{j-1}x_{ij} \le Mz1_{ij}$$ where $$M=min(20,j-1)$$
$$\sum_{k=j+1}^{N}x_{ij} \le Mz2_{ij}$$ where $$M=min(20,N-j)$$ $$z1_{ij}+z2_{ij} -1 \le x_{ij} \quad \forall j$$

• I do think it works because before it decides to make $r$ 0 or 1, if $r-1$ is 1 and it hasn't completed all N= assigned resources, it is forced to make $r=1$ Mar 25 at 14:32
• Suppose there are $7$ columns (instead of $50$) and you want at most one contiguous block of at most $3$ (instead of $20$). Your formulation returns only $4$ solutions per row when there should instead be $19$ ($1$ all zero, $7$ with one $1$, $6$ with two $1$s, and $5$ with three $1$s). Mar 25 at 15:09
• Your second formulation looks better, but you don't need $z1_{ij} \le$ or $z2_{ij} \le$ in the first two constraints. Also, your big-M constant $M$ means something different than in the question. You can use $20$, or even better use $\min(20,j-1)$ for the first constraint and $\min(20,N-j)$ for the second constraint. Mar 26 at 14:47
• Thanks @RobPratt, I'd update my answer Mar 26 at 17:09