Optimization Online


Customizing the Solution Process of COIN-ORís Linear Solvers with Python

Mehdi Towhidi (mehdi.towhidi***at***gerad.ca)
Dominique Orban (dominique.orban***at***gerad.ca)

Abstract: Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users customize such aspects easily. We provide a scripting mechanism to easily implement and experiment with pivot rules for the Simplex method by building upon COIN-ORís open-source linear programming package CLP. Our mechanism enables users to implement pivot rules in the Python scripting language without explicitly interacting with the underlying C++ layers of CLP. In the same manner, it allows users to customize the solution process while solving mixed-integer linear programs using the CBC and CGL COIN-OR packages. The Cython programming language ensures communication between Python and COIN-OR libraries and activates user-defined customizations as callbacks. For illustration, we provide an implementation of a well-known pivot rule as well as the positive edge ruleóa new 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.

Keywords: Linear Programming, Mixed-Integer Linear Programming, Python, Cython, COIN-OR, CLP, Simplex Pivot

Category 1: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Cahier du GERAD G-2012-07, GERAD, Montreal, Quebec, Canada, March 2012

Download: [PDF]

Entry Submitted: 03/12/2012
Entry Accepted: 03/12/2012
Entry Last Modified: 05/04/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society