Originally posted by: SystemAdmin
I am running into a performance issue that I believe is related to how I use the cp.element() method. In my problem, I have several parallel arrays of constants and my decision variables are simply indexes into these arrays. When I run problems with even nominally sized arrays, I am finding that the running time is much worse than I'd expected. In fact, I could write a few nested loops that would exhaustively search the space in a fraction of the time.
I suspect that the trouble is with how I am using the cp.element() method. Below is a sample program and its output that shows the problem I am having. In this program there are 8 integer decision variables that can each take on one of 6 values (0 to 5). It appears that the search space has size 8*6=48, however the output shows that 1743 branches were considered. When I run this problem using only one array (just A instead of A and B) the computation does not branch at all.
What am I doing wrong here? Is there a better way to use cp.element() or some other method to achieve the desired result? My problem has arrays that are significantly larger and I would still like to use ILOG CP to solve this.
Alex
import java.util.Random;
import ilog.concert.IloException;
import ilog.concert.IloIntExpr;
import ilog.concert.IloIntVar;
import ilog.cp.IloCP;
public
class ElementTest
{
public
static
void main(String[] _args)
throws IloException
{ Random random=
new Random(0);
int m=8;
int n=6;
int[][] A=
new
int[m][n]; System.out.println(
"A");
for (
int i=0;i<m;i++)
{
for (
int j=0;j<n;j++)
{ A[i][j]=random.nextInt(100); System.out.print(A[i][j]+
"\t");
} System.out.println();
}
int[][] B=
new
int[m][n]; System.out.println(
"B");
for (
int i=0;i<m;i++)
{
for (
int j=0;j<n;j++)
{ B[i][j]=random.nextInt(100); System.out.print(B[i][j]+
"\t");
} System.out.println();
} IloCP cp=
new IloCP(); IloIntVar[] indexes=
new IloIntVar[m]; IloIntExpr[] aValues=
new IloIntExpr[m]; IloIntExpr[] bValues=
new IloIntExpr[m]; IloIntExpr[] prod=
new IloIntExpr[m];
for (
int i=0;i<m;i++)
{ IloIntVar index=cp.intVar(0,n-1); indexes[i]=index; aValues[i]=cp.element(A[i],index); bValues[i]=cp.element(B[i],index); prod[i]=cp.prod(aValues[i],bValues[i]);
} IloIntExpr obj=cp.sum(cp.sum(prod),cp.sum(aValues)); cp.addMaximize(obj);
if (cp.solve())
{ System.out.println(
"obj="+cp.getValue(obj));
for (
int i=0;i<m;i++)
{ System.out.println(
"index["+i+
"]="+cp.getIntValue(indexes[i]));
}
}
}
};
A 60 48 29 47 15 53 91 61 19 54 77 77 73 62 95 44 84 75 41 20 43 88 24 47 52 60 3 82 92 23 45 45 37 87 2 62 25 53 38 35 60 75 55 30 98 91 74 36 B 12 62 19 77 16 46 7 16 8 37 43 47 87 88 5 58 8 17 51 18 58 18 38 72 57 51 26 80 97 62 35 20 67 73 17 69 5 52 89 43 1 41 23 80 68 14 16 23 ! ---------------------------------------------------------------------------- ! Maximization problem - 8 variables, 0 constraints ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation) ! . Log search space : 20.7 (before), 20.7 (after) ! . Memory usage : 315.4 Kb (before), 315.4 Kb (after) ! ---------------------------------------------------------------------------- ! Branches Non-fixed Branch decision Best * 8 0.00s _int4 = 0 16170 * 72 0.00s _int0 = 1 32177 * 121 0.00s _int3 != 3 39659 * 326 0.00s _int6 = 1 41600 * 358 0.00s _int1 = 4 42545 * 654 0.00s _int6 = 2 42853 1000 3 _int4 = 0 F 42853 ! Search terminated, replaying optimal solution ! ---------------------------------------------------------------------------- ! Solution status : Terminated normally, optimal found (tol. = 4) ! Number of branches : 1743 ! Number of fails : 882 ! Total memory usage : 355.3 Kb (347.5 Kb CP Optimizer + 7.9 Kb Concert) ! Time spent in solve : 0.02s (0.02s engine + 0.00s extraction) ! Search speed (br. / s) : 111552.0 ! ---------------------------------------------------------------------------- obj=42853.0 index[0]=3 index[1]=5 index[2]=0 index[3]=5 index[4]=4 index[5]=3 index[6]=2 index[7]=2
#CPOptimizer#DecisionOptimization