Branch and price example
AnsweredHello everybody,
Are there any B&P Java example using Gurobi?
Regards
Omidi. A

Gurobi does not support branchandprice (which means to also add columns at local nodes of the search tree). What you can do with Gurobi is socalled "column generation". This means to solve the root LP relaxation in a loop with your pricer producing new columns until the pricer does not find any additional improving variables. Then, you would install the integrality restrictions for the variables of the final root LP relaxation and solve the resulting problem as a MIP.
But note that this procedure will only be a heuristic. Because you are not generating additional columns at the local nodes of the MIP search tree, it could be that you are missing the optimal solution. But in many cases, column generation is a pretty good heuristic.

Dear Dr. Achterberg,
I am using the Gurobi Optimization Suite (using LP and MIP solvers) via academic license for the development of a largescale optimization framework for solving complex airline crew pairing optimization problems (goal of my doctoral thesis). In that, I have developed a Column Generation heuristic in which a root LP relaxation is solved first until the desired quality of the LPsolution, which is then solved using Gurobi MIP solver by including integrality constraints. It is similar to what you have mentioned here. However, in an attempt to further improve the performance of my framework, I want to implement a branchandprice algorithm. I have explored a lot but have not been able to find a way around using the Gurobi solvers. Is it possible to use Gurobi's MIP solver to stop the MIPrun after branching at each node, then generate some new columns using pricer & solve the new LPrelaxation, and then continue the old MIP run from where it was stopped?
Thanks & Regards,
Divyam, Ph.D. Student, IIT Roorkee, India

No, unfortunately not. Gurobi's data structures and algorithms are designed for a fixed number of variables during the solving process. Hence, if you add more variables, you need to start from scratch.
What you could do is to let your MIP run until some point (some reasonable solution is available, or even until optimality), then look at the incumbent solution (and maybe also at other solutions in the solution pool) and generate new variables that would potentially be able to improve those solutions. Then, start the MIP solve from scratch with the extended model.
But note that such an approach would also just be heuristic and doesn't guarantee global optimality. To get global optimality you need to apply branchandprice, which means that you have to use a different framework that supports this. For example, you could use SCIP. But note that this will be a major implementation effort.
Regards,
Tobias

Thanks for your prompt response. Previously, I did not elaborate on my current CGMIP framework. I am already doing what you have suggested above. I take the incumbent solution of the first MIPrun and try to improve it again by generating new columns in the resulting LPrelaxation using the CG heuristic. After performing sufficient iterations of the CGheuristic, I again perform a MIPrun for the new LPsolution. In this way, I keep on running such reoptimization loops until I find an integer solution with the desired quality. I came across SCIP too (btw great work there). However, adapting to SCIP will require unimaginable implementation efforts as I have done all the developments (idea prototyping) in Python. Hence, I am looking for a way around Gurobi only. Are there any features in Gurobi's suite that allows stopping the MIPrun as soon as it branches at one node or something like that?

I have realized it now that this won't take me anywhere. I am keen on understanding what are the customization features available with the Gurobi's MIP solver.
I just have another doubt but I am not sure whether it is okay to put it in this thread or not? This is in regard to the termination of a MIPrun for a largescale problem. In my doctoral research, I am working on a largescale airline crew pairing combinatorial optimization problem. The MIPruntime is huge for the first LPsolution. Hence, how one can make a wise termination decision with Gurobi's MIPsolver given that the aim is to find an approximately good integer solution (not optimal) in the minimum time possible? I am already using the MIPFocus feature in order to prioritize finding a better feasible solution rather than proving its optimality. Are there any other features that could be used in the light of the abovementioned aim?
Thanks & Regards.

This is a tough question. How to choose parameters to find good solutions quickly depends heavily on the type of problems you are solving. As far as I understand, a main issue with your models is that solving the LP relaxation takes very long. Hence, I guess that Gurobi is only able to process a very few number of nodes within the time that you want to wait. In this case, you may want to try the "NoRel" heuristic, which can be activated via the "NoRelHeuristic" parameter. This tries to find feasible solutions without having to solve the full LP relaxation.
You may also try the "ImproveStartGap", "ImproveStartTime", or "ImproveStartNodes" parameter. These parameters activate the improvement phase after the corresponding criterion has been hit. With Gurobi 9.0 we significantly improved the heuristics used in this improvement phase.
So, maybe a combination of finding a solution with the "NoRel" heuristic and then improving it in the improvement phase may get you some good solutions without having to solve too many full LP relaxations.
Best regards,
Tobias

Thanks, Tobias, for giving these great suggestions. I will explore them and would ask for more input if required. I am currently using Gurobi v8.1.1 to keep the experimental settings constant for a fair comparison among the experiments performed this year. Still, I will check the performance of my framework with Gurobi 9.0. Is there any document where I could learn about the changes made in v9.0 over the v8.1.1?
Also, I have seen that there are termination parameters in Gurobi to stop a MIPrun based on a userdefined time limit and/or optimality gap. I aim to find feasible solutions as soon as possible rather than improving the bound. Given this, I am finding it difficult to terminate a MIPrun profitably. With your above suggestions, I could adjust the focus of the MIP to find feasible solutions first. But, how can I automate the termination of a MIPrun based on the fact that, after a point, finding a feasible solution is not worth in comparison to the computational resources to be spent in it? In other words, is it possible to identify a point in a MIPrun:
# at which the qualitygain in the previous feasible solution was not much in comparison to the runtime spent in finding it, or
# after which even finding a feasible solution would be timeconsuming?
Best Regards,
Divyam

Hi Divyam  Here's a list of new features:
https://www.gurobi.com/products/gurobioptimizer/whatsnewcurrentrelease/
Gwyneth

Thank you, Gwyneth. The page is descriptive enough. Could you guide me to the documentation where I could find description of all parameters related to MIP solver of Gurobi? For example, I am not able to find anything related to "NoRelHeursistic" param.
@Dr. Tobias: can you give your feedback on the doubts I asked in the last message.

The "NoRelHeuristic" parameter is undocumented. Just set it to 1 in order to activate the heuristic.
You cannot predict when new incumbent solutions will be found and how their quality will be. Of course, the global dual bound tells you the best possible quality of any solution that can be found in the future, but just because the last few incumbent solutions did not improve the primal bound much does not say that there won't be a much better solution found within the next few seconds.
If you want to implement a more complex termination criterion, you can install a callback function that tracks certain statistics (e.g., you could check the primal and dual bounds) and aborts the solve if you think that it is now a waste of time.
Regards,
Tobias
Please sign in to leave a comment.
Comments
12 comments