# Set null the next set of N values

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.
• Not quite clear what you are asking. Do you mean that you want to avoid 101, 1001, 10001, and 100001? Commented Jan 28, 2023 at 22:01
• 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" Commented Jan 28, 2023 at 22:03

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.

• Thanks, in this case j starts from i, right? Commented Jan 28, 2023 at 22:55
• 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$).
– prubin
Commented Jan 28, 2023 at 23:20
• 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$? Commented Jan 28, 2023 at 23:34
• 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.
– prubin
Commented Jan 29, 2023 at 3:38

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.

• Thanks! Literally what I was trying to achieve Commented Jan 28, 2023 at 22:39
• @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? Commented Jan 29, 2023 at 12:56
• @A.Omidi It is the distributive property: $P \lor (Q \land R)$ is equivalent to $(P \lor Q) \land (P \lor R)$ Commented Jan 29, 2023 at 13:56
• @RobPratt, Thanks. 🙏 Commented Jan 29, 2023 at 16:25
• Your latter proposal enforces contiguous ones but allows $0\dots01\dots10\dots0$. Commented Sep 5, 2023 at 13:25

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.

• 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? Commented Jan 29, 2023 at 8:59
• 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$. Commented Jan 29, 2023 at 13:36
• 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? Commented Jan 30, 2023 at 3:01