CODEWITHSUNDEEP
minizinc
Juan
Juan

Reputation: 2103

MiniZinc MILP constraint to restrict a certain for at most 3 contiguous in an array

I have the next MiniZinc code

array [0..5] of var 0..1: a;
constraint sum(a) = 3;
output [show(a)]

And I need to add two constraints to ensure that at most I have 3 contiguous 1's. I thought that adding constraint sum(a) = 3; helps but how can I add a constraint to make sure I have 3-contiguous 1s for example 111000 or 011100?

Upvotes: 0

Views: 93

Answers (2)

Axel Kemper
Axel Kemper

Reputation: 11322

Another alternative is to constrain the distance between first and last 1:

int: n = 5;
set of int: N = 1..n;
array [N] of var 0..1: a;

var N: first = n + 1 - max(i in N)(i * a[n - i + 1]);
var N: last = max(i in N)(i * a[i]);
constraint sum(a) == 3;
constraint (last - first + 1) == 3;
output [show(a)]

Upvotes: 1

Magnus Åhlander
Magnus Åhlander

Reputation: 1446

Here is one way by constraining the sum of each block of 4 consecutive elements to 3:

array [0..5] of var 0..1: a;

int: MAX_CONTIGUOUS_ONES = 3;
constraint forall(start in 0..5-MAX_CONTIGUOUS_ONES)
  (sum([a[i] | i in start..start+MAX_CONTIGUOUS_ONES]) <= MAX_CONTIGUOUS_ONES);

output [show(a)]

Upvotes: 0

Related Questions