search

coin-or / SYMPHONY

SYMPHONY is an open-source solver, callable library, and development framework for mixed-integer linear programs (MILPs) written in C with a number of unique features
https://github.com/coin-or/SYMPHONY/wiki
Other
68 stars 17 forks source link

readme

SYMPHONY

A COIN-OR Project

Projects such as this one are maintained by a small group of volunteers under the auspices of the non-profit COIN-OR Foundation and we need your help! Please consider sponsoring our activities or volunteering to help!

Latest Release

_This file is auto-generated from config.yml using the generate_readme script. To make changes, please edit config.yml or the generation scripts here and here._

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 has been deployed in a variety of application areas, including computational biology, wireless telecommunications, supply chain management, transportation services, and air transportation.

SYMPHONY is written in C and is released as open source under the Eclipse Public License 2.0.

It is distributed under the auspices of the COIN-OR Foundation.

The SYMPHONY development site is https://github.com/coin-or/SYMPHONY.

CITE

Code: DOI

Paper: http://dx.doi.org/10.1007/0-387-23529-9_5

CURRENT BUILD STATUS

Windows Builds

Linux and MacOS Builds

DOWNLOAD

What follows is a quick start guide for obtaining or building SYMPHONY on common platforms. More detailed information is available here.

Docker image

There is a Docker image that provides SYMPHONY, as well as other projects in the COIN-OR Optimization Suite here

Binaries

For newer releases, binaries will be made available as assets attached to releases in Github here. Older binaries are archived as part of SYMPHONY here.

Due to license incompatibilities, pre-compiled binaries lack some functionality. If binaries are not available for your platform for the latest version and you would like to request them to be built and posted, feel free to let us know on the mailing list.

Source

Source code can be obtained either by

Dependencies

SYMPHONY has a number of dependencies, which are detailed in config.yml. Dependencies on other COIN-OR projects are automatically downloaded when obtaining the source with coinbrew. For some of the remaining third-party dependencies, automatic download scripts and build wrappers are provided (and will also be automatically run for required and recommended dependencies), while other libraries that are aeasy to obtain must be installed using an appropriate package manager (or may come with your OS by default).

BUILDING from source

These quick start instructions assume you are in a bash shell.

Using coinbrew

To download and build SYMPHONY from source, execute the following on the command line. 

wget https://raw.githubusercontent.com/coin-or/coinbrew/master/coinbrew
chmod u+x coinbrew
./coinbrew fetch SYMPHONY@master
./coinbrew build SYMPHONY

For more detailed instructions on coinbrew, see https://coin-or.github.io/coinbrew. The coinbrew script will fetch the additional projects specified in the Dependencies section of config.yml.

Without coinbrew (Expert users)

./configure -C
make
make test
make install

USING SYMPHONY

Using SYMPHONY from the command line

To use SYMPHONY as a generic solver, type the executable name on the command line, followed by one or more of the command-line switches. On the command-line, there is one required switch---you must specify the location of the input file by using either -F 'filename' (MPS file or automatic detection with file extension) or -L 'filename' (LP format). If the -D switch is also present, the file will be assumed to be a GMPL model file with the data file specified after the -D switch. In LINUX, the following command would solve the instance sample.mps

symphony -F sample.mps

The remaining switches are used to set SYMPHONY's native parameters on the command line. Below is a list of these parameters. This list can also be obtained by executng

symphony -h

Note that all SYMPHONY parameters are denoted by a lowercase letter. Many other parameters can be set with the use of a parameter file (specified with -f). These parameters are listed in the SYMPHONY user's manual.

symphony [ -FL file ] [ -f parameter_file_name ]
        [ -hd ] [-a 0/1] [-b 0/1 ] [-s cands] [-l 0/1] [ -q 0/1 ] [ -r 0/1]
        [-j 0/1 ] [ -e n ] [ -i iters ] [ -t time ] [ -g gap ] [ -n nodes ]
        [ -u ub ] [ -p procs ] [ -k rule ] [ -v level ] [ -c rule ]
        [ -m max ] [ -z n ] [-o tree_out_file] [-w 0/1]

        -F model: model should be read in from file 'model'
                  (MPS format is assumed unless -D is also present)
        -L model: LP format model should be read in from file 'model'
        -D data: model is in AMPL format and data is in file 'data'
        -T dir: run test with MIPLIB3 models
        -h: help
        -f file: read parameters from parameter file 'file'
        -d: stop at first feasible solution
        -a 0/1: whether to use primal heuristics
        -b 0/1: whether to use reliability branching
        -s cands: use at most 'cands' candidates for strong branching
        -l 0/1: whether to impose a limit on strong branching time
        -q 0/1: whether or not to tighten root bounds
        -r 0/1: whether or not to do reduced cost tightening
        -j 0/1: whether or not to generate cgl cuts
        -w 0/1: whether or not to use hot starting in strong branching
        -e n: set pre-processing level to 'n'
        -i iters: allow a max of 'iters' iterations in presolve
        -t time: set wallclock time limit to 'time'
        -g gap: set gap limit to 'gap'
        -n nodes: set node limit to 'nodes'
        -u ub: use initial upper bound 'ub'
        -p procs: allow 'procs' additional threads or processors
        -k i: use node selection rule 'i'
        -v n: set verbosity to level 'n'
        -c i: use rule 'i' to compare candidates
        -m max: allow a max of 'max' cuts to enter per iteration
        -z n: set diving threshold to 'n'
        -o file: output vbc-like tree information to file 'file'

Using the SYMPHONY interactive optimizer

To use SYMPHONY's Interactive shell, run the executable name without any command line arguments. Then type help or ? to see a list of available commands which are as follows for this version:

    load      : read a problem in mps or ampl format
    solve     : solve the problem
    lpsolve   : solve the lp relaxation of the problem
    set       : set a parameter
    display   : display optimization results and stats
    reset     : restart the optimizer
    help      : show the available commands/params/options  

    quit/exit : leave the optimizer

So, if you want to load and solve an ampl/gmpl file, you will need to type load sample.mod sample.dat and then solve.

Using the callable library

To use SYMPHONY as a generic callable library, compile SYMPHONY as described above. The library that is created along with the solver itself can be linked to using the API described in the user's manual. For examples of using the callable library in this way, see the Examples/ subdirectory.

DEVELOPING CUSTOM APPLICATIONS

To customize SYMPHONY by implementing the custom callback functions, simply modify the files in the SYMPHONY/Applications/USER/ subdirectory, as described in the user's manual and follow the compilation procedures in the file SYMPHONY/Applications/USER/README. There are a number of sample applications available as examples of how to do this kind of development with SYMPHONY. These include solvers for the matching problem, the set partitioning problem (simple and advanced versions), the vehicle routing and traveling salesman problems, and the mixed postman problem. These applications are distributed as separate packages and can be downloaded from http://www.branchandcut.org. There is a white paper that guides the user through the development of the matching solver.

CURRENT TESTING STATUS

SYMPHONY can be used in a very large number of possible configurations and we simply aren't able to test them all. Below is a rough idea of the testing status of various configurations to date. If you need a certain configuration, I would be happy to help you get it running. Please let me know.

LP INTERFACES

The native interfaces for OSL and CPLEX have been deprecated Only LP solvers with OSI interfaces are supported

Well tested: CPLEX, CLP

Well tested, but have some stability or other issues: GLPK

Compiled, but not well tested: SPX

TESTED CONFIGURATIONS

SEQUENTIAL

Sequential configurations are now automatically built and tested on Linux, OS X, and Windows using Github Actions (see above for status).

SHARED MEMORY PARLLEL (OpenMP)

Builds and passes unit test with gcc and CLP on LINUX.

DISTRIBUTED MEMORY PARALLEL (PVM)

Known configurations that build and pass unit test

APPLICATIONS

CUT GENERATORS

Cut generators are supplied by the Cut Generation Library (CGL). The cut generators that are turned on by default have been well tested. Two cut generators that are part ofthe CGL are turned off by default because of known issues. These are lift and project cuts and the simple rounding cuts. The generator for Gomory cuts works well, but has somenumerical issues. We found a few cases where the optimal solution was not found when using the Gomory cut generator, especially in combination with CPLEX. If the solver is not performing as it should, try turning off some of the cut generators to see if that fixes the problem.

ADDITIONAL DOCUMENTATION

If you have downloaded a source distribution, LaTex source for the full documentation is available in the SYMPHONY/Doc/ subdirectory. Quick start guides and pointers to other on-line documentation can be found below.

The PDF version of the manual is available here:

https://coin-or.github.io/SYMPHONY/doc/SYMPHONY-5.7.1-Manual.pdf

An on-line version that is for a slightly earlier release is here:

http://coin-or.github.io/SYMPHONY/man-5.7/

Project Links

AUTHORS

SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and Laci Ladanyi (ladanyi@us.ibm.com). Menal Guzelsoy (menal.guzelsoy@gmail.com) and Ashutosh Mahajan (amahajan@iitb.ac.in.edu) have been instrumental in development since version 5.0.

ACKNOWLEDGEMENT

SYMPHONY was developed with support from