Originally posted by: QiuFeng

Hi all,
I would like to guide the branch process, but I don't want to take over the whole branch process.

Here is one situation where I need to guide the branch process: From some heuristics, I know that part of the binary variables are going to take certain values in the optimal solution, with high probability. Of course I can't just fix these variables to those values. I'm wondering how I can use this information (the partial solution that could possibly appear in optimal solutions) to guide the B&B process? For example, let the B&B first branch on the variables that I have information about. What is the best strategy to use this partial solution? How can I do it in CPLEX, without taking over the whole branch process?

Another situation is that, I have a binary model. One part of the binary variables are set covering variables, and the other binary variables are more like "indicating" variables which are more important. Should I let CPLEX branch on "indicating" variables first ? How Can I do it in CPLEX?

Thanks in advance!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Probably, you could use Goal to construct the stack which has all the variables you would like to branch and bound on, and after all these variables have been assigned to a binary variable, use BranchAsCplexGoal to have CPLEX continue to branch itself.
What do you mean by not take over the whole branch process? You still want to use Dynamic Tree instead of B&B? If so, just ignore what I said...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: QiuFeng

thanks, but I'm using callable libraries. what is the corresponding functions in callable libraries?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Rather than messing with the branching process, you might use CPXaddmipstarts at the outset to give CPLEX either a complete or partial solution, based on the variables whose values you think you can guess. CPLEX will attempt to extend it to a feasible solution. If it succeeds, that will give you a hopefully good incumbent right away.

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

Hi Paul, although partial solution could help Cplex to work out an incumbent solution very quickly, however, it will no guarantee CPLEX would branch on these variables first. I think Feng's idea is that he would like to assign to some of the binary variables values which he believe very likely to be in the optimal solution and then branch on other variables, if this does not work, he would like CPLEX to come back to modify the values of some of the pre fixed variables and then continue to branch on other variables after fixing the original binary variables with some new values. I strongly doubt if this would be realized by starting from a partial feasible solution.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: QiuFeng

Hi Paul,
Thanks for your reply. I checked the CPLEX manual about this function. As Jim mentioned in the post above, CPXaddmipstarts helps find a feasible solution. This possibly gives a good upper bound. However, upper bound is not critical in my problem. Even the optimal solution is found by CPXaddmipstarts, how to prove optimality is still an issue. I'm wondering what kind of benefit I can dig out from this partial solution which will possibly appear in the optimal solution. For example, can the B&B tree size be reduced by first branching on the partial solution?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> QiuFeng wrote:
> For example, can the B&B tree size be reduced by first branching on the partial solution?

Off hand, I don't see why it would be reduced. You might reach optimum sooner, and you might not. Ultimately, though, every possible combination of values for the integer variables must be eliminated, either because it is infeasible or because it fails to improve on the best known solution. The sooner you get a good incumbent (preferably the optimum), the sooner you prune nodes based on the latter criterion; but feasible nodes that are not optimal but whose LP bound is better than the optimum will need to be dealt with regardless of the branching strategy.

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

Hi Paul, thanks for your input. I will give a try to CPXaddmipstarts.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

One option could be to use branch priorities. These instruct CPLEX to first branch on variables with higher priorities. You can also specify the direction into which CPLEX should branch first.
What do you mean by "not take over the whole branching process"? Could you use a branch callback that mainly branches just like CPLEX does and only performs your custom branching eventually?
#CPLEXOptimizers
#DecisionOptimization