PolySCIP

ZIB

About

PolySCIP is a solver for multi-criteria integer programming as well as multi-criteria linear programming with an arbitrary number of objectives. In other words, it solves optimization problems of the form:

min / max c 1 x c k x s.t. Axb , x n n

where k 2 , A m × n , b m .

Description
Bi-criteria integer program with feasible space.
Description
Discrete set in objective space of a maximization problem with dominated points (black) and non-dominated points (blue).

Description
Bi-criteria linear program with feasible space.
Description
Non-discrete set in objective space of a maximization problem with dominated points (black, gray) and non-dominated points (blue).

The name PolySCIP is composed of Poly (from the Greek πολύς meaning "many") and SCIP. It utilizes a lifted weight space approach and uses SCIP to solve weighted single-objective problems. The current version of PolySCIP computes the supported extreme non-dominated points (blue circles in the above figures) as well as unbounded non-dominated rays. Its file format .mop is based on the .mps file format.

The long-term development goal of PolySCIP is to solve general multi-criteria mixed-integer optimization problems, i.e., problems of the above form where x n 1 × n 2 with n 1 + n 2 = n .

News

13/Nov/2015 Website launched.
29/Feb/2016 SCIP Version 3.2.1 with PolySCIP version 1.0 released.
Feb/2017 New SCIP release with new PolySCIP version capable of computing all non-dominated points for bi- and tri-objective integer programs.

Download

PolySCIP is part of SCIP and comes without any warranty. The source code of PolySCIP resides in the SCIP source code directory at scip-version/applications/PolySCIP.

Installation

You can also find an INSTALL file in the PolySCIP directory located at scip-version/applications/PolySCIP.

PolySCIP uses data structures of the Lemon graph library. Lemon as well as PolySCIP use cmake for the build process.

1. Install the Lemon graph library:

  1. Download and unpack the source code
  2. Change into the Lemon directory and follow the instructions in the INSTALL file (in case of build problems, try to use a cmake version >= 3.0)

2. Build SCIP:

  1. Downloaded the SCIP Optimization Suite, unpack the archive and change into the unpacked directory
  2. Execute 'make scipoptlib' or 'make scipoptlib SHARED=true'
    • This will build SCIP, SoPlex and Zimpl. In order to build Zimpl successfully, you will need will GMP.
    • In case of problems, try to switch off dependencies. For example, if you do not have/want the READLINE library and ZLIB library, execute 'make READLINE=false ZLIB=false scipoptlib'
    • If you do not have the GMP library installed, switch off Zimpl via 'make ZIMPL=false scipoptlib'
    • You can combine all switches via 'make ZIMPL=false READLINE=false ZLIB=false scipoptlib' - this will build SCIP and SoPlex with the least dependencies
    • For more make options or in case of other problems take a look into the INSTALL file of the SCIP Optimization Suite

3. Build PolySCIP:

  1. Change into the PolySCIP directory at scip-3.2.1/applications/PolySCIP
  2. Execute 'mkdir build' and change into the 'build' directory
  3. If Lemon was installed globally at /usr/local
    • Execute 'cmake ..'
  4. If Lemon was installed at a different locaction than /usr/local
    • Execute 'cmake .. -DLEMON_INC=/path/to/lemon/include' where /path/to/lemon/include is the path to the 'include' directory of your Lemon installation
  5. Execute 'make' (and 'make doc' if Doxygen is installed on your system)
  6. The polyscip binary will be located outside of the 'build' directory in the PolySCIP directory after a successful build; command line options can be inquired via 'polyscip -h'

User Guide

For more details about the usage and file format of PolySCIP as well as an easy way to generate .mop files containing (your) mathematical programs see the PolySCIP user guide.

Developers

Main developers Former and further developers
Sebastian Schenker Timo Strunk

License

PolySCIP is part of SCIP and distributed under the ZIB Academic License. You are allowed to retrieve (Poly)SCIP for research purposes as a member of a non-commercial and academic institution. If you want to use PolySCIP, but you do not comply with the above criteria, please contact me.

If you use PolySCIP for your work, please include an acknowledgement and a reference to:
S. Schenker, R. Borndörfer, M. Skutella, T. Strunk: PolySCIP.
Mathematical Software - Proceedings of ICMS 2016, G.-M. Greuel, T. Koch, P. Paule, A. Sommese (Eds.),
Lecture Notes in Computer Science Vol. 9725, ISBN: 978-3-319-42431-6
Here is the corresponding BibTeX.

Bugs

If you find any bugs, please send a description to Sebastian Schenker.

Problem Library

MOPLIB (short for Multi-Objective Problem LIBrary) is a collection of multi-objective optimization problems. If you look for problem instances for PolySCIP, then you could use the multi-objective integer problem instances as well as the multi-objective linear problem instances from MOPLIB.

Related Links

If you develop a solver for multi-criteria optimization problems, let me know so I can list it here as well.

Bensolve - a vector linear program solver
inner - a multi-objective linear program solver

Cooperation

The development of PolySCIP started in the project A5 Multicriteria Optimisation within the Collaborative Research Center 1026 Sustainable Manufacturing - Shaping Global Value Creation.

Sustainable Manufacturing