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

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Mehdi Towhidi, Dominique Orban
DOI:https://doi.org/10.1007/s12532-015-0094-2
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2015
Tag:Software; Theoretical Computer Science
Volume:8
Issue:4
Page Number:15
First Page:377
Last Page:391
Mathematical Programming Computation :MPC 2016 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.