Originally posted by: isczg

Hi,

Given a set of dvar intervals whose length is not predefined and would be decided by other constraints, I'd like to introduce a new type of constraint: a interval shall always be included by other intervals whose length is greater than the former.

For example, in a specific solution for intervals A1,A2,.., An, we get lengthOf(A1) >= lengthOf(A2) >= .. >= lengthOf(An), then this solution must also guarantee that A1 including A2 (A1 starts before A2 and ends after A2), A2 including A3, .., An-1 including An.

I have two questions:

1. how to write the above "Nesting Intervals" constraint in OPL?

2. would this constraint significantly increase the complexity of the original model, and make the new model much harder to solve?

Regards,

Hi,

let me give you an example:

using CP;

int N=4;

dvar interval A[1..N] size 1..100;

subject to
{
forall(i in 2..N)
  {
      startBeforeStart(A[i-1],A[i],1);  
      endBeforeEnd(A[i],A[i-1],1);
  }

}

which will give the attached gantt.jpg if you click on A

Originally posted by: isczg

Hi Alex,

The length of interval A[1..N] is unknown and will be decided by other constraints in the model. When building the model, we can not assert that A[1] must include A[2]. But the constraint must guarantee that if the length of A[1] is greater than A[2] in the solution, then A[1] shall include A[2].

Regards, 

Hi,

then you could write something quite naive like

using CP;

int N=4;

dvar interval A[i in 1..N] size 10-i;

subject to
{
forall(i in 2..N)
  {
    (lengthOf(A[i-1])>= lengthOf(A[i]))  =>
    (
    ((startOf(A[i-1])<= startOf(A[i]))) &&
    ((endOf(A[i-1])>= endOf(A[i])))
    );
      
  }

or use overlapLength

using CP;

int N=4;

dvar interval A[i in 1..N] size 10-i;

subject to
{
forall(i in 2..N)
  {
    (lengthOf(A[i-1])>= lengthOf(A[i]))  =>
    (
    //((startOf(A[i-1])<= startOf(A[i]))) &&
    //((endOf(A[i-1])>= endOf(A[i])))
    overlapLength(A[i-1],A[i])==lengthOf(A[i])
    );
      
  }

regards

Originally posted by: isczg

Well, but this would bring O(n²) additional constraints. I am also skeptical about there could be better ways.

regards,

Hi,

why not linear ?

If I run

using CP;

int N=100;

dvar interval A[i in 1..N] size N-i;

subject to
{
forall(i in 2..N)
  {
    (lengthOf(A[i-1])>= lengthOf(A[i]))  =>
    (
    //((startOf(A[i-1])<= startOf(A[i]))) &&
    //((endOf(A[i-1])>= endOf(A[i])))
    overlapLength(A[i-1],A[i])==lengthOf(A[i])
    );
      
  }
}

execute
  {
  writeln(cp.info.NumberOfConstraints)  ;
  }

I get

100

regards

Originally posted by: isczg

The 100 constraints are not sufficient to ensure the nesting condition.

For example:

there are three interval A[1], A[2], A[3], if we write the following constraints

(lengthOf(A1) >= lengthOf(A2)) => (overlapLength(A(1),A(2))==lengthOf(A(2)))
(lengthOf(A1) <=lengthOf(A2)) => (overlapLength(A(1),A(2))==lengthOf(A(1)))
(lengthOf(A2) >= lengthOf(A3)) => (overlapLength(A(2),A(3))==lengthOf(A(3)))
(lengthOf(A2) <= lengthOf(A3)) => (overlapLength(A(2),A(3))==lengthOf(A(2))

and if a specific solution satisfies:

A2.length > A1.length > A3.length

then the above constraints can only guarantee that  "A2 includes A1" and  "A2 includes A3", but "A1 includes A3" was missed.

So  we should add the constraint for every pair of intervals, and it is O(n2).

regards,

Hi,

I see what you mean.

So if you want to stay linear you may try to use a sort:

using CP;

int N=100;

dvar interval A[i in 1..N] size N-i;

dvar int rank[1..N] in 1..N;
dvar int le[i in 1..N];
dvar int st[i in 1..N];
dvar int en[i in 1..N];

subject to
{

allDifferent(rank);
forall(i in 1..N)
{
le[i]==lengthOf(A[i]);
st[i]==startOf(A[i]);
en[i]==endOf(A[i]);
}

forall(i in 2..N) le[rank[i-1]]>= le[rank[i]];

forall(i in 2..N)
  {
    
    st[rank[i-1]]<= st[rank[i]];
    en[rank[i-1]]>= en[rank[i]];
    
    
      
  }
}

assert forall(i in 2..N)
    (lengthOf(A[rank[i-1]])>= lengthOf(A[rank[i]]))  ;

execute
  {
  writeln(cp.info.NumberOfConstraints)  ;
  }

regards

Originally posted by: isczg1

Hi,

Seems linear, using sort is not as effective as the O(n2)  method even for small problems with some perturbation for initial solution:

1.  sort method - opl engine will run on and on

2. O(n2) method - opl engine will find solution instantly

Hi,

then you could try with a search phase:

using CP;
int N = 8;
int sz[1..N] = [2,3,1,1,5,7,3,6];  
dvar interval A[i in 1..N] in i..100 size sz[i];  // perturbation to make initial solution infeasible

dvar int rank[1..N] in 1..N;
dvar int le[i in 1..N];
dvar int st[i in 1..N];
dvar int en[i in 1..N];

 execute {
  var f = cp.factory
  var phase1 = f.searchPhase(rank);
 
 cp.setSearchPhases(phase1);
}
 

subject to
{
  allDifferent(rank);
  forall(i in 1..N)
  {
    le[i]==lengthOf(A[i]);
    st[i]==startOf(A[i]);
    en[i]==endOf(A[i]);
  }
  forall(i in 2..N) le[rank[i-1]]>= le[rank[i]];
  forall(i in 2..N)
  {
    st[rank[i-1]]<= st[rank[i]];
    en[rank[i-1]]>= en[rank[i]];
  }
}

gives a solution in less than one second

regards

Originally posted by: isczg

Hi,

Search phase is awesome. Thank you!