Mathematical Programming Computation, Volume 8, Issue 4, November 2016

Font Size:  Small  Medium  Large

Customizing the solution process of COIN-OR’s linear solvers with Python

Mehdi Towhidi, Dominique Orban

Abstract


Implementations of the simplex method differ mostly in specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer program- ming differ mostly in the type of cuts and the exploration of the search tree. We provide a scripting mechanism to easily implement and experiment with primal and dual pivot rules for the simplex method, by building upon COIN-OR’s open-source linear programming package CLP, without explicitly interacting with the underlying C++ layers of CLP. In the same manner, users can customize the solution process of mixed-integer linear programs using the CBC and CGL COIN-OR packages by cod- ing branch-and-cut strategies and cut generators in Python. The Cython programming language ensures communication between Python and C++ libraries and activates user-defined customizations as callbacks. Our goal is to emphasize the ease of devel- opment in Python while maintaining acceptable performance. The resulting software, named CyLP, has become a part of COIN-OR and is available under open-source terms. For illustration, we provide an implementation of the positive edge rule—a recently proposed rule that is particularly efficient on degenerate problems—and demonstrate how to customize branch-and-cut node selection in the solution of a mixed-integer program.


Full Text: pdf

mpc footer
© MPS 2008-2016