Back to SYMPHONY Home Page

Quick Start Guide

SYMPHONY Version 4.0 is a powerful environment for implementing custom branch, cut, and price algorithms. The subroutines in the SYMPHONY library comprise a state-of-the-art MILP solver designed to be modular and easy to customize for various problem settings. All internal library subroutines are generic--their implementation does not depend on the the problem-setting. As of Version 4.0, SYMPHONY works out of the box as a generic MILP solver, with the capability to read both MPS files and GMPL (a subset of AMPL) files and solve the described mixed integer programs. To customize SYMPHONY, various user subroutines can be written and parameters set that modify the default behavior of the algorithm. The API for these subroutines is described in this manual and files containing function stubs are provided. As an example, by replacing the default I/O subroutine, one can easily modify the solver so that it reads in problem instances in a custom format (such as the TSPLIB format for specifying traveling salesman problem instances).

The vast majority of the computation takes place within a ``black box,'' of which the user need have no knowledge. SYMPHONY performs all the normal functions of branch, cut, and price--tree management, LP solution, cut pool management, as well as inter-process or inter-thread communication. Solvers can be built in a wide variety of configurations, ranging from fully parallel to completely sequential, depending on the user's needs. The library runs serially on almost any platform, and can also run in parallel in either a fully distributed environment (network of workstations) or shared-memory environment simply by changing a few options in the makefile. To run in a distributed environment, the user must have installed the Parallel Virtual Machine (PVM), available for free from Oak Ridge National Laboratories. To run in a shared memory environment, the user must have installed an OpenMP compliant compiler. A cross-platform compiler called Omni, which uses cc or gcc as a back end, is available for free download . For other options, visit http://www.openmp.org.

New in Version 4.0 is the extensive use of the COIN optimization libraries. SYMPHONY now uses COIN's OSI to interface with most commonly available LP solvers. Generic cuts are generated using COIN's Cut Generator Library (CGL) and the COIN LP Solver (CLP) can be used through the OSI to solve the LP relaxations. The COIN MPS reader is used to read in MILP instances in MPS format. For a summary of what else is new, see Section 1.1. The improvements have required a number of changes to the API. Code written for previous versions of SYMPHONY will be broken, but not too badly. Instructions for porting from previous version are contained in the file SYMPHONY-4.0/README-4.0.

This section of the manual is concerned with the detailed specifications needed to develop an application using SYMPHONY. It is assumed that the user has already read the first part of the manual, which provides a high-level introduction to parallel branch, cut, and price and the overall design and use of SYMPHONY.