3
$\begingroup$

I'm dealing with a problem I already modelled by using linear programming. The already existing constraints set at 1 groups of contiguous variables (for ex: (0001111100000000000) ). I'm now asked to add a constraint that:

  • set at 0 at least the next set of N variables In the mentioned example, said N = 5 I won't be able to get (00011111000011110000), but I could get (00011111000000011110). What causes me a problem, is that I have groups of 1s and not single placed 1s. If I had just single placed 1s, the constraint would be something similar: $$\sum_{i=0}^{N}x_i=0$$but I can't find a way to formulate the constraint in order to cover all the 1s of the set.
$\endgroup$
2
  • $\begingroup$ Not quite clear what you are asking. Do you mean that you want to avoid 101, 1001, 10001, and 100001? $\endgroup$
    – RobPratt
    Commented Jan 28, 2023 at 22:01
  • $\begingroup$ Yes, but I can't modelize them: the idea is that "I want that the next N variables after the last 1 of each group of variables set at 1 should be 0" $\endgroup$
    – devOn
    Commented Jan 28, 2023 at 22:03

3 Answers 3

5
$\begingroup$

If I understand this correctly, what you want to enforce is the following: if $x_i=1$ and $x_{i+1}=0$ (so that variable $i$ is the last in a string of one or more consecutive 1s) then $x_{i+2}=\dots=x_{i+N}=0$ (position $i+1$ is the start of $N$ consecutive 0s). You can do that with the following constraints for each index $j$: $$x_j \le 1-x_{j-2} + x_{j-1}$$$$x_j \le 1-x_{j-3}+x_{j-2}$$$$\vdots$$$$x_j \le 1-x_{j-N}+x_{j-N+1}.$$Omit any constraints for which the variable being subtracted on the right does not exit. For instance, if $N=5$ and $j=4$ you would have the first two constraints, but the third constraint would subtract $x_0,$ which doesn't exist, so you stop after two constraints.

$\endgroup$
4
  • $\begingroup$ Thanks, in this case j starts from i, right? $\endgroup$
    – devOn
    Commented Jan 28, 2023 at 22:55
  • $\begingroup$ No, $j$ starts from 3. So you get one constraint for $j=3$ (if $x_1=1$ and $x_2=0$ then $x_3$ has to be 0), two constraints for $x_4$ (has to be 0 if either $x_1=1$ and $x_2=0$ or $x_2=1$ and $x_3=0$), three constraints for $x_5$, and four for $x_6$ onward (assuming $N=5$). $\endgroup$
    – prubin
    Commented Jan 28, 2023 at 23:20
  • $\begingroup$ Sorry, I didn’t get the mechanism for the initial value of $j$: assuming to have $A=50$ variables in total, $N=5$ variables that should be 0 after the last 1, $j$ will start from $N-1$? $\endgroup$
    – devOn
    Commented Jan 28, 2023 at 23:34
  • $\begingroup$ Assuming you want five consecutive zeros any time a group of 1s of any length (including just a single 1) ends, then the first time you would need to enforce this would be if $x_1=1$ and $x_2=0$, after which you would need to force $x_3$ to be 0. So $j$ would start at 3. $\endgroup$
    – prubin
    Commented Jan 29, 2023 at 3:38
3
$\begingroup$

To avoid $101$, the logical proposition is $$\lnot (x_i \land \lnot x_{i+1} \land x_{i+2}).$$ Rewriting in conjunctive normal form yields $$\lnot x_i \lor x_{i+1} \lor \lnot x_{i+2},$$ which you can enforce via linear constraint $$(1-x_i) + x_{i+1} +(1-x_{i+2}) \ge 1,$$ equivalently, $$x_i - x_{i+1} + x_{i+2} \le 1.$$ More generally, to avoid $10\dots01$ (with $n$ zeroes), impose $$x_i - \sum_{j=i+1}^{i+n} x_j + x_{i+n+1} \le 1.$$


Rather than impose separate constraints to avoid 101, 1001, 10001, and 100001, @prubin suggested instead enforcing $$(x_i \land \lnot x_{i+1}) \implies \bigwedge_{j=i+2}^{i+n} \lnot x_j.$$ Now rewrite in conjunctive normal form to somewhat automatically derive the desired linear constraints: $$ \lnot (x_i \land \lnot x_{i+1}) \lor \bigwedge_{j=i+2}^{i+n} \lnot x_j \\ (\lnot x_i \lor x_{i+1}) \lor \bigwedge_{j=i+2}^{i+n} \lnot x_j \\ \bigwedge_{j=i+2}^{i+n} (\lnot x_i \lor x_{i+1} \lor \lnot x_j) \\ \bigwedge_{j=i+2}^{i+n} ((1 - x_i) + x_{i+1} + (1 - x_j) \ge 1) \\ \bigwedge_{j=i+2}^{i+n} (x_i - x_{i+1} + x_j \le 1), $$ which is equivalent to what @prubin recommended.

$\endgroup$
12
  • $\begingroup$ Thanks! Literally what I was trying to achieve $\endgroup$
    – devOn
    Commented Jan 28, 2023 at 22:39
  • $\begingroup$ @RobPratt, Would you please, is there any rule to move indexed logical and, $\bigwedge_{j=i+2}^{i+n}$, from the right to the left side of the third expression? $\endgroup$
    – A.Omidi
    Commented Jan 29, 2023 at 12:56
  • 1
    $\begingroup$ @A.Omidi It is the distributive property: $P \lor (Q \land R)$ is equivalent to $(P \lor Q) \land (P \lor R)$ $\endgroup$
    – RobPratt
    Commented Jan 29, 2023 at 13:56
  • $\begingroup$ @RobPratt, Thanks. 🙏 $\endgroup$
    – A.Omidi
    Commented Jan 29, 2023 at 16:25
  • 1
    $\begingroup$ Your latter proposal enforces contiguous ones but allows $0\dots01\dots10\dots0$. $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 13:25
2
$\begingroup$

As I understand you have a set of numbers 000011110 and you want to detect the index of the last 1 and then set next N numbers at 0. Obviously your set/list of cardinality 10 isn't like {0001110000} as in that case you already have 0s after the 1s. For the problem to make sense it would be like 0110001110 or 0011000111
If length of the set is known say m then
$\sum_{i=m+1}^N x_{i} \le 2 - (x_m+x_{m-1}) $
and to make it tighter
$\sum_{i=m+1}^N x_{i} \le x_m$

If the length of the set is not known then its a different problem. In that case need to find at what maximum index the last 1 occurs.

$\endgroup$
3
  • $\begingroup$ But if $m$ is said to be the set length (of the total variables), how can a variable have the index $i=m+1$? Or am I missing something? $\endgroup$
    – devOn
    Commented Jan 29, 2023 at 8:59
  • $\begingroup$ You may have defined set of indices of length $m+n$, of which first $m$ have values of 0 or 1 series, like $x_1,x_2,...x_m$. $\endgroup$ Commented Jan 29, 2023 at 13:36
  • $\begingroup$ No, if I only define $m$ as the total amount of variables and $N$ the next 0 variables to be set, how would your constraints be? $\endgroup$
    – devOn
    Commented Jan 30, 2023 at 3:01

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.