Originally posted by: dbaena

Hi,
I have a doubt about CPLEX applied to MIP problems. I am solving a initial problem P1 with x binary variables and y continuos variables. After I solve that, I fix "x" variables and I have a new group of binary varibales (a group of y). I call this problem as P2. In theory, the problem P2 is more easy.

In order to take advantage of solving P1, I am using:

cplex.setParam(IloCplex::AdvInd,1);

and when I solve P1 I do:

cplex.addMIPStart(IloNumVarArray, IloNumArray);

but I see that P2 take more time than P1!! I don't understand it.

I show the output:

P1:

Solving MIP problem. Stage: 0
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 5.55 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

0 0 7.59518e+08 85 7.59518e+08 16

• 0+ 0 7.59518e+08 7.59518e+08 16 0.00%

0 0 cutoff 7.59518e+08 7.59518e+08 16 0.00%
Time: 9

P2:

Solving MIP problem. Stage: 1
1 of 2 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 7.5952e+08.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 4.22 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

• 0+ 0 7.59518e+08 17 ---

0 0 cutoff 7.59518e+08 7.59518e+08 17 0.00%
0 0 cutoff 7.59518e+08 7.59518e+08 17 0.00%
Elapsed time = 22.64 sec. (tree size = 0.00 MB, solutions = 0)
Time: 23

Thanks a lot!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

According to the log files, both problems are easy in terms of the combinatorics: they both solve at the root node.

So, the only difficulty seems to be associated to the linear program solves. Why do you think that the second problem should be easier? Is it (after fixing x) much smaller?

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Hi Tobias, thanks.
Yes, the number of fixed variables is big. For this reason, I think that the problem is muchsmaller.
On the other hand, I think that I don't need to solve linear program at the root node of P2 because it is the last node of P1...
But I don't know how can I avoid it...
Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Maybe you should just set the MIPDISPLAY parameter to 4. This will produce more output (in particular the root LP log) so that you can better see what is going on.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

OK, I'll see it. Thanks a lot.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just to be clear here, you really start out with problem P0 in which both x and y are binary. You relax integrality on y to get P1, solve that, fix the x values and reinstate integrality on y to get P2. Is that correct? If so, I would say that P2 should be easier than P0, but I see no reason to assume that it is easier than P1.

Suppose that problem P0 separates into an assignment model using x and a TSP using y. (I know your problem does not separate, but I'm using this as a trivial example.) Then P1 separates into an assignment problem and an LP, and no branching is required, but P2 is still a TSP and is in no way as easy as P1 was.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Hi Paul,
In fact, P1 and P2 have the same number of binary variables (more or less). Only, they have less relaxed vars (P2) because there are a number of fixed variables (the solution of P1).

thanks a lot!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

But as far as I understand, P1 and P2 have different binary variables (even though their number might be roughly the same). Paul's comment was that the underlying structure of the two problems could be different and thus the difficulty for solving them as a MIP could be much different.

There are models with millions of binary variables that just solve very easily at the root node. On the other hand, there are models with 50 binary variables that cannot be solved in ages. So, the number of binary variables in the model is typically not a good indicator for the difficulty of the model. Only if you keep the structure of the model fixed and then increase its size, you would typically see an increase in the solving time.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Thanks a lot Tobias.
#CPLEXOptimizers
#DecisionOptimization