0
$\begingroup$

I need your help. I'm setting up an LP and I'm trying to find constraints to introduce the binary varibale $b_{ij}$. So it should take the value 0 if the sum of all $a_{ij}$ values to the period t are $\le n~ \forall i \in I \text{ and } j \in J$. $n$ being a not yet defined whole number. Otherwise, it is supposed to take the value 1. I think one models the whole thing with Big-M, but how exactly I do not know unfortunately.

$\endgroup$
4
  • $\begingroup$ Is $a_{ij}$ a decision variable? If so, what type? Is $n$ a decision variable or an input parameter? How do $i$ and $j$ relate to $t$? $\endgroup$
    – RobPratt
    Commented Jun 16, 2023 at 17:36
  • $\begingroup$ $a_{ij}$ is also either 0 or 1. It indicates whether seller $i$ sold all of his products in period $j$. If so, it is $=1$ $\endgroup$
    – Karl Seidl
    Commented Jun 16, 2023 at 17:38
  • $\begingroup$ So you want to model the following for all $i$ and $t$? $$b_{it} = 0 \iff \sum_{j \le t} a_{ij} \le n$$ $\endgroup$
    – RobPratt
    Commented Jun 16, 2023 at 17:40
  • $\begingroup$ Yep that's correct $\endgroup$
    – Karl Seidl
    Commented Jun 16, 2023 at 17:42

2 Answers 2

3
$\begingroup$

You want to enforce $$b_{it} = 0 \iff \sum_{j \le t} a_{ij} \le n.$$ You can enforce $$b_{it} = 0 \implies \sum_{j \le t} a_{ij} \le n$$ with big-M constraint $$\sum_{j \le t} a_{ij} - n \le M_1 b_{it},$$ where $M_1 = |\{j\in J: j \le t\}| - n$.

You can enforce $$\sum_{j \le t} a_{ij} \le n \implies b_{it} = 0,$$ equivalently its contrapositive $$b_{it} = 1 \implies \sum_{j \le t} a_{ij} \ge n + 1,$$ with big-M constraint $$n + 1 - \sum_{j \le t} a_{ij} \le M_2 (1 - b_{it}),$$ where $M_2 = n + 1$.

Another way to think of this is that you want $\sum_{j \le t} a_{ij}$ to be between $\color{red}{0}$ and $\color{red}{n}$ if $b_{it}=0$ and between $\color{blue}{n+1}$ and $\color{blue}{U_t}=|\{j\in J: j \le t\}|$ if $b_{it}=1$, yielding $$\color{red}{0}(1-b_{it}) + (\color{blue}{n+1})b_{it} \le \sum_{j \le t} a_{ij} \le \color{red}{n}(1-b_{it}) + \color{blue}{U_t} b_{it}$$

$\endgroup$
-1
$\begingroup$

$ \sum_{j\le t} a_{i,j} \le n + Mb_{i,j}$
$ n+\epsilon \le \sum_{j \le t} a_{i,j} + M(1-b_{i,j})$
with $ \epsilon$ as a small number, depending upon expected values of $n$

$\endgroup$
1
  • $\begingroup$ @RobPratt summing over $t$ $\endgroup$ Commented Jun 16, 2023 at 19:06

Your Answer

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

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