3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ User = machine? $\endgroup$
    – RobPratt
    Mar 25 at 13:43

2 Answers 2

Reset to default
9
$\begingroup$

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}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – KGM
    Mar 25 at 23:35
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Mar 26 at 0:42
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Mar 26 at 12:58
  • $\begingroup$ @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$ $\endgroup$
    – RobPratt
    Mar 26 at 13:39
  • $\begingroup$ @RobPratt, many thanks. 4th constraints is exactly what I was looking for. 👌 $\endgroup$
    – A.Omidi
    Mar 26 at 14:49
0
$\begingroup$

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$

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$ $\endgroup$
    – Sutanu Majumdar
    Mar 25 at 14:32
  • 1
    $\begingroup$ 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). $\endgroup$
    – RobPratt
    Mar 25 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Mar 26 at 14:47
  • $\begingroup$ Thanks @RobPratt, I'd update my answer $\endgroup$
    – Sutanu Majumdar
    Mar 26 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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