GitHub

Introduction

Warning

We assume that readers are familiar with integer programming and exact optimization methods.

Coluna is under active development. Some features are undocumented because they are very experimental. Current users are expected to read the source code.

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 upfront and MathOptInterface (MOI) to delegate master and subproblems to MIP solvers.

The user introduces an original MIP that models 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 Coluna with his decomposition of the model. The BlockDecomposition syntax allows the user to implicitly 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 with 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.6+.

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

Acknowledgements

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