Originally posted by: ununun

Hello, I have been struggling with this for a long time. any help is very much appreciated!

Let's say I have an array of length 5 and I define a binary variable y_i (i = 1.. 5) for each of them. I want to select a subset of this array with the continuity constraint that this subset must be adjacent. The size of this subset could be anywhere from 0 to 5. 

example:

good: 0 0 0 0 0

good: 0 0 1 0 0

good: 0 1 1 1 0

good: 1 0 0 0 0

bad: 0 1 0 1 0

bad: 1 0 0 1 0

Basically, I am thinking of a constraint that forces those 1s together.

any help/comment is highly appreciated!

Originally posted by: ununun

I think I have a solution for this:

define two extra variables x_min, x_max to get the minimal and maximal index of positive y.

then

x_max >= y_i * i . --> this captures the maximum index .  

x_min >= y_i * (4 - i) --> this (4 - x_min) captures the minimum index .   

x_max - (4 - x_min) + 1 <= \sum_i y_i

not sure whether there exists better approaches...

Hi,

In OPL I would write

int N=5;
dvar boolean x[1..N];
dvar int y[1..N];

subject to
{
forall(i in 2..N) y[i]==maxl(x[i]-x[i-1],0);
y[1]==x[1];
sum(i in 1..N) y[i]<=1;
}

execute
{
writeln(x);
}

and then I would use https://www.ibm.com/developerworks/community/forums/html/topic?id=d8d12e36-3150-4e1c-a956-d707d17f274c&ps=25

to check whether all solutions are good

int N=5;
dvar boolean x[1..N];
dvar int y[1..N];

subject to
{
forall(i in 2..N) y[i]==maxl(x[i]-x[i-1],0);
y[1]==x[1];
sum(i in 1..N) y[i]<=1;
}

execute
{
writeln(x);
}

 main {
cplex.solnpoolintensity=4;

    thisOplModel.generate();
    cplex.solve();
    if (cplex.populate()) {
      var nsolns = cplex.solnPoolNsolns;
      
      
      writeln("Number of solutions found = ",nsolns);
      writeln();
      for (var s=0; s<nsolns; s++) {
        thisOplModel.setPoolSolution(s);
        thisOplModel.postProcess();
      }
    }
}

 

gives

Number of solutions found = 16

 [0 0 0 0 0]
 [0 1 1 1 0]
 [0 1 1 1 1]
 [1 1 1 1 1]
 [0 0 1 1 0]
 [0 0 0 1 0]
 [0 0 1 1 1]
 [0 0 0 1 1]
 [0 0 0 0 1]
 [1 0 0 0 0]
 [1 1 0 0 0]
 [1 1 1 0 0]
 [0 0 1 0 0]
 [0 1 1 0 0]
 [0 1 0 0 0]
 [1 1 1 1 0]

regards