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
    Commented Mar 25, 2023 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
    Commented Mar 25, 2023 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
    Commented Mar 26, 2023 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
    Commented Mar 26, 2023 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
    Commented Mar 26, 2023 at 13:39
  • $\begingroup$ @RobPratt, many thanks. 4th constraints is exactly what I was looking for. 👌 $\endgroup$
    – A.Omidi
    Commented Mar 26, 2023 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
    Commented Mar 25, 2023 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
    Commented Mar 25, 2023 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
    Commented Mar 26, 2023 at 14:47
  • $\begingroup$ Thanks @RobPratt, I'd update my answer $\endgroup$
    – Sutanu Majumdar
    Commented Mar 26, 2023 at 17:09

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