Solving Constraint Integer Programs

## How to Cite

- Documentation

## SCIP Workshops

Related work, team members, cooperation, imprint and privacy statement.

SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming and branch-cut-and-price. It allows for total control of the solution process and the access of detailed information down to the guts of the solver.

older news...

## What is SCIP?

A similar technique is used for solving both Integer Programs and Constraint Programs: the problem is successively divided into smaller subproblems (branching) that are solved recursively.

On the other hand, Integer Programming and Constraint Programming have different strengths: Integer Programming uses LP relaxations and cutting planes to provide strong dual bounds, while Constraint Programming can handle arbitrary (non-linear) constraints and uses propagation to tighten domains of variables.

SCIP is a framework for Constraint Integer Programming oriented towards the needs of mathematical programming experts who want to have total control of the solution process and access detailed information down to the guts of the solver. SCIP can also be used as a pure MIP and MINLP solver or as a framework for branch-cut-and-price.

SCIP is implemented as C callable library and provides C++ wrapper classes for user plugins. It can also be used as a standalone program to solve mixed integer linear and nonlinear programs given in various formats such as MPS, LP, flatzinc, CNF, OPB, WBO, PIP, etc. Furthermore, SCIP can directly read ZIMPL models.

## Interfaces and LP solvers usable with SCIP

Detailed list of scip's features.

- very fast standalone solver for linear programming (LP), mixed integer programming (MIP), and mixed integer nonlinear programming (MINLP)
- framework for branching, cutting plane separation, propagation, pricing, and Benders' decomposition,
- constraint handlers to implement arbitrary constraints,
- variable pricers to dynamically create problem variables,
- domain propagators to apply constraint independent propagations on the variables' domains,
- separators for cutting planes based on the LP relaxation; benefit from a dynamic cut pool management,
- relaxators can be included to provide relaxations (e.g., semidefinite relaxations or Lagrangian relaxations) and dual bounds in addition to the LP relaxation, working in parallel or interleaved
- plugins to apply Benders' decomposition and implement Benders' cuts,
- primal heuristics to search for feasible solutions with specific support for probing and diving,
- node selectors to guide the search,
- branching rules to split the problem into subproblems; arbitrarily many children per node can be created, and the different children can be arbitrarily defined,
- presolvers to simplify the solved problem,
- file readers to parse different input file formats,
- event handlers to be informed on specific events, e.g., after a node was solved, a specific variable changes its bounds, or a new primal solution is found,
- display handlers to create additional columns in the solver's output.
- dialog handlers to extend the included command shell.
- conflict analysis can be applied to learn from infeasible subproblems
- dynamic memory management to reduce the number of operation system calls with automatic memory leakage detection in debug mode

## What is the SCIP Optimization Suite?

The SCIP Optimization Suite is a toolbox for generating and solving mixed integer nonlinear programs, in particular mixed integer linear programs, and constraint integer programs. It consists of the following parts:

The user can easily generate linear, mixed integer and mixed integer quadratically constrained programs with the modeling language ZIMPL. The resulting model can directly be loaded into SCIP and solved. In the solution process SCIP may use SoPlex as underlying LP solver.

Since all six components are available in source code and free for academic use, they are an ideal tool for academic research purposes and for teaching mixed integer programming.

Download the SCIP Optimization Suite below .

A further extension of SCIP in order to solve MISDPs (mixed-integer semidefinite programs) is available from TU Darmstadt: SCIP-SDP .

SCIP also includes an extension for solving Steiner tree and related problems: SCIP-Jack .

Enabling Research through the SCIP Optimization Suite 8.0 Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, Jakob Witzig Available at ACM Digital Library , June 2023 BibTeX

The SCIP Optimization Suite 8.0 Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, Jakob Witzig Available at Optimization Online and as ZIB-Report 21-41 , December 2021 BibTeX

The SCIP Optimization Suite 7.0 Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Marc Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, Jakob Witzig Available at Optimization Online and as ZIB-Report 20-10 , March 2020 BibTeX

The SCIP Optimization Suite 6.0 Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegscheider, Jonas T. Witt, Jakob Witzig Available at Optimization Online and as ZIB-Report 18-26 , July 2018 BibTeX

The SCIP Optimization Suite 5.0 Ambros Gleixner, Leon Eifler, Tristan Gally, Gerald Gamrath, Patrick Gemander, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Stefan Vigerske, Dieter Weninger, Jonas T. Witt, Jakob Witzig Available at Optimization Online and as ZIB-Report 17-61 , December 2017 BibTeX

The SCIP Optimization Suite 4.0 Stephen J. Maher, Tobias Fischer, Tristan Gally, Gerald Gamrath, Ambros Gleixner, Robert Lion Gottwald, Gregor Hendel, Thorsten Koch, Marco E. Lübbecke, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Dieter Weninger, Jonas T. Witt, Jakob Witzig Available at Optimization Online and as ZIB-Report 17-12 , March 2017 BibTeX

The SCIP Optimization Suite 3.2 Gerald Gamrath, Tobias Fischer, Tristan Gally, Ambros M. Gleixner, Gregor Hendel, Thorsten Koch, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Stefan Vigerske, Dieter Weninger, Michael Winkler, Jonas T. Witt, Jakob Witzig Available at Optimization Online and as ZIB-Report 15-60 , February 2016 BibTeX

In order to reference the general algorithmic design behind constraint integer programming and SCIP's solving techniques regarding mixed-integer linear and nonlinear programming, please cite the following articles:

- Constraint Integer Programming: a New Approach to Integrate CP and MIP Tobias Achterberg, Timo Berthold, Thorsten Koch, Kati Wolter Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2008, LNCS 5015, Pages 6–20, 2008 Available as ZIB Report 08-01 and at SpringerLink , January 2008 BibTeX
- SCIP: Solving Constraint Integer Programs Tobias Achterberg Mathematical Programming Computation, Volume 1, Number 1, Pages 1–41, 2009. Available at Mathematical Programming Computation , 2009 BibTeX

A more detailed description of SCIP can be found in

- Constraint Integer Programming Tobias Achterberg Ph.D. thesis, TU Berlin, July 2007. Available as Doctoral Thesis , January 2009 BibTeX

The features for the global optimization of convex and nonconvex MINLPs are described in

- Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8 Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller, Felipe Serrano, Stefan Vigerske, Fabian Wegscheider arXiv:2301.00587, 2023. BibTeX

The extension of SCIP to solve MIPs exactly over rational input data is described in

- A Computational Status Update for Exact Rational Mixed Integer Programming Leon Eifler, Ambros Gleixner Integer Programming and Combinatorial Optimization. IPCO 2021, Lecture Notes in Computer Science, vol 12707. pp. 163-177 BibTeX

However, for the latest developments, please consult our series of release reports .

Since November 4, SCIP is licensed under the Apache 2.0 License .

Releases up to and including Version 8.0.2 remain under the ZIB Academic License as indicated by the files contained in the releases. The new license applies from Version 8.0.3 onwards.

The files you can download here come without warranty . Use at your own risk!

Please note that version x.x.x is currently in beta stage.

## Source Code

You can either download SCIP alone or the SCIP Optimization Suite (recommended), a complete source code bundle of SCIP, SoPlex, ZIMPL, GCG, PaPILO and UG.

Click here for information on different platforms ...

- For compilation instructions please consult the installations section of the online documentation.
- SCIP is completely implemented in C. The code should compile with any C compiler that supports the C99 standard. We have tested SCIP with GNU, Clang and Intel compilers on 32- and 64-bit versions of Linux, Mac and Windows.
- If you are using the GNU compiler on SunOS and you experience a strange behavior of your program (segmentation faults), you might try a reduce the optimization level -O2 . If problems occur with STL code, you might change to a different implementation by adding -library=stlport4 to CXX_COMPILER_FLAGS . (Note: There are different implementations of the STL on SUN platforms.)

## Precompiled Packages

You can also download precompiled executables of SCIP with which you can solve MIP, MIQCP, CIP, SAT, or PBO instances in MPS, LP, RLP, ZIMPL, flatzinc, CNF, OPB, WBO, PIP, or CIP format. Note that these executables do not include the readline features (i.e., command line editing and history) due to license issues. However, you can download the free readline wrapper rlwrap to provide this missing feature to the executables.

If you use conda , you can install the components of the scipoptsuite using the conda packages .

- In order to build SCIP yourself with support for symmetry handling , you need bliss . A patched bliss fork is now available on GitHub . This fork allows to limit the number of search nodes and generators during the backtrack search and improves performance of symmetry handling in SCIP.
- For some of the mac packages you need the libgfortran and libtbb libraries, and bison . You can install them for example via homebrew: `brew install bison`, `brew install gcc` and `brew install tbb` before installing the scipoptsuite. After installation of the .sh package to a custom directory you may need to include the lib folder into your DYLD_LIBRARY_PATH. If you want to compile the Suite on a apple silicon M series processor you might need to set `ARCH=arm` as an argument to make.
- The linux precompiled binaries are built on debian and ubuntu, both debian based distributions. Chances are that you won't be able to install them on a different one, like arch-linux.
- If you download an executable containing PaPILO you might need a working installation of the TBB library in your machine. (This might also be available via your package manager, for debian, for example, it is called `libtbb2`.)
- For GCG on a linux system you need a working installation of hMETIS version >= 2.0, and zsh (apt install zsh) in your system.
- Here is the download section of MIPLIB 2017 benchmark MPS files.
- SCIP is also available on the NEOS Server , where you can post your model in LP or MPS format, or as an AMPL, GAMS, or ZIMPL model and let the NEOS Server solve it with SCIP linked to CPLEX.
- A development version of SCIP 7 to solve MIPs exactly without floating-point roundoff errors is available as a separate download on Github .

Every now and then there are SCIP Workshops where developers and users come together to discuss different approaches and implementations.

The next workshop will be held on the occasion of SCIP's 20th anniversary on November 4th, 2022. Click here for further information. Sign up for the SCIP mailing list to get notified about future events.

- An up-to-date list of publications about SCIP can be found at swMath.org .

## Projects at ZIB that use SCIP

- Optimization of Gas Transport ,DFG Research Center Matheon , Project B20.
- Advanced Solver Technology for SCM
- DESI – Durchgängig energiesensible IKT-Produktion
- Exact Integer Programming , DFG Priority Program 1307 Algorithm Engineering .
- Integrated Planning of Multi-layer Networks , DFG Research Center Matheon , Project B3.
- Service Design in Public Transport , DFG Research Center Matheon , Project B15.
- ForNe: Research Cooperation Network Optimization
- Chip Design Verification , DFG Research Center Matheon , Project D17.
- Discrete Morse Functions .
- Infeasible Linear Inequality Systems .
- MLTN - Multi-layer Transport Networks
- Stable sets and special graph classes
- Symmetries in Integer Programming , DFG Research Center Matheon , Project B12.
- VeriCount - Counting Solutions in the Field of Verification
- Scheduling the SBB Cargo Railroad routing and shipment operations at night, Combinatorial Optimization & Graph Algorithms Group , TU Berlin.
- Scheduling Techniques in Constraint Integer Programming, DFG Research Center Matheon , Project B25.

## Projects using SCIP (outside ZIB)

- Project A9: Resilient Design from SFB 805: Control of Uncertainties in Load-Carrying Structures in Mechanical Engineering , TU Darmstadt
- Projekt EXPRESS: Exploiting Structure in Compressed Sensing Using Side Constraints from SPP 1798: Compressed Sensing in Information Processing (CoSIP) , TU Darmstadt
- Project A01: Global Methods for Stationary Gastransport from Transregio/SFB 154: Mathematical Modelling, Simulation and Optimization on the Example of Gas Networks , TU Darmstadt
- Project A4: Mathematical Models and Methods for an Optimum Combination of Passive and Active Components from SFB 805: Control of Uncertainties in Load-Carrying Structures in Mechanical Engineering , TU Darmstadt
- DSP – Parallel Solver for Stochastic Mixed-integer Programming Problems, Argonne National Laboratory
- GOBNILP – Globally Optimal Bayesian Network learning using Integer Linear Programming, The University of York
- SCIL – Symbolic Constraints in Integer Linear programming , Max-Planck-Institut für Informatik
- Generic Column Generation , RWTH Aachen
- Normaliz , a tool for computations in affine monoids, vector configurations, lattice polytopes, and rational cones developed at the University of Osnabrück.
- Numberjack – A python constraint programming platform, University College Cork
- Thermos Map-driven web-based software for optimising the layout of heat networks, and associated applications, Centre for Sustainable Energy, UK

## Some Papers that use SCIP

- Conflict Analysis in Mixed Integer Programming Tobias Achterberg Discrete Optimization, Special Issue 4, 2007
- Hybrid Branching Tobias Achterberg, Timo Berthold Proc. of CPAIOR 2009, LNCS 5547, 05.2009.
- Improving the Feasibility Pump Tobias Achterberg, Timo Berthold Discrete Optimization, Special Issue 4, 2007
- Constraint Integer Programming: Techniques and Applications Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, Kati Wolter ZIB-Report 08-43.
- Constraint Integer Programming: a New Approach to Integrate CP and MIP Tobias Achterberg, Timo Berthold, Thorsten Koch, Kati Wolter Proc. of CPAIOR 2008, LNCS 5015, 2008
- Teaching MIP Modeling and Solving Tobias Achterberg, Thorsten Koch, and Martin Grötschel ORMS Today 33, no. 6
- Counting solutions of integer programs using unrestricted subtree detection Tobias Achterberg, Stefan Heinz, Thorsten Koch Proc. of CPAIOR 2008, LNCS 5015, 2008
- Experiments with Linear and Semidefinite Relaxations for Solving the Minimum Graph Bisection Problem Michael Armbruster, Marzena Fügenschuh, Christoph Helmberg, and Alexander Martin Technical Report, TU Darmstadt, 2006
- Constrained Clustering using Column Generation Babaki, B., Guns, T., Nijssen, S. CPAIOR, May 2014, Cork, Ireland
- Heuristics of the Branch-Cut-and-Price-Framework SCIP Timo Berthold Operations Research Proceedings 2007
- RENS - Relaxation Enforced Neighborhood Search Timo Berthold ZIB-Report 07-28
- Rapid learning for binary programs Timo Berthold, Thibaut Feydy, Peter J. Stuckey Proc. of CPAIOR 2010, LNCS 6140
- SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 Timo Berthold, Ambros Gleixner, Stefan Heinz, Thorsten Koch, and Yuji Shinano. ZIB-Report 12-24
- Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering Timo Berthold, Ambros M. Gleixner ZIB-Report 09-40
- A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling Timo Berthold, Stefan Heinz, Marco Lübbecke, Rolf H. Möhring, Jens Schulz Proc. of CPAIOR 2010, LNCS 6140
- Nonlinear pseudo-Boolean optimization: relaxation or propagation? Timo Berthold, Stefan Heinz, Marc E. Pfetsch Theory and Applications of Satisfiability Testing – SAT 2009, LNCS 5584, 2009
- Solving Pseudo-Boolean Problems with SCIP Timo Berthold, Stefan Heinz, Marc E. Pfetsch ZIB-Report 08-12
- Extending a CIP framework to solve MIQCPs Timo Berthold, Stefan Heinz, Stefan Vigerske ZIB-Report 09-23
- Comparing MIQCP solvers to a specialised algorithm for mine production scheduling Andreas Bley, Ambros M. Gleixner, Thorsten Koch, Stefan Vigerske ZIB-Report 09-32
- Auslegung heterogener Kommunikationsnetze nach Performance und Wirtschaftlichkeit Andreas Bley, Friederich Kupzog, and Adrian Zymolka Proc. of the 11th Kasseler Symposium Energie-Systemtechnik: Energie und Kommunikation, 2006
- Angebotsplanung im öffentlichen Nahverkehr Ralf Borndörfer, Marika Neumann, Marc E. Pfetsch ZIB-Report 08-04, to appear in Heureka'08
- The Location-Dispatching Problem: polyhedral results and Content Delivery Network Design Philippe Chrétienne, Pierre Fouilhoux, Eric Gourdin, and Jean-Mathieu Segura Electronic Notes in Discrete Mathematics 26, 867-874, 2010
- Coordination of Cluster Ensembles via Exact Methods Ioannis T. Christou IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(2):279—293, 2011
- A Branch-and-Price Algorithm for Multi-mode Resource Leveling Eamonn T. Coughlan, Marco E. Lübbecke and Jens Schulz Proc. of SEA 2010, LNCS 6049, 226-238, 2010
- Models and Algorithms for Maximum Flow Problems Having Semicontinuous Path Flow Constraints Robert Curry and J. Cole Smith IISE Transactions, 2017
- Optimal control of spatial-dynamic processes: the case of biological invasions Rebecca S. Epanchin-Niell and James E. Wilen Agricultural and Applied Economics Association 2010 Annual Meeting
- Integer linear programming models for topology optimization in sheet metal design Armin Fügenschuh and Marzena Fügenschuh Mathematical Methods of Operations Research, to appear (2008)
- Scenario Technique with Integer Programming for Sustainability in Manufacturing Armin Fügenschuh, Pia Gausemeier, Günther Seliger, and Semih Severengiz Lecture Notes in Business Information Processing 46, 320-331, 2010
- Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs Gerald Gamrath and Marco E. Lübbecke Proc. of SEA 2010, LNCS 6049, 239-252, 2010
- Ein neuer Ansatz zur Optimierung des Bilanzausgleichs in einem Gasmarktgebiet Uwe Gotzes Zeitschrift für Energiewirtschaft, 1-13, 2019
- Using Model Counting to Find Optimal Distinguishing Tests Stefan Heinz and Martin Sachenbacher Proc. of CPAIOR 2009, LNCS 5547
- Exact and Approximate Sparse Solutions of Underdetermined Linear Equations Sadegh Jokar, Marc E. Pfetsch ZIB-Report 07-05
- Computing Optimal Morse Matchings Michael Joswig and Marc E. Pfetsch SIAM Journal on Discrete Mathematics 20, no. 1, 2006
- Orbitopal Fixing Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch Proc. of the 12th Integer Programming and Combinatorial Optimization conference (IPCO) M. Fischetti and D. Williamson (eds.), LNCS 4513, Springer-Verlag, 74-88, 2007
- On connectivity limits in ad hoc networks with beamforming antennas Moritz Kiese, Christian Hartmann, Julian Lamberty, and Robert Vilzmann EURASIP Journal on Wireless Communications and Networking 2009, No.7, 74-88, 02.2009
- Approximated segmentation considering technical and dosimetric constraints in intensity-modulated radiation therapy with electrons Antje Kiesel and Tobias Gauer ArXiv e-prints, May 2010
- Rapid Mathematical Programming or How to Solve Sudoku Puzzles in a few Seconds Thorsten Koch Operations Research Proceedings 2005
- Algorithms to separate {0,1/2}-Chvatal-Gomory cuts Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka Algorithmica 55, No. 2, 375-391
- A formulation space search heuristic for packing unequal circles in a fixed size circular container C. O. López and J. E. Beasley European Journal of Operational Research 251 (2016) 64–73
- Large-scale identification of genetic design strategies using local search Desmond S. Lun, Graham Rockwell, Nicholas J. Guido, Michael Baym, Jonathan A. Kelner, Bonnie Berger, James E. Galagan, and George M. Church Molecular Systems Biology 5, No. 296, 2009
- Optimization Methods For Selecting Founder Individuals For Captive Breeding or reintroduction of Endangered Species Webb Miller, Stephen J. Wright, Yu Zhang, Stephan C. Schuster, Vanessa M. Hayes Pacific Symposium on Biocomputing, 43-53, 2010
- Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics Sebastian Orlowski, Arie M. C. A. Koster, Christian Raack, and Roland Wessäly Proceedings of the Third International Network Optimization Conference, 2007
- Branch-And-Cut for the Maximum Feasible Subsystem Problem Marc E. Pfetsch SIAM Journal on Optimization 19, No. 1, 21-38 (2008)
- Integer Programming and Sports Rankings Christian Raack, Annie Raymond, Thomas Schlechte, Axel Werner ZIB-Report 13-19
- Rostering from staffing levels: a branch-and-price approach Egbert van der Veen and Bart Veltman Proc. of the 35th International Conference on Operational Research Applied to Health Services, 1-10, 2009
- Faster MIP solutions via new node selection rules Daniel T. Wojtaszeka and John W. Chinneck Computers & Operations Research 37, 1544-1556, September 2009
- Optimal Packings of Congruent Circles on a Square Flat Torus as Mixed-Integer Nonlinear Optimization Problem. Vladimir Voloshinov and Sergey Smirnov Voevodin V., Sobolev S. (eds) Supercomputing. RuSCDays 2019. Communications in Computer and Information Science, vol 1129. Springer, December 2019
- Robust Aircraft Routing Chiwei Yan and Jerry Kung INFORMS Transportation Science, July 2016

If you know about further projects or papers that use SCIP, please let us know .

For general information or questions about SCIP please write to the SCIP mailing list [email protected] after subscribing to it at the SCIP mailing list page . For licensing questions, please see the license section of the web page and the contact provided there. Trouble compiling SCIP from source? Please check the build documentation before sending an email. For questions about our SCIP interfaces on GitHub please open an issue in the corresponding repository.

## Mailing List

The SCIP mailing list can be accessed via the SCIP mailing list page . You can conveniently search the archives using Google: site:listserv.zib.de/pipermail/scip

## Stack Overflow

We are also watching the SCIP tag on stackoverflow.com and will answer your questions there. Note that we will not answer faster only because you posted the same question both to stack overflow and the mailing list.

## Reporting Bugs

SCIP has more than 500,000 lines of source code and is definitely not bug free. If you'd like to help us improve SCIP, visit our bug submission page and file a bug report in English or German.

## Student Assistants

Click here for a list of further contributors ....

We are thankful to many people who over the years have contributed code to SCIP, among others:

SCIP is developed in cooperation with

© 2023 by Zuse Institute Berlin (ZIB). For the imprint and privacy statement we refer to the Imprint of ZIB with the following additions and modifications:

## Download form

The number of SCIP downloads is tracked and used to generate statistics about the downloads and to generate the world map of download locations. The personal information is used to distinguish the number of downloads from the number of users per year that might download more than one version or archive. In addition to the privacy statements of ZIB, we hereby declare that your name and affiliation recorded for the SCIP download is used for purposes of granting licenses and for statistics about software downloads, and is processed and stored on our server for the duration of a year.

## Google OR-Tools

- Español – América Latina
- Português – Brasil
- Tiếng Việt
- Installation

## Route. Schedule. Plan. Assign. Pack. Solve.

## Get started with OR-Tools

Learn how to solve optimization problems from C++, Python, C#, or Java.

## Install OR-Tools

See the Release Notes for the latest updates.

## OR-Tools won gold in the international constraint programming competition every year since 2013.

About or-tools.

OR-Tools is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

After modeling your problem in the programming language of your choice, you can use any of a half dozen solvers to solve it: commercial solvers such as Gurobi or CPLEX, or open-source solvers such as SCIP, GLPK, or Google's GLOP and award-winning CP-SAT.

## Open-Source Mixed-Integer and Linear Programming Solvers and Software

## Exploring Mixed-Integer and Linear Programming Solvers

We know there are a range of solvers, free and paid, to choose from. We also know that for some situations, a free solver might be all that you need. This article is designed to help you better understand your choices among free solvers, their relative performance, and some questions to ask yourself in deciding what type of solver is right for you.

Academics : We offer a free, full-featured Gurobi license for qualifying students, faculty, and staff. Visit our Academic page to learn more.

## Common Free Mixed-Integer and Linear Programming Solvers

There are several open-source packages available for optimization. Two popular ones are GLPK and LP_Solve. The nice thing about these packages is that it’s easy to get started because you can download and install them immediately. But these packages are far behind the state of the art in optimization.

## Open-Source Performance: Mixed-Integer and Linear Programming Comparisons

Performance is typically a crucial consideration when choosing a solver. To give a sense of the relative performance of the various solver options listed above, we’ve summarized the results of independent benchmark tests maintained by Hans Mittelmann at Arizona State.

If we look at performance on Mixed Integer Programming (MIP) models across a broad set of test models, the table below shows results along two key dimensions: a) was the solver able to solve the model, and b) how quickly was the model solved? As you can see from the results, performance varies widely across solvers.

Internally, when testing GLPK and LP Solve on over 2400 models (ones that Gurobi can solve in under 1000 seconds), one of the solvers failed in 63% of the test cases, while the other failed in about 72% of the test cases.

What does it mean to fail? Sometimes the free solvers simply reached the 1,002nd time limit before optimizing the problem. But in some cases, the solvers reported an incorrect solution or falsely concluded that the problem was infeasible .

People often assume that open-source packages are close to the performance of commercial products, figuring that the free solvers might be two times or maybe ten times slower than their commercial alternatives. The reality is that Gurobi can often be 10,000 times faster than open-source solvers.

Unfortunately, when people experience slow performance with free solvers, they often give up on optimization technology altogether .

## Three Reasons to Choose a Free Solver

As you can see from the data above, free solvers tend to struggle with practical models, either failing to solve them at all or solving them relatively slowly. However, we don’t mean to give you the impression that free solvers are never the right choice. Below are a few scenarios where you may want to consider a free solver.

## 1. There is no approved budget

Often times, when a company is first looking at using an optimization solver in their business, there may not be an approved budget. Management may still be trying to determine the role optimization can play in planning and decision-making, and the team doing the work is still “getting their feet wet.”

## 2. You prefer to program in C or C++

Most free solvers are written in C or C++ and don’t offer other APIs. GLPK requires you to use C. Gurobi offers both C and C++ APIs, as well as a full range of other APIs, including Python.

## 3. The model(s) being solved are both small and relatively easy to solve

Free solvers tend to struggle with larger and more difficult models, but if a free solver is able to solve your problem now, and you are confident that your problem won’t become more difficult in the future, then a free solver could be a reasonable choice.

We want to stress that you should consider future growth in the model. We’ve seen many situations where free solvers worked well on a small prototype but were unable to handle the production model. This can cause a lot of rework that you may be able to avoid.

Before you make the choice to use a free solver, we suggest that you look at relative performance on models of similar size and complexity to those that you are likely to want to solve eventually. We are happy to assist if you like. We have a very large library of models and may be able to run a specific comparison.

## Avoiding the “False Negative” Trap

One of the most important questions people tend to ask when they are first exploring solvers is if optimization is a fit for their business. We have seen cases where someone selected a free solver, tried building a model, and the solver just couldn’t handle the problem. As a result, they assumed their problem was just too complex to use optimization techniques.

Others find free solvers just too hard to use, given the solver didn’t support the programming language they preferred, they couldn’t get support, etc. The team then ends the project and moves on. This is unfortunate since, with the right tools and support, the project might have been a great success. If you find yourself in this situation, please contact us. We may be able to help steer you in the right direction so you get the results you need to support continuing with the project.

## Should I Start with Open-Source Tools and Switch to a Commercial Tool Later ?

It’s great that it’s easy to get started with open-source tools, but you should approach them with your eyes open. For example, if an open-source tool is unable to solve your model, you shouldn’t assume that your project is hopeless.

Additionally, a state-of-the-art commercial solver can save valuable development time in several ways. First, the interfaces in commercial solvers are typically more polished and advanced than those in open-source tools. For example, the Gurobi Python interface brings a modeling syntax to the popular Python language. Second, commercial systems like Gurobi offer pre-built IT infrastructure like client-server options and cloud computing.

## Overview of Free vs. Commercial Solvers

There are several important differences between free and commercial solvers you should keep in mind:

## Try Gurobi for Free

Sign up below for a free commercial evaluation or academic license. Then take Gurobi for a spin! You can even export and run your MPS files and experience the difference for yourself.

## Guidance for Your Journey

30 day free trial for commercial users, always free for academics.

GUROBI NEWSLETTER

Latest news and releases

- Why Gurobi?
- Gurobi Optimizer
- Linear Programming (LP) – A Primer on the Basics

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

## Evaluation License

Academic license, cloud trial.

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Looking for documentation?

## Jupyter Models

Case studies, privacy overview.

## GLPK (GNU Linear Programming Kit)

Introduction | Downloading | Documentation | Mailing Lists/Newsgroups | Request an Enhancement | Report a Bug | Maintainer

## Introduction to GLPK

The GLPK ( G NU L inear P rogramming K it) package is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library.

GLPK supports the GNU MathProg modeling language , which is a subset of the AMPL language.

## Downloading GLPK

The GLPK distribution tarball can be found on http://ftp.gnu.org/gnu/glpk/ [via http] and ftp://ftp.gnu.org/gnu/glpk/ [via FTP]. It can also be found on one of our FTP mirrors ; please use a mirror if possible.

To make sure that the GLPK distribution tarball you have downloaded is intact you need to download the corresponding .sig file and run a command like this:

gpg --verify glpk-4.32.tar.gz.sig

If that command fails because you do not have the required public key, run the following command to import it:

gpg --keyserver keys.gnupg.net --recv-keys 5981E818

and then re-run the previous command.

## Documentation

The GLPK documentation consists of the Reference Manual and the description of the GNU MathProg modeling language. Both these documents are included in the distribution (in LaTeX, DVI, and PostScript formats).

## Mailing Lists/Newsgroups

GLPK has two mailing lists: [email protected] and [email protected] .

The main discussion list is [email protected] , and is used to discuss all aspects of GLPK, including development and porting.

There is a separate list used for reporting bugs, [email protected] . For details on submitting a bug report, please see the section Report a Bug below.

Announcements about GLPK and most other GNU Software are made on [email protected] .

To subscribe to these or any GNU mailing lists, please send an empty mail with a Subject: header line of just "subscribe" to the relevant -request list. For example, to subscribe yourself to the main GLPK discussion list, you would send mail to [email protected] with no body and a Subject: header line of just "subscribe". Another way to subscribe is to use the mailing list interface; see Help-glpk and Bug-glpk .

Currently there are no newsgroups dedicated to GLPK.

## Request an Enhancement

If you would like any new feature to be included in future versions of GLPK, please send a request to [email protected] .

Please remember that development of GLPK is a volunteer effort, and you can also contribute to its development. For information about contributing to the GNU Project, please read How to help GNU .

## Report a Bug

If you think you have found a bug in GLPK, then please send as complete a report as possible to [email protected] .

GLPK is currently being maintained by [email protected] , [email protected] .

Please send FSF & GNU inquiries to [email protected] . There are also other ways to contact the FSF.

The GLPK package is part of the GNU project, released under the aegis of GNU.

Copyright © 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Andrew Makhorin, Department for Applied Informatics, Moscow Aviation Institute, Moscow, Russia. All rights reserved.

Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.

Updated: $Date: 2012/06/23 11:35:42 $

Linear optimization software

## HiGHS - high performance software for linear optimization

Open source serial and parallel solvers for large-scale sparse linear programming (LP), mixed-integer programming (MIP), and quadratic programming (QP) models

## Get started

HiGHS is high performance serial and parallel software for solving large-scale sparse linear programming (LP), mixed-integer programming (MIP) and quadratic programming (QP) models, developed in C++11, with interfaces to C, C#, FORTRAN, Julia and Python.

HiGHS is freely available under the MIT licence, and is downloaded from Github . Installing HiGHS from source code requires CMake minimum version 3.15, but no other third-party utilities. HiGHS can be used as a stand-alone executable on Windows, Linux and MacOS. There is a C++11 library which can be used within a C++ project or, via one of the interfaces, to a project written in other languages.

Your comments or specific questions on HiGHS would be greatly appreciated, so please send an email to [email protected] to get in touch with the team.

## Documentation

Information on how to set up and use HiGHS is given in the HiGHS Documentation page .

HiGHS is based on the high performance dual revised simplex implementation (HSOL) and its parallel variant (PAMI) developed by Qi Huangfu. Features such as presolve, crash and advanced basis start have been added by Julian Hall and Ivet Galabova. The QP solver and original language interfaces were written by Michael Feldmeier. Leona Gottwald wrote the MIP solver. The software engineering of HiGHS was developed by Ivet Galabova.

If you use HiGHS in an academic context, please acknowledge this and cite the following article

Parallelizing the dual revised simplex method, Q. Huangfu and J. A. J. Hall, Mathematical Programming Computation , 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

We greatly appreciate the financial help from our users, allowing us to improve and enhance our solvers! Donations are welcome via GitHub Sponsors at the HiGHS Sponsors page .

Tax-deductible donations are also welcome through the Linux Foundation at the HiGHS donation page.

Our interior point solver for LP has been championed as a game changer by the open-source energy systems planning community, and this has led to a "common good" funding campaign for its enhancement and development.

## Integer Linear Programming

Integer Linear Programming (ILP) is a type of optimization problem where the variables are integer values and the objective function and equations are linear.

$$ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \le \mathbf{b} \\ & && \mathbf{x} \ge \mathbf{0} \\ &&& \mathbf{x} \in \mathbb{Z}^n \end{align} $$

A Mixed-Integer Linear Programming (MILP) problem has continuous and integer variables. Mixed-Integer Nonlinear Programming (MINLP) also includes nonlinear equations and requires specialized MINLP solvers such as APOPT . MINLP solvers can also solve MILP or ILP problems although other solvers such as CPLEX, Gurobi, or FICO Xpress are specialized commercial solvers for MILP. APMonitor and GEKKO solve MINLP problems. The following integer linear programming (ILP) problem has a two potential maximum values at (1,2) and (2,2).

APMonitor Model File

Integer variables are declared in APMonitor with the prefix int . The problem is solved with MATLAB , Julia , Python or through the APMonitor Online Interface .

Python Gekko

Gekko is a Python API to APMonitor. The same ILP problem is solved with Gekko.

Nonlinear programming solvers (such as IPOPT) may not return an integer solution because they are designed for continuous variables. Mixed Integer Nonlinear Programming solvers (such as APOPT) are equipped to solve for binary or integer variables. It is selected with m.options.SOLVER=1 . Select the appropriate solver option to either find an initial solution without integer variables or an integer solution. It is sometimes desirable to find a non-integer solution first because of the often significant reduction in computation time without the integer variables.

Solution in Matrix Form

Another representation is matrix form. Gekko function qobj defines a linear or quadratic objective and axb defines the `Ax\leb` constraint.

Solution in Sparse Matrix Form

For large-scale problems, it is more efficient to solve the problem in sparse matrix form. The matrix arguments are passed to Gekko in coordinate (COO) list form. COO list form is [row indices],[values] for a vector and [row indices],[column indices],[values] for a matrix.

Additional Resources

- Dynamic Optimization with Discrete Variables
- Discrete Optimization
- Linear Programming
- Mixed Integer Nonlinear Programming (MINLP)

Documentation

- Error Messages
- PrivacyPolicy
- Release Notes
- User Reviews
- Registration
- 🎓 Begin Python
- 🎓 Begin Matlab
- 🎓 Begin Java
- 🎓 Data Science
- 🎓 Control (MATLAB)
- 🎓 Control (Python)
- 🎓 Optimization
- 🎓 Dynamic Optimization
- GEKKO (Python)
- APM Server (Windows)
- APM Server (Linux)
- Command Line
- Web Interface
- Option Overview
- Global Options
- Local Options

Model Elements

- Differential
- Constraints
- Slack Variables
- Integer Variables
- Conditional Statements
- Connections
- Intermediates

Application Modes

- 1=Simulate (SS)
- 2=Estimate (SS)
- 3=Optimize (SS)
- 4,7=Simulate (Dyn)
- 5,8=Estimate (Dyn)
- 6,9=Optimize (Dyn)
- Model (apm)
- Options (dbs)
- Classify (info)
- Solution (t0)
- Dynamic Optimization

Page last modified on February 27, 2021, at 03:33 PM

## COMMENTS

very fast standalone

solverforlinearprogramming(LP), mixedintegerprogramming(MIP), and mixedintegernonlinearprogramming(MINLP) framework for branching, cutting plane separation, propagation, pricing, and Benders' decomposition, highly flexible through many possible user plugins: constraint handlers to implement arbitrary constraints,Modified 10 years, 5 months ago. Viewed 20k times. 26. I am newbie for. I plan to use

integer linear programmingamy combinatorial optimization problem. I am more familiinteger linear programmingsolvertosolvearwithC++/objectorientedon an IDE.programmingOR-Toolsis an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows,integerandlinearprogramming, and constraintprogramming. After modeling your problem in theprogramminglanguage of your choice, you can use any of a half dozen solvers tosolveit: commercial solvers such ...GLPK

solves(LP) and milinearprogrammingxed(MIP) problems. ...integerprogrammingThe simple answer is, lp_

solveis a MixedIntegerLinearProgramming(MILP)solver. And what isLinearProgramming? See "What isLinearProgramming?" and "Oh, and we also want tosolveit as anintegerprogram." for a brief description. Also see Formulation of an lp problem in lpsolve.The GLPK (

G NU L inear P rogramming K it) package is intended forsolvinglarge-scalelinearprogramming(LP), mixedintegerprogramming(MIP), and other related problems. It is a set of routines written in ANSICand organized in the form of a callable library. GLPK supports the GNU MathProg modeling language, which is a subset of the AMPL ...HiGHS is high performance serial and parallel software for

solvinglarge-scale sparselinearprogramming(LP), mixed-integerprogramming(MIP) and quadraticprogramming(QP) models, developed inC++11, with interfaces toC, C#, FORTRAN, Julia and Python. HiGHS is freely available under the MIT licence, and is downloaded from Github.Define a

linearprogramas follows: Given that the constraints limit to either 0 or 1, any feasible solution to theintegerprogramis a subset of vertices. The first constraint implies that at least one end point of every edge is included in this subset. Therefore, the solution describes a vertex cover.APMonitor and GEKKO

solveMINLP problems. The followinginteger linear programming(ILP) problem has a two potential maximum values at (1,2) and (2,2). max y −x+y≤ 1 3x+2y≤ 12 2x+3y≤ 12 x,y≥ 0 x,y∈ Z max y − x + y ≤ 1 3 x + 2 y ≤ 12 2 x + 3 y ≤ 12 x, y ≥ 0 x, y ∈ Z.