Branch and price example
Answered
Hello everybody,
Are there any B&P Java example using Gurobi?
Regards
Omidi. A
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Gurobi does not support branch-and-price (which means to also add columns at local nodes of the search tree). What you can do with Gurobi is so-called "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.
3 -
Dear Dr. Achterberg,
I am using the Gurobi Optimization Suite (using LP and MIP solvers) via academic license for the development of a large-scale 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 LP-solution, 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 branch-and-price 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 MIP-run after branching at each node, then generate some new columns using pricer & solve the new LP-relaxation, and then continue the old MIP run from where it was stopped?
Thanks & Regards,
Divyam, Ph.D. Student, IIT Roorkee, India
0 -
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 branch-and-price, 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
1 -
Thanks for your prompt response. Previously, I did not elaborate on my current CG-MIP framework. I am already doing what you have suggested above. I take the incumbent solution of the first MIP-run and try to improve it again by generating new columns in the resulting LP-relaxation using the CG heuristic. After performing sufficient iterations of the CG-heuristic, I again perform a MIP-run for the new LP-solution. In this way, I keep on running such re-optimization 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 MIP-run as soon as it branches at one node or something like that?
0 -
Sure. You can install a callback, which is then called at every single node in the search tree. And you can call the abort() method to stop the MIP search. But I don't understand how this would help you.
Tobias
1 -
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 MIP-run for a large-scale problem. In my doctoral research, I am working on a large-scale airline crew pairing combinatorial optimization problem. The MIP-runtime is huge for the first LP-solution. Hence, how one can make a wise termination decision with Gurobi's MIP-solver 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 above-mentioned aim?
Thanks & Regards.
0 -
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
1 -
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 MIP-run based on a user-defined 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 MIP-run 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 MIP-run 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 MIP-run:
# at which the quality-gain 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 time-consuming?
Best Regards,
Divyam
0 -
Hi Divyam - Here's a list of new features:
https://www.gurobi.com/products/gurobi-optimizer/whats-new-current-release/
Gwyneth
0 -
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.
0 -
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
0 -
The NoRelHeuristic parameter can actually be set to 0 (turn off), 1 (find one feasible solution), 2 (find five feasible solutions) or 3 (let Gurobi decide how long it runs).
Sonja
0
Post is closed for comments.
Comments
13 comments