This repository contains a structured template for a branch and bound algorithm. This allows for rapid testing and experimentation of your B&B ideas.
The purpose is not for performance! The purpose is quick implementation for prototyping branch and bound ideas!
So copy or fork this repo, and apply it to your own problem by filling in the blank lines.
fail fast -someone clever
The main part of the code consists 5 Python classes within branch_and_bound.py.
Here is a brief introduction, however for more information please read the documentation within branch_and_bound.py.
Problem should contain all the relevant information for you specific problem instance.
This includes all parameters required to generate & solve an instance of this problem.
For ease of use, consider using this object in one of the following ways:
- As an inheritance of a common algebraic modelling package, such as a
docplex.mp.model.Modelobject. See example here. - Use class methods as instance generators. Great for generating instances of a particular structure.
This should just be a basic container for a solution.
Can be considered as only a dataclass if need.
But it must always contain feasible solution!
And it must always have an objective_value attribute!
In many cases, implementation is far easier when we have a so called root problem.
This is essentially an optimisation problem formulation of the problem instance, before any variable fixings.
This class shall handle that model, and then also has a solve(fixings) method that can solve the root problem, with given variable fixings.
For example, this could be the base MIP created from a problem instance.
Then variable fixings are added based on the branch and bound tree.
After the node problem is solved, these fixings are removed from the root problem.
The node object contains all information to generate a specific node. This includes which variables are fixed, which are free etc. This could either contain itself an entire model, or simply a reference to the root problem.
This is the main part of the code. Realistically, any user of this code should only ever interface with this object to either
- Set any
parameters, - Call the
solve()method, - Retrieve the
solution.
Everything else should be considered as private.
For the branch and bound process, the object has the following important attributes,
_node_list_incumbent_solution
The main branch and bound iterations are handled inside solve().
Within these iterations, we call the following important methods,
_get_next_node()_heuristic_repair()_make_children()
All should be self explanatory, however for more information on the purpose of each method see documentation inside branch_and_bound.py.
This repo is designed as a template.
Therefore, the idea is to grab the code within branch_and_bound.py, and fill in the blanks for your own purpose.
An example of this is shown in knapsack_example.py, where we fill in the branch and bound solver to solve a basic 0-1 knapsack problem.
The implementation simply fills in the code from branch_and_bound.py.
There are several test provided in test_bnb_solver.py.
These should be appropriate for any implementation, and can be used to ensure you don't break any of the code when adjusting for your own implementation.
It's a good idea to also check your implementation against another method to solve the problem. For the knapsack example, we test that the branch and bound solver matches the solution found from cplex.
We welcome and appreciate all contributions! Especially any changes that might make the template easier to understand / use / implement / extend.