Originally posted by: dbaena

Hello,
I try to explain what I want to do with an example.
I have 10 binary variables (x1,x2,x3,x4,x5,x6,x7,x8,x9,x10). And I descompose my problem (minimization) in two parts. In the first problem (P1) I relax x6 to x10 variables and I solve P1 with 5 binary variables. I obtain a solution (for me a LB). After, I fix the values of x1-x5 with the solution of P1 and I solve P2, where x1-x5 are fixed and x6-x10 are binary variables (not relaxed just).

What is my problem?

I want to solve P2 as a continuation of P1. Is to say, as a new branch of tree that I finished with P1...
I don't know If I explain well...

Thanks a lot!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Suppose that you set priorities, with x6-x10 having lower priority than x1-x5. You can use a callback (I think a cut callback would be best) to test whether x1-x5 were all integer and, if so, record the node objective value as your bound. Would that accomplish what you want?

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: EdKlotz

> Paul Rubin wrote:
> Suppose that you set priorities, with x6-x10 having lower priority than x1-x5. You can use a callback (I think a cut callback would be best) to test whether x1-x5 were all integer and, if so, record the node objective value as your bound. Would that accomplish what you want?
>
> 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)
I think Paul's approach should work. Also, once you discover in the cut callback that x1-x5 are all integers, you might want to actually add the
fixings for those variables as "cuts" and turn on CPLEX's node presolve feature
so that you get a performance speedup for the remaining part of the optimization.

Also, don't assume that this approach of using a single branch and bound tree is the fastest. You may get better results by actually fixing x1-x5 once they
attain integer values and restarting the optimization from scratch. The
additional presolve reductions with this two tree approach may actually work
faster. So, I suggest you compare both ways on representative problems, then
decide which one works best.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Hi,

thanks a Paul and EdKlotz. I don’t understand the option of Paul very well. I’ll see it with calm.
EdKlotz, the problem of your option is that restarting the optimization from scratch suppose a root relaxation (important computational time) while that it isn’t necessary because the better lower bound is when x6-x10 are relaxed (is to say, the problem P1).
Now, I am doing the following:
I built the P1 problem with x1-x5 as binary variables and x6-x10 relaxed. I solve this problem and I have a LB. After, I modify the P1 problem fixing the values of x1-x5 with xi.setLB() or xi.setUB() and un-relaxing the x6-x10 variables (object IloConversion…). I call to this problem as P2. When I solve P2, it does a relaxation…but I don’t want to do it because the LB is the value of P1. I think that I could avoid it. In fact, the P2 could continue from the last node solved in P1….

thanks a lot!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> dbaena wrote:
> Hi,
>
> thanks a Paul and EdKlotz. I don’t understand the option of Paul very well. I’ll see it with calm.
> EdKlotz, the problem of your option is that restarting the optimization from scratch suppose a root relaxation (important computational time) while that it isn’t necessary because the better lower bound is when x6-x10 are relaxed (is to say, the problem P1).

Yes, I understand that the approach I proposed no longer provides you the lower
bound you obtained when solving P1. But, with the variable fixings you do,
the lower bound you obtain at the root node solve of P2 may be better. So,
I still recommend you compare the two tree approach I described with any
single tree approach you devise.

> Now, I am doing the following:
> I built the P1 problem with x1-x5 as binary variables and x6-x10 relaxed. I solve this problem and I have a LB. After, I modify the P1 problem fixing the values of x1-x5 with xi.setLB() or xi.setUB() and un-relaxing the x6-x10 variables (object IloConversion…). I call to this problem as P2. When I solve P2, it does a relaxation…but I don’t want to do it because the LB is the value of P1. I think that I could avoid it. In fact, the P2 could continue from the last node solved in P1….

OK, so let's suppose the lower bound you got from P1 is tighter than the one
you get from solving the root node relaxation associated with P2. Using a
cut callback, you could add a cut that the objective function is >= the lower
bound obtained from P1 (assuming you are minimizing). So, you can obtain
the benefit of the lower bound of P1 if it is tighter. However, we have
seen some cases where adding constraints involving the objective function
worsens CPLEX's performance because it makes the pseudo costs CPLEX typically
calculates to select the branching variable less informative. Nonetheless,
particularly if you set priorities per Paul's suggestion, you may not
have this problem in your case. And regardless, it's worth a try.

Ed
>
> thanks a lot!!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Thanks Paul,
Now I understand your explanation. But, I have a question.

It is possible that cplex choose branch a variable with a lower priority? For example, it is possible that CPLEX branh by x7 before x3 during the process?

If it is possible, this solution is not good for me.

Thank you Paul.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> dbaena wrote:
> Thanks Paul,
> Now I understand your explanation. But, I have a question.
>
> It is possible that cplex choose branch a variable with a lower priority? For example, it is possible that CPLEX branh by x7 before x3 during the process?
>
> If it is possible, this solution is not good for me.
>
> Thank you Paul.

That's hard to say for sure without examining major amounts of source code.
However, based on a quick look, CPLEX typically respects the priorities specified
by the user. The only possible exceptions I see involve situations where CPLEX
encounters numerical difficulties solving a node LP.

One way to check this is to set CPLEX's MIP search parameter to 1 (traditional
branch and cut search) and set the MIP interval to 1. Then the node log
CPLEX writes to disk will include information on the branching variable at
each node. You can use that to confirm that you get branching selections
consistent with your priorities.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Thanks a lot EdKlotz.
Best regards,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Branching priorities work as follows:

At each node, CPLEX collects the list of all integer variables with fractional LP value. Then, from this list, it filters the variables by priority such that only those variables survive that have the highest priority among the fractional integer variables at the current node. Then, one of the surviving variables is chosen as branching variable.

This means that if you set branching priorities of x1 to x5 to 1, and leave the priorities of x6 to x10 at 0, CPLEX will always branch on one of the x1 to x5 variables first, provided that at least one of them is fractional in the current LP relaxation. So, if all x1 to x5 are integral in the LP solution, CPLEX will branch on x6 to x10, even though the x1 to x5 variables are not yet fixed.

Overall, I am pretty sure that the most simple approach is actually the best for your situation. Namely, just solve the problem with x6 to x10 relaxed to continuous variables, then fix x1 to x5 to their optimal values and turn x6 and x10 back into integer variables, and finally do a second optimization run on this model.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Thanks a lot Tobias!
Yes, I think also that the most simple approach is actually the best for your situation. I'll try with simple option (just solve the problem with x6 to x10 relaxed to continuous variables, then fix x1 to x5 to their optimal values and turn x6 and x10 back into integer variables, and finally do a second optimization run on this model) with big problems and I hope to obtain good results.

Thank you for your help.

Best regards,
#CPLEXOptimizers
#DecisionOptimization