# PolySCIP

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:

where $k\ge 2,A\in {ℚ}^{m×n},b\in {ℚ}^{m}$.

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\in {ℤ}^{{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.

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.

• The SCIP Optimization Suite includes SCIP with PolySCIP, SoPlex and Zimpl. Choose this source code archive if you want to install PolySCIP in the most user-friendliest way.
• The SCIP source code archive contains SCIP with PolySCIP. You will have to link it to an already installed linear programming solver.

# 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:

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

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.

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.