Introduction

Coluna is a framework written in Julia to implement a decomposition approach to optimize block structured mixed-integer programs (MIP).

Coluna relies on the tools of the JuMP-dev community at both ends of the problem treatment. It uses the JuMP modeling language up front and MathOptInterface (MOI) to delegate master and subproblems to MIP solvers.

The user introduces an original MIP that model his problem using the JuMP along our specific extension BlockDecomposition that offers a syntax to specify the problem decomposition. Coluna reformulates the original MIP using Dantzig-Wolfe and Benders decomposition techniques. Then, Coluna optimizes the reformulation using the algorithm chosen by the user.

Coluna offers a "black-box" implementation of the branch-and-cut-and-price algorithm:

  1. The input is the set of constraints and variables of the MIP in its natural/compact formulation (formulated with JuMP or MOI).
  2. BlockDecomposition allows the user to provide to Coluna his decomposition of the model. The BlockDecomposition syntax allows the user to implicilty define subsystems in the MIP on which the decomposition is based. These subsystems are described by rows and/or columns indices.
  3. The reformulation associated to the decomposition defined by the user is automatically generated by Coluna, without requiring any input from the user to define master columns, their reduced cost, pricing/separation problem, or Lagrangian bound.
  4. A default column (and cut) generation procedure is implemented. It relies on underlying MOI optimizers to handle master and subproblems. However, the user can use pricing callbacks to solve the subproblems.
  5. A branching scheme that preserves the pricing problem structure is offered by default; it runs based on priorities and directives specified by the user on the original variables.

Installation

Coluna is a package for Julia 1.0+

It requires JuMP to model the problem, BlockDecomposition to define the decomposition, and a MIP solver supported by MathOptInterface to optimize the master and the subproblems.

You can install Coluna and its dependencies through the package manager of Julia by entering :

] add Coluna

Contributions

We welcome all contributions that help us to improve Coluna. You can suggest ways to enhance the package by talking with developers on the discord chat dedicated to Coluna, or opening an issue via the GitHub issues tracker

Once the suggestion approved, you can open a Pull Request (PR) with the implementation of your suggestion.

Before requesting the review, make sure that your code follows the style guide and passes tests.

Do no forget to update docstrings and the tests when necessary. It is very important to keep clear the goal of the PR to make the review fast. So we might close a PR that fixes two unrelated issues or more.

Coluna style follows the blue style guide for Julia amended by the following instruction on naming :

Names of variables and functions are treated equally. Use names that express what the variable/function do. > Either use :

  • lowercasenospace when the nam``is composed of three words or less with no ambiguity on words separation.
  • snake_case otherwise

Note that the application of the style guide is a work in progress.

Acknowledgements

Atoptima, Mathematical Optimization Society (MOS), Région Nouvelle-Aquitaine, University of Bordeaux, and Inria