Coluna.jl: A branch-cut-and-price framework in Julia (Abstract)

Coluna is an open-source branch-and-cut-and-price framework in Julia developed by Atoptima, a company that designs and develops cutting-edge cloud-based applications for all businesses requiring complex resource assignment optimization, in collaboration with members of Inria and Université de Bordeaux. We first give an overview of the project, of the architecture of the framework, and we present the Generalized Assignment problem with which we introduce the main features of Coluna. In the first example, we model the generalized assignment problem with JuMP and optimize it using Gurobi. Then, we use BlockDecomposition to perform a Dantzig-Wolfe decomposition over the machines. We then optimize the problem with Coluna. The latter reformulates the problem and runs a Branch-and-Price on the reformulation. In the second example, we consider a variant of the generalized assignment problem where one has to pay to use a machine. We present a family of valid inequalities to improve the quality of the formulation. We define a cut callback to separate these inequalities with Coluna and then run a branch-cut-and-price. In the third example, we want to pack circles (in two dimensions) into two boxes at minimum cost. We decompose the problem over the boxes. Since the subproblems are non-linear, we must use a pricing callback to solve them. We show how to define the pricing callback and optimize the problem using Coluna. Coluna is registered package. The project is available at https://github.com/atoptima/Coluna.jl