I'm wondering if there exists a way in CP Optimizer 12.10 to stop the search if the upper bound (of a minimization problem) doesn't get better after "x" seconds. This would be especially helpful when trying to solve a difficult instance of an NP-Hard problem and the search is stuck in one incumbent solution.
I know there exist some parameters to control the search as cp.param.TimeLimit
(I'm using that) or cp.param.FailLimit
but that is not that I need for my problem.
Any help would be highly appreciated.
what you can do is use a main block (flow control) if you rely on the OPL API and in this main block you give a time limit of x seconds, then you get the bound and the current objective, you save them if you think you should go further or stop if you're ok with the solution.
Let me share a full example out of the lifegame example in the OPL product. And remember John Conway once again.
using CP;
int n=20;
int Half=n div 2;
range FirstHalf = 1..Half;
range LastHalf = n-Half+1..n;
range States = 0..1;
range Bord = 0..(n+1);
range Interior = 1..n;
range obj = 0..(n*n);
tuple neighbors {
int row;
int col;
}
{neighbors} Neighbor =
{<(-1),(-1)>,<(-1),0>,<(-1),1>,<0,(-1)>,<0,1>,<1,(-1)>,<1,0>,<1,1>};
dvar int Life[Bord][Bord] in States;
dvar int Obj in obj;
dvar int x[0..(n+2)*(n+2)-1];
maximize Obj;
subject to {
forall(i,j in Bord) Life[i][j]==x[i*(n+2)+j];
//ct1:
Obj == sum( i , j in Bord )
Life[i][j];
forall( i , j in Interior ) {
ct21:
2*Life[i][j] - sum( nb in Neighbor )
Life[i+nb.row][j+nb.col] <= 0;
ct22:
3*Life[i][j] + sum( nb in Neighbor )
Life[i+nb.row][j+nb.col] <= 6;
forall( ordered n1 , n2 , n3 in Neighbor ) {
ct23:
-Life[i][j]+Life[i+n1.row][j+n1.col]
+Life[i+n2.row][j+n2.col]
+Life[i+n3.row][j+n3.col]
-sum( nb in Neighbor : nb!=n1 && nb!=n2 && nb!=n3 )
Life[i+nb.row][j+nb.col] <= 2;
}
}
forall( j in Bord ) {
ct31:
Life[0][j] == 0;
ct32:
Life[j][0] == 0;
ct33:
Life[j][n+1] == 0;
ct34:
Life[n+1][j] == 0;
}
forall( i in Bord : i<n ) {
ct41:
Life[i][1]+Life[i+1][1]+Life[i+2][1] <= 2;
ct42:
Life[1][i]+Life[1][i+1]+Life[1][i+2] <= 2;
ct43:
Life[i][n]+Life[i+1][n]+Life[i+2][n] <= 2;
ct44:
Life[n][i]+Life[n][i+1]+Life[n][i+2] <= 2;
}
ct5:
sum( i in FirstHalf , j in Bord )
Life[i][j] >=
sum( i in LastHalf , j in Bord )
Life[i][j];
ct6:
sum( i in Bord , j in FirstHalf )
Life[i][j] >=
sum( i in Bord , j in LastHalf )
Life[i][j];
}
main
{
thisOplModel.generate();
cp.param.timelimit=10;
var obj=0;
var bound=0;
var oldobj=0;
var oldbound=0;
while (1==1)
{
cp.solve();
obj=cp.getObjValue();
bound=cp.getObjBound();
writeln("bound and obj =",bound," ",obj);
if (Opl.abs((oldobj-oldbound-obj+bound))<=0) break;
oldobj=obj;
oldbound=bound;
}
}
which gives
bound and obj =398 181
bound and obj =398 180
bound and obj =398 180
// Script execution finished with status 1.