Coluna.jl

Coluna is a branch-and-price-and-cut framework written in Julia. You write an original MIP that models your problem using the JuMP modeling language and our specific extension BlockDecomposition offers a syntax to specify the problem decomposition. Then, Coluna reformulates the original MIP and optimizes the reformulation using the algorithms you choose. Coluna aims to be very modular and tweakable so that you can define the behavior of your customized branch-and-price-and-cut algorithm.

Installation

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 provides examples to run advanced branch-cut-and-price. Improvements in documentation are expected in the future. You can browse the stable documentation if you work with the latest release or the dev documentation if you work with the master version of Coluna.

Features

We aim to integrate into Coluna the state-of-the-art techniques used for branch-and-cut-and-price algorithms.

• Features which are well-tested (but performance may still be improved).
  • Dantzig-Wolfe decomposition
  • Branch-and-bound algorithm (with branching in master)
  • Column generation (MILP pricing solver/pricing callback)
• Features that work well but need more tests/usage and performance review before being stable:
  • Strong branching (with branching in master)
  • Stabilization for column generation
  • Cut generation (robust and non-robust)
  • Benders decomposition
  • Preprocessing (presolve) of formulations and reformulations
• Features that should work. Structural work is done but these features may have bugs:
  • Benders cut generation
• Features in development.
  • Clean-up of the master formulation (removal of unpromising columns and cuts)
  • Saving/restoring LP basis when changing a node in branch-and-bound

Contributing

If you encounter a bug or something unexpected happens while using Coluna, please open an issue via the GitHub issues tracker.

See the list of contributors who make Coluna possible.

Premium support

Using Coluna for your business? Contact us to get tailored and qualified support.

Acknowledgments

The platform development has received an important support grant from the international scientific society Mathematical Optimization Society (MOS) and Région Nouvelle-Aquitaine.

Atoptima

University of Bordeaux

Inria

Related packages

• BlockDecomposition is a JuMP extension to model decomposition.
• DynamicSparseArrays provides data structures based on packed-memory arrays for dynamic sparse matrices.