Software


One of my main research interests is in the development of software for optimization. Primarily, I focus on so-called software frameworks that implement basic methodology with lots of hooks for customization. The hope is that with good design, the software will be useful to other people in other contexts and for a wide rang of applications. At present, the following are te major packages I maintain. However, there are many more smaller packages available at my Github page.

  • COIN-OR: A repository of open source software for operations research
  • SYMPHONY (Download): A framework for solving mixed integer linear programs
  • CHiPPS: A framework for implementing parallel tree search algorithms
  • DIP (Download): A framework for implementing decomposition-based algorithms for mixed integer linear programs
  • CBC (Download): A solver for for mixed integer linear programs developed by John Forrest (and now maintained by me)
  • MibS (Download): A solver for mixed integer bilevel linear programs
  • GImPy (Download): A Python graph class with implementations of major algorithms and visualizations
  • GrUMPy (Download): A project for visualizing mathematical programming algorithms in Python
  • DisCO (Download)
  • COIN-OR Optimization Suite (Download): An umbrella project containing a collection of many of the COIN-OR optimization codes

I also contribute to these other projects:


COIN-OR

I am the chair of the Technical Leadership Council of the COIN-OR Foundation, a non-profit foundation whose primary goal is the development of interoperable open source software for operations research. Subsidiary goals of the project are to:

  • provide a repository for hosting open source development projects related to operations research,
  • encourage mechanisms for peer review of software that complement the already-existing peer-review process for journal articles, and
  • accelerate the pace of computational research by fostering the development and release of software for operations research.

For more information, please visit the COIN-OR Web site .

Recent publications related to COIN-OR:

Recent presentations related to COIN-OR:

SYMPHONY (Download)

SYMPHONY is an open-source generic MILP solver, callable library, and extensible framework for implementing customized solvers for mixed-integer linear programs (MILPs). SYMPHONY can be built in various sequential and parallel configurations for either distributed or shared memory architectures and can be used “out of the box” as a solver for generic mixed-integer linear programs or customized through a wide variety of user callback functions and control parameters. SYMPHONY has a number of advanced capabilities stemming from the research projects discussed above, including the ability to solve multi-objective MILPs, the ability to warm start its solution procedure, and the ability to perform basic sensitivity analyses. SYMPHONY has an active user community and has been deployed in a variety of application areas, including computational biology, wireless telecommunications, supply chain management, transportation services, and air transportation.
Solvers that we have developed with SYMPHONY include:

  • Traveling Salesman Problem
  • Vehicle Routing Problem
  • Airline Crew Scheduling (Set Partitioning)
  • Mixed Postman Problem
  • Matching Problem
  • Capacitated Network Routing Problem
  • Multi-criteria Knapsack Problem

Recent publications related to SYMPHONY:

  • T.K.R., M. Guzelsoy, and A. MahajanSYMPHONY Version 5.2 User’s Manual, COR@L Laboratory Technical Report (2009) (PDF).
  • T.K.R., Parallel Branch and Cut, in Parallel Combinatorial Optimization, E. Talbi, ed. (2006) (Working paper version: PS PDF)
  • J.T. Linderoth and T.K.R., Noncommercial Software for Mixed-Integer Linear Programming, to appear in Integer Programming: Theory and Practice, John Karlof, ed. (2005) (Working paper version: PS PDF).
  • T.K.R. and M. Guzelsoy, The SYMPHONY Callable Library for Mixed Integer Programming, The Proceedings of the Ninth INFORMS Computing Society Conference (2005), 61 (Working paper version: PS PDF).
  • T.K.R., Parallel Branch and Cut for Capacitated Vehicle Routing, Parallel Computing, 29 (2003), 607 (Working paper version: PS PDF).

Recent presentations related to SYMPHONY:

CHiPPS (Download)

The COIN-OR High Performance Parallel Search Framework (CHiPPS) was developed in partnership with IBM under the auspices of the COIN-OR project described above and with funding from NSF. CHiPPS is a C++ class library for implementing scalable algorithms based on parallel tree search and is implemented in three layers.

  • The Abstract Library for Parallel Search (ALPS) implements the search handling methods required for implementing large-scale, data-intensive parallel search algorithms, such as those used for solving discrete optimization problems. The primary focus of this research is to improve the scalability of these algorithms, given that very large amounts of data are required to describe each search tree node. Source code for CHiPPS is available open source through the COIN-OR SVN repository. A description of the design of the library is contained in the slides from a talks listed. There is also a draft design document available.
  • The Branch, Constrain, and Price Software (BiCePS) is built on top of ALPS (see description above) and implements the data-handling capabilities required for implementing relaxation-based branch and bound algorithms. BiCePS makes few assumptions about the nature of the relaxation that is employed to obtain the lower bounds and hence can be used to implement algorithms based not just on linear programming relaxations, but also on relaxations involving nonlinear constraints or even relaxations based on semidefinite programming. This project is also available open source through the COIN-OR SVN repository.
  • The BiCePS Linear Integer Solver (BLIS) is built on top of BiCePS and is a concretization of this library in which the relaxation method used is linear programming. BLIS is implemented with largely the same philosophy as SYMPHONY, but is written in C++ so that the user need only derive a few classes and override the appropriate methods in order to develop a state-of-the-art parallel algorithm for a particular problem-setting. BLIS will eventually have largely the same user interface as COIN/BCP, a previously developed C++ library similar to SYMPHONY. BLIS is also available open source through the COIN-OR CVS repository.

Recent publications related to CHiPPS:

  • Y. Xu, T.K.R., L. Ladányi, and M.J. Saltzman, Computational Experience with a Software Framework for Parallel Integer Programming (Revised), to appear in the INFORMS Journal on Computing (2009) (Working paper version: PDF).
  • T.K.R., Parallel Branch and Cut, in Parallel Combinatorial Optimization, E. Talbi, ed. (2006) (Working paper version: PS PDF)
  • Y. Xu, T.K.R., L. Ladányi, and M.J. Saltzman, ALPS: A Framework for Implementing Parallel Search Algorithms, The Proceedings of the Ninth INFORMS Computing Society Conference (2005), 319 (Working paper version: PS PDF).

Recent presentations related to CHiPPS:

  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Implementing Custom Applications with CHiPPS, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Computational Experience with Parallel Integer Programming using the CHiPPS Framework, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Doing it in Parallel (DIP) with the COIN-OR High Performance Parallel Search Framework (CHiPPS), University of Newcastle, Newcastle, NSW, Australia, May 2009 (PDF).

DIP (Download)

As part of our research on decomposition-based algorithms for mixed-integer programming, we are developing a generic framework that allows users to easily implement and experiment with a wide range of integrated decomposition algorithms. Such algorithms integrate traditional decomposition techniques with polyhedral methods. The user has only to provide a partition of the constraints and a solver for the appropriate relaxation and any of the decomposition algorithms are easily employed. A decomposition-based separation algorithm is also provided as part of the framework.

Recent publications related to DIP:

Recent presentations related to DIP:

  • M. Galati and T.K.R., A Framework for Decomposition in Integer Programming, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R. and M. Galati, A Framework for Decomposition in Integer Programming, University of Newcastle, Newcastle, NSW, Australia, June 2009 (PDF).

MiBS

MibS is a solver we have been developing for solving general mixed integer linear bilevel programs. It is available here.

Recent presentations related to MibS:

  • S. DeNegre, T.K.R. Branch and Cut for Mixed Integer Bilevel Linear Programs, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R. and S. Denegre, Bilevel Integer Linear Programming, University of Newcastle, Newcastle, NSW, Australia, May 2009 (PDF).

Recent publications related to MibS:

Coin Binary Project (Download)

CoinBinary is a project I manage within COIN-OR whose goal is to make it easy to download and install binaries for a wide range of COIN projects on a wide range of platforms.

Coin All Project (Download)

CoinAll is a project I manage within CoinBinary that is an umbrella under which one can compile a large set of the COIN projects automatically in one coherent environment.

Open Solver Interface (Download)

I am involved in the design of the second generations of OSI, which provides a uniform interface to third-party solvers, such as those for linear programming. The idea is to provide a solver-independent interface with back-end implementations interfacing to specific solvers. Software written using the OSI will automatically work with any solver for which a back end has been provided without changing a single line of code. OSI is available open source through the COIN-OR

Recent presentations related to OSI:

COIN-OR Build Tools (Download)

The COIN-OR Build Tools are the infrastructure that make it possible to build many COIN projects in a coherent environment.

If you find something here useful, buy me a beer!

Trackback