Originally posted by: ecnirp

Hi,

I am implementing a cutting plane algorithm for a bilevel MIP in which my master problem (MP) is much easier to solve than my subproblem (SP). Because of this, I wish to only add cuts (by solving SP) to the MP after I have found its integer optimal solution (given the set of cuts that have been added thus far). To the best of my knowledge, whenever an integer solution is found, I must either fathom the node or make that the incumbent integer solution. I don't want to do this. I need a third option, where the node is kept active and the SP is only solved if the node is the optimal integer solution (for the MP with the current set of cuts).

In my current implementation, I re-solve the MP after each cut is added. I am curious as to whether it is possible, using CPLEX, to implement my algorithm in such a way that only one branch & bound tree is required for my MP. This would require me to be able to refrain from fathoming or making incumbent any nodes containing integer solutions. Then, when the optimal integer solution has been found, the SP is solved, and the cut is added throughout the tree. Is this possible?

Thanks,
Mike
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Take a look at the solution pool feature in CPLEX. It may be possible to configure it to retain all integer feasible solutions. I've not used it myself, so I don't know if it retains nodes our just solutions. (A node could contain more than one feasible solution.) Also, if your master has many nodes with integer feasible solutions, you could easily run out of memory (or time).

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

I've only read about bilevels and don't have any practical experience with them, but another option is to use RLT methods to find the convex hull of the lower problem, and roll it into 1 MIP. It's definitely possible, but maybe not practical. You would likely need an exponential number of cuts to find the entire convex hull.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you propose is possible, but I doubt that it is practical.
What you would need to do is a combination of an incumbent callback, branch callback, and node selection callback.
The incumbent callback would just reject any solution, and set some flag in your branch callback. Now, in your branch callback, if the flag is set, you would just create a single child without any modifications (i.e., a node that is equivalent to the current node), but assign a user node data object to the node to mark it for the node selection callback. Finally, the node selection callback would never select any of the marked nodes, provided that there are still other nodes available.

But as I said: this is really not practical. Very complicated implementation, and you lose dynamic search due to the usage of control callbacks. And even disregarding all of this, I think your current approach of resolving the master problem from scratch after each round of Bender's cuts will perform better, because then presolving, cutting plane separation, and branching can exploit the new Bender's cuts in the subsequent master problem solve.

Paul pointed you to a potential improvement: you can set the solution pool parameters in such a way that all feasible solutions that are encountered during the solving process are collected. You can even use the populate command to enumerate all feasible solutions, all optimal solutions, or all feasible solutions that are within a certain gap to optimality. When you generate your Bender's cuts for the optimal solution, you could then filter out all solutions of the pool that are cut off by your cuts. If there is a solution left in the pool, just create another set of Bender's cuts for this solution and iterate until all solutions in the pool are cut off or you have generated enough Bender's cuts.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ecnirp

I appreciate the responses.

Paul - I will look into the solution pool idea

The RLT idea wouldn't be practical in my case.

Tobias - Thanks for the explanation. I will probably stick with my current implementation. However, in the future, I may have problems with more difficult master problems. In such a case, I may want to still be somewhat stingy with how often I solve the subproblem, but I will also not want to solve MP to optimality each iteration. Do you think your method of using the 3 callback types is the only way to solve such a problem? Or would Paul's idea work best?

Thanks,
Mike
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think that the approach using the solution pool should work best in most cases.

Another possibility would be to set CPLEX parameters such that solutions are basically found in order of objective values, starting with the optimal solution.

If you set the backtrack tolerance (CPX_PARAM_BTTOL) to 0.0, and disable primal heuristics (set CPX_PARAM_HEURFREQ to -1), then CPLEX will do pure best first search, which means that the first solution that is found is optimal or close to optimal, with a small twist: CPLEX will process the nodes in best bound order, such that the currently processed node is always one with best dual bound value. Solving the LP relaxation of the node can increase (in minimization models) the dual bound, such that an integral LP solution can still be worse than the dual bound of the second best node and thus potentially non-optimal. Nevertheless, this strategy should make sure that you will only see very good solutions to your master problem in the lazy constraint callback, and for those you probably want to solve your sub problem.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: ecnirp

Thank you for all of your responses
#CPLEXOptimizers
#DecisionOptimization