SoPlex

The Sequential object-oriented simPlex

About

SoPlex is a Linear Programming (LP) solver based on the revised simplex algorithm. It features preprocessing techniques, exploits sparsity, and offers primal and dual solving routines. It can be used as a standalone solver reading MPS or LP format files as well as embedded into other programs via a C++ class library. SoPlex has been implemented as a part of Roland Wunderling's Ph.D. thesis Paralleler und Objektorientierter Simplex-Algorithmus (in German) and is available in source code. SoPlex is free for academic research and can be licensed for commercial use.

News

07/Mar/2014 Binaries for Linux and Windows available for download.
27/Feb/2014 Version 2.0.0 released. Release Notes
25/Feb/2014 Website relaunched.
16/Oct/2013 Version 1.7.2 released. Release Notes
04/Jan/2013 Version 1.7.1 released. Release Notes
31/Jul/2012 Version 1.7.0 released. Release Notes
28/Oct/2011 Version 1.6.0 released. Release Notes

older news...

30/Sep/2010 Version 1.5.0 released. Release Notes
06/Aug/2010 Patch 1.4.2c available for download providing an additional interface method to set a starting basis in the SoPlex class.
19/Jan/2010 Patch 1.4.2b available for download. Please update if you encounter problems in combination with older compiler versions.
12/Jun/2009 Patch 1.4.2a available for download. Please update.
11/Sep/2009 Version 1.4.2 released. Release Notes
20/Feb/2009 Version 1.4.1 released. Release Notes
30/Sep/2008 Version 1.4.0 released. Release Notes
27/Aug/2007 Version 1.3.2 released. Release Notes
21/Aug/2007 Website relaunched.
17/Nov/2006 Version 1.3.1 released. Release Notes
03/Feb/2006 Version 1.3.0 released. Release Notes
10/Apr/2002 Version 1.2.1 released. Release Notes
14/Jan/2002 Version 1.2.0 released. Release Notes

License

SoPlex is distributed under the ZIB Academic License. You are allowed to retrieve SoPlex for research purposes as a member of a non-commercial and academic institution.
If you want to use SoPlex commercially or if you are interested in maintenance and support, please contact us by sending an email to Thorsten Koch.

Any publication for which SoPlex is used must include an acknowledgment and a reference to the Ph.D. thesis:

Roland Wunderling,
Paralleler und Objektorientierter Simplex-Algorithmus,
ZIB technical report TR 96-09, Berlin 1996.

Here is the corresponding bibtex entry.

Download

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

older versions...
  • SoPlex version 1.6.0
  • Source code:

  • SoPlex version 1.5.0
  • Source code:

  • SoPlex version 1.4.2
  • Source code:

    Additional files:
    • datakey.h: For some older versions of the GCC compiler, the implementation of the SoPlex index management can trigger a bug in glibc. We recommend to either update your compiler or use the following alternative SoPlex implementation: Copy file datakey.h to src directory.
    • soplex.cpp: Fix for a small bug appearing when the LP is solved to optimality by the SoPlex simplifier. Copy file soplex.cpp to src directory.
    • soplex.h: Additional interface method to set a starting basis within the SoPlex class. Copy file soplex.h to src directory.

  • SoPlex version 1.4.1
  • Source code:

  • SoPlex version 1.4.0
  • Source code:

  • SoPlex version 1.3.2
  • Source code:

    Additional files:
    • example.cpp: The current version still outputs the old version number in the example program. This patched version outputs the correct number. Copy file to src in the SoPlex directory.
    • make.darwin.x86.gnu.dbg: Makefiles needed for Mac (Darwin) with Intel processors (contributed by Volker Kaibel). Copy files to make in the SoPlex directory.
    • make.darwin.x86.gnu.opt: Makefiles needed for Mac (Darwin) with Intel processors (contributed by Volker Kaibel). Copy files to make in the SoPlex directory.

  • SoPlex version 1.3.1
  • Source code:

Platforms

SoPlex is completely implemented in C++. The code should be compliant with the current ANSI standard. RTTI and STL (other than iostream) are not used. With a decent modern C++ compiler you should have a chance.

We have tested SoPlex with compilers from

  • GNU
  • Compaq
  • Intel
  • SUN
  • HP
  • SGI
  • IBM
  • MS Windows

More details can be found in the Doxygen documentation.

FAQ

Frequently asked questions about SoPlex

  1. I have installation problems. What can I do?

    Please have a look at the INSTALL file. If you are using SoPlex version 2.0.0 or higher you should try to recompile with LEGACY=true. This will restore the previous command line interface and disable some new features like iterative refinement with rational arithmetic.

  2. How can I contribute?

    Please report bugs and problems.
    In fact, a couple of improvements of SoPlex are possible. If you are interested in helping please contact us.

  3. So, how do I start working with SoPlex?

    To just read LPs from a file and solve them without modifying the LPs, compile SoPlex and use it on the command line. Calling the binary without parameters gives you some usage information. To use SoPlex as a callable library, see src/example.cpp or src/soplexmain.cpp (from which the SoPlex binary is compiled) on how to construct an LP, solve it, and extract the solution. For further details, you have to consult the doxygen documentation of the code (or even the code itself). Another good starting point might also be the SoPlex interface of SCIP.

  4. Can I use SoPlex with Branch-and-cut or MIP solvers?

    Yes, but the corresponding software needs an interface. Currently, the following frameworks have an interface to SoPlex.

    • SCIP - Solving Constraint Integer Programs.
    • ABACUS has an older interface to 1.2.1 only.
    • There is also an interface to COIN OSI.
  5. Why is malloc/free sometimes used and not new/delete?

    Because there is no realloc with new/delete. Because malloc is faster. And we only use it for builtin types or so called "Data Objects" . If you do not like this decision, it is quite easy to change spxalloc.h such as to use new/delete.

  6. Can SoPlex solve Integer Programs (IPs)?

    No. You need an IP-Solver for this. Most IP-Solver use LP-Solvers as a subroutine and do some kind of Branch-and-Bound. For instance, you can use SCIP (Solving Constraint Integer Programs) together with SoPlex to solve IPs. SCIP can be obtained at here and is distributed under the ZIB academic license, like SoPlex.

  7. Is there a Windows version?

    The code is tested to compile under Microsoft Visual Studio 2008 and 2010. It should also be possible to create a Windows version by compiling it with the GCC under Cygwin or minGW

  8. I want a primal and a dual simplex, where are they?

    That is nearly easy. You can set SoPlex to use the ENTERing and LEAVEing algorithm and COLUMN and ROW representation.

     ENTER LEAVE
    COLUMNPrimalDual
    ROW Dual Primal

    COLUMN oriented is the "usual" representation. Then Entering is the Primal and Leaving is the Dual algorithm. In ROW oriented representation, we have in principle the explicit dual and then the algorithms are reversed. The only problem is that SoPlex is a composite simplex algorithm. That means it switches between entering and leaving algorithm as it needs. So all you can choose is which algorithm is used first, but then an arbitrary number of switches may occur. (Even so, often no switch at all happens.)

  9. I got a segment violation or a signal 11.

    If all of the test instances from Netlib work, but your LP gives this problem, mail your LP in as an gzip'ed MPS of LP file and we will check. If you have this problem also with the test instances, check your stack space: ulimit -s will report the current size in kilobytes. Try a higher value. If this doesn't help, maybe your compiler is broken. Try compiling without optimization.

  10. I got messages or exceptions stating "This shall not be." or similar.

    Such messages are an indication of numerical trouble, which may happen from time to time especially on LPs with weird numbers. If the problem occurs with the binary, try using another scaler (call soplex without parameters to see how to specify this). If the problem occurs while using the callable library of SoPlex, you can try to add a scaler and a preprocessor yourself (see the SoPlex class) unless you solve the same LP repeatedly with small changes (as in a Branch-and-cut process, for instance). If you send us an LP or MPS file with the offending linear program together with a description of your settings, we may have a closer look at it to see if we can do something about it.

  11. Can SoPlex handle basis files?

    Yes, the binary version allows to read and write basis files using the options --readbas= and writebas=, respectively. The library version allows to read or write a basis file from within the code as well. This can be useful for debugging. If you cannot reconstruct an error occurring in the library code with the binary version, try to save a basis and try again. Note that the LP needs to be in MPS format in order to ensure compatability of the basis and the LP (the LP format cannot store ranged rows).

  12. SoPlex means "Sequential Simplex". Is there a parallel version available?

    No. Some research was done in this direction. You can find most of the results in http://www.zib.de/PaperWeb/abstracts/TR-96-09 and http://www.zib.de/PaperWeb/abstracts/SC-95-45.

  13. Is there a wrapper class/library to use SoPlex instead of CPLEX ?

    No.

  14. How can I make LP generation easier?

    You can use ZIMPL, available at under the ZIB academic license. It takes a (human readable) file describing the linear program together with a data file as input and generates LPs or MIPs in LP- or MPS-format.

  15. What kind of preprocessing is done?

    In the default setting SoPlex presolves the given LP in order to simplify the problem as far as possible by removing rows, columns, and bounds. Moreover, infeasibility or unboundedness may be detected. The simplification cannot be undone, but given a primal/dual solution for the simplified LP, the simplifier can reconstruct the primal/dual solution and basis of the unsimplified LP.

    Handled are:

    • empty rows / columns
    • unconstrained rows
    • row singletons
    • forcing rows
    • zero objective column singletons
    • (implied) free column singletons
    • doubleton equations combined with a column singleton
    • (implicitly) fixed columns
    • redundant lhs / rhs
    • redundant variable bounds
    • variables that are free in one direction
    • (weakly) dominated columns
    • duplicate rows / columns

    The preprocessing can be switched off by using the option -s0.


Mailing List and Bugs

Bugs

If you find one, it would be nice if you send a description together with a data file that shows the problem or even better a working fix to Thorsten Koch.

Mailing List

For information about new releases, patches, or for posting your questions about SoPlex, subscribe to the SoPlex mailing list here.

Developers

Main developers

Ambros Gleixner
Matthias Miltenberger

Further and former developers

Tobias Achterberg now at Gurobi
Timo Berthold
Andreas Bley now at TU Berlin
Dennis Elbr├Ąchter
Benjamin Hiller
Wei Huang now at Siemens AG, Corporate Technology
Thorsten Koch 
Sebastian Orlowski now at atesio
Eva Ramlow
Dan Steffy
Marc Pfetsch now at TU Darmstadt
Andreas Tuchscherer
Roland Wunderling former main developer - now at IBM

Cooperation

SoPlex is developed in cooperation with