Originally posted by: SystemAdmin

[deborah said:]

Hi to all!!!

CP-Optimizer solve my model but it doesn't stop, goes into a loop!!

I've seen the "Engine Log" and it found the solution after 1 sec, but if I don't impose a time limit it doesn't stop. For exemple yesterday it run for 10 hours, so I stopped it.

Why?

Is my model the problem?

How can I modify the .ops file to avoid this problem?

Thanks in advance.

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[jfk said:]

Hello Deborah,
do you know that the solution CPO finds is the optimal? It is a possible scenario that solution is found in 1sec and proving the optimality takes time, though a 10hours run seems to be excessive.

as to the .ops you can set many things in the search control under constraint programming:
optimality tolerance
time limit
fail limit
etc.

well, if you could share your model it would be great...

cheers
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shaw said:]

Hello Deborah,

If you specify an optimization criterion, then CP Optimizer will not stop until
it proves that the problem has not solution, or the best solution that it has
found is optimal.  This can potentially take forever.  If you want it to stop
earlier, you can set a limit as Ferenc suggests.
  What behaviour were you looking for?


Paul
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi!!

Thank you for your replay.

This is my model:



/*********************************************
* OPL 6.1.1 Model
* Author: Deborah
* Creation Date: 08/feb/2009 at 18:49:41
*********************************************/

using CP;

execute {
//cp.param.FailLimit=200;
//cp.param.timeLimit=7200;
}

/*********************************************
* DATA
*********************************************/

int n = ...; //number of tasks
int K = ...; //number of crane

int l0[1..K]=...; //the starting position of QC k expressed by a ship bay number

int r[1..K]=...; //the earliest available time of QC k

int l[1..n]=...; //the location of task i expressed by a ship bay number

int taskType[1..n]=...; //type of task  (Deck=1 or Hold=2)

int p[1..n]=...; //the processing time of task i

int operationType[1..n]=...; //type of operation (loading=1 or unloading=2)

int safetyDistance=...; //safety distance between QCs (es. 1 ship bay)

int t=...; //the travel time between two consecutive bays

int a1=...; //the weight assigned to the makespan component of the objective function

int a2=...; //the weight assigned to the total completion time component of the
//objective function


/*********************************************
* PRE-PROCESSING
*********************************************/

int precedence[1..n][1..n];//the task pairs (i, j) describes the precedence
// relationships  (i.e.,i must precede j whenever (i, j)=1)
execute inizializePrecedence {
for( var i=1; i<=n; i++)<br /> for( var j=1; j<=n; j++)<br /> if(i!=j && l[i]==l[j]){
if(operationType[i]==2 && operationType[j]==1)precedence[i][j]=1;
else
if(taskType[i]==1 && operationType[i]==2 && taskType[j]==2
&& operationType[j]==2)
          precedence[i][j]=1;
          else
          if(taskType[i]==2 && operationType[i]==1 && taskType[j]==1
          && operationType[j]==1)
          precedence[i][j]=1;
          else
          precedence[i][j]=0;
      }
      else
      precedence[i][j]=0;
}

int noSimultaneously[1..n][1..n];//the tasks i and j cannot be performed
//simultaneously whenever (i, j)=1
execute inizializeSimultaneously {
  for( var i=1; i<=n; i++) <br />   for( var j=i+1; j<=n; j++){<br />     if(i!=j && Opl.abs(l[i]-l[j])<=safetyDistance){<br />      noSimultaneously[i][j]=1;
      noSimultaneously[j][i]=1;
     }
     else{
      noSimultaneously[i][j]=0;
      noSimultaneously[j][i]=0;
     }
  }
}

float tij[1..n][1..n]; //the travel time of a QC from location l[i] to location l[j]
execute inizializeTij {
  for( var i=1; i<=n; i++) <br />   for( var j=1; j<=n; j++){<br />     tij[i][j] = t*Opl.abs(l[i]-l[j]);
  }
}

float t0j[1..K][1..n]; //the travel time of each QC k from location l0[k] to
//location l[j]
execute inizializeT0j {
  for( var i=1; i<=K; i++) <br />   for( var j=1; j<=n; j++){<br />     t0j[i][j] = t*Opl.abs(l0[i]-l[j]);
  }
}
 
{int} pgreco[1..n]; //a set of tasks that must be completed before i starts
execute{
  for( var i=1; i<=n; i++) <br />    for( var j=1; j<=n; j++)<br />    if(precedence[j][i]==1)
    pgreco[i].add(j);
}

{int} sigma[1..n]; //a set of tasks that can only start after i is completed
execute{
  for( var i=1; i<=n; i++) <br />    for( var j=1; j<=n; j++)<br />    if(precedence[i][j]==1)
    sigma[i].add(j);
}
 
{int} upsilon[1..n][1..n]; /*a set of tasks belonging to the same ship bay that can
start only after i is completed and must be
completed before j starts./
{int} upsilon1[1..n][1..n]; // upsilon U j
execute{
  for( var i=1; i<=n; i++){ <br />    for( var j=1; j<=n; j++)<br />    if(i!=j){
    for(var l=1; l<=n; l++)<br />    if(l!=i && l!=j && pgreco[j].contains(l) && sigma[i].contains(l)){
    upsilon[i][j].add(l);
    upsilon1[i][j].add(l);
    }
    upsilon1[i][j].add(j);
    }
    }
}

int xi[1..n][1..n]; / a lower bound on the difference between the starting time of a
task j and the completion time of a task i, which uses the
precedence relationships inside a ship bay*/

execute{
for( var i=1; i<=n; i++) <br />    for( var j=1; j<=n; j++){<br />    xi[i][j]=0;
    if(Opl.card(upsilon[i][j]) !=0){
    for( var l = 0; l < Opl.card(upsilon&#91;i&#93;&#91;j&#93;) ; l++)<br />    xi[i][j]+=p[Opl.item(upsilon[i][j],l)];
    }
    }
  }

int xi0[1..n]; /*a straightforward lower bound on the starting time of a task j when j
has predecessors on the same ship bay*/
execute{
    for( var j=1; j<=n; j++){<br />    xi0[j]=0;
    if(Opl.card(pgreco[j])!=0){
    for( var l=0; l<Opl.card(pgreco&#91;j&#93;); l++)<br />    xi0[j]+=p[Opl.item(pgreco[j],l)];
    }
    }
  }
 
{int} omega[1..n];
  execute{
  for( var i=1; i<=n; i++) <br />    for( var u=1; u<=n; u++) <br />    if(l[u]!=l[i])
    omega[i].add(u);
  }

  int a[1..n]; //a Lower Bound for the Task Starting Time
  execute{
  for(var i=1; i<=n; i++){<br />  var dmin = r[1]+t0j[1][i];
  for(var k=2; k<=K; k++)<br />  if(r[k]+t0j[k][i] < dmin)<br />  dmin=r[k]+t0j[k][i]; 
  a[i]= Opl.maxl( (dmin+xi0[i]) , 0 );
  }
  }
  int U=0; //an Upper Bound for the Task Completion Time
  execute{
  var pro=0;
  for(var i=1; i<=n; i++)<br />  pro+=p[i];
  var lmin=Number.MAX_VALUE;
  var lmax=0;
  for(var j=1; j<=n; j++){<br />  if(l[j]<lmin)<br />  lmin=l[j];
  if(l[j]>lmax)
  lmax=l[j];
  }
for(var k=1; k<=K; k++){<br />  var sum=r[k];
  sum+=pro;
  //Calcolo di Tk
  var Tk=0;
  if(l0[k]<lmin)<br />  Tk=lmax-l0[k];
  else
  if(l0[k]>lmax)
  Tk=l0[k]-lmin;
  else
  if((l0[k]-lmin)<=(lmax-l0[k]))<br />  Tk=l0[k]+lmax-(2*lmin);
  else
  Tk=(2*lmax)-l0[k]-lmin;
  sum+=Tk;
  if(k==1)
  U=sum;
  else
  if(sum<U)<br />  U=sum;
  }
  }

/*********************************************
  * DECISION VARIABLE
  ********************************************/

dvar interval tasks[i in 1..n] size p[i];

dvar interval tasksOnMachines[k in 1..K][i in 1..n] optional;

dvar sequence machines[k in 1..K] in all(i in 1..n) tasksOnMachines[k][i] types all(i in 1..n) i;

dexpr int C[k in 1..K] = max(i in 1..n) endOf(tasksOnMachines[k][i]);//the completion time of QC k

dvar int W; //the makespan



/*********************************************
  * OBJECTIVE FUNCTION
 
   minimize
    a1*W + a2*sum(k in 1..K) (C[k]);
  *********************************************/
 
   minimize
   a1*W;
   

/*********************************************
  * CONSTRAINTS
  *********************************************/

constraints{

forall(k in 1..K, i in 1..n) (r[k]+t0j[k][i]) <= startOf(tasksOnMachines[k][i], ftoi(round(r[k]+t0j[k][i]))); //If interval variable tasksOnMachines[k ][i] is optional, you must make sure the constraint is satisfied when the interval is absent, that's why a value "r[k]" is specified in the startOf expression.<br />
forall(k in 1..K) C[k]<=W; //Define the makespan <br />
forall(i in 1..n) alternative(tasks[i], all(k in 1..K) tasksOnMachines[k][i]);

  forall(k in 1..K) noOverlap(machines[k],{ <i,j, ftoi(round(tij&#91;i,j&#93;))> | i in 1..n, j in 1..n});

forall(k in 1..K) C[k]>=r[k];



/*

             no_simultaneously_constraint:


no_crossing_constraint:

*/


}



This is the .dat file



n =10;
K = 2;

l0 = #[
       1: 1
       2: 6
     ]#;
     
r = #[
       1: 0
       2: 0 
     ]#;     

l = #[
       1: 2
       2: 10
       3: 3
       4: 2
       5: 6
       6: 2
       7: 7
       8: 7
       9: 3
       10: 5
     ]#;
     
taskType = #[
       1: 2
       2: 1
       3: 1 
       4: 2
       5: 1
       6: 1
       7: 1
       8: 2
       9: 2
       10: 2
     ]#;
     
p = #[
       1: 41
       2: 19
       3: 6 
       4: 12
       5: 37
       6: 34
       7: 48
       8: 10
       9: 56
       10: 3
     ]#;

operationType = #[
       1: 1
       2: 1
       3: 2 
       4: 2
       5: 2
       6: 1
       7: 2
       8: 1
       9: 2
       10: 2
     ]#;
     
safetyDistance = 1;

t = 1;

a1= 3;

a2= 0;



Regards

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Didier Vidal said:]

Deborah,

Just a side note on your model (it will not answer your question about proving optimality).
You can simplify simple data initialization with syntaxes as follow:

/*
int noSimultaneously[1..n][1..n];//the tasks i and j cannot be performed
//simultaneously whenever (i, j)=1
*/
int noSimultaneously[i in 1..n][j in 1..n] = (abs(l[i] - l[j]) <= safetyDistance);<br />/* 
execute inizializeSimultaneously {
  for( var i=1; i<=n; i++) <br />  for( var j=i+1; j<=n; j++){<br />    if(i!=j && Opl.abs(l[i]-l[j])<=safetyDistance){<br />    noSimultaneously[i][j]=1;
    noSimultaneously[j][i]=1;
    }
    else{
    noSimultaneously[i][j]=0;
    noSimultaneously[j][i]=0;
    }
  }
}
*/


Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi Didier,

thanks for your help, your replies are always useful.

Regards

Deborah
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Hi!

I set several parameter in .ops file but my model run and doesn't stop... it stop only if I set a time limit, is it normal???

Paul has said: "CP Optimizer will not stop until it proves that the problem has not solution, or the best solution that it has
found is optimal.  This can potentially take forever". So, if my model run for a long long time, this don't means that my model isn't correct... is it true????

Thanks

Deborah


#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Didier Vidal said:]

if my model run for a long long time, this don't means that my model isn't correct

That's right.

In [b]some[/b] cases, you can add surrogate constraints that help CP Optimizer prove optimality faster, as illustrated in the 'timetabling example' in the OPL documentation.



Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[deborah said:]

Thanks Didier!!!

Deborah
#DecisionOptimization
#OPLusingCPOptimizer