Coluna is a branch-and-price-and-cut framework written in Julia. The user introduces an original MIP that models his problem using the JuMP modeling language and our specific extension BlockDecomposition that offers a syntax to specify the problem decomposition. Then, Coluna reformulates the original MIP and optimizes the reformulation using the algorithms chosen by the user. Coluna aims to be very modular and tweakable so that any user can define the behavior of his customized branch-and-price-and-cut algorithm.
Coluna is a Julia Language package.
You can install Coluna through the Julia package manager. Open Julia's interactive session (REPL) and type:
] add Coluna
The documentation is under construction. You can browse the stable documentation for an introductory example or the dev documentation if you are working with the master version of Coluna.
We aim to integrate to Coluna the state-of-the-art techniques used for branch-and-cut-and-price algorithms. We look for beta users as Coluna is under active development.
No stable feature at the moment
Features that work but you may have some bugs:
- Cuts generation
- Column generation algorithm
- Dantzig-Wolfe decomposition
- Pricing callback
- Robust cut callback
- Stabilization
- Strong-branching
Features that should work. Structural work is done but it may be not performant:
- Benders decomposition
- Branch-and-price-and-cut algorithm
- Clean up of large scale formulations
Features in development, foundations have been laid:
- Nested/Recursive decomposition
- Parallelisation of the Branch-and-Bound Tree Search
Future features:
- Mixed Dantzig-Benders decomposition
- Preprocessing specific to reformulated problems
Contributions are welcomed !
If you encounter a bug or something unexpected happens while using Coluna, please open an issue via the GitHub issues tracker or chat with us on the discord dedicated to Coluna.
You can also suggest and add new models in ColunaDemos for tests and benchmarks.
See the list of contributors who make Coluna possible.
The platform development has received an important support grant from the international scientific society Mathematical Optimization Society (MOS) and Région Nouvelle-Aquitaine.
- BlockDecomposition is a JuMP extension to model decomposition.
- DynamicSparseArrays provides data structures based on packed-memory array for dynamic sparse matrices.