[Coin-discuss] SCIP: an open-source Constraint Mixed Integer Programming Solver

[Tobias Achterberg]

Dear colleagues,

the following announcement has only limited relation to the COIN project, but if you are looking for
 open-source software for Mixed Integer Programming, you might be interested. However, if you think
the COIN LP solver of John Forrest is a greate piece of software (which is true), you have another
opportunity to bring it to good use by using SCIP linked to CLP.

=====

I'd like to announce the release of SCIP (Solving Constraint Integer Programs).
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.
It integrates techniques from Mixed Integer Programming, Constraint Programming
and SAT Solving.
SCIP can also be used as pure MIP solver or as framework for branch-cut-and-price.

You can download the complete source code of the current version 0.80 from

http://scip.zib.de

SCIP is free of charge for academic institutions and non-commercial use. If you
want to use it as a commercial institution, you have to obtain a commercial License
from ZIB.
(Because SCIP is not free of charge for commercial use, I could not incorporate it into
the COIN project.)

SCIP has the following features:
* framework for branching, cutting, pricing and propagation
* multi LP solver support through an LP interface, currently supporting
    - CPLEX
    - Soplex
    - CLP
* highly flexible through many possible user extensions:
    - constraint handlers to implement arbitrary constraints, currently supporting
      linear constraints and some specializations like knapsack and set packing,
      set covering, and set partitioning
    - separators to apply cutting planes on the LP relaxation
          * clique cuts
          * c-MIR cuts
          * Gomory mixed integer cuts
          * implied bound cuts
          * strong CG cuts
    - pricers to dynamically generated problem variables
    - domain propagators to reduce the variables' domains
    - primal heuristics
          * several diving heuristics, including guided dives
          * two different rounding heuristics
          * Local Branching
          * RINS
          * Octane
    - node selectors to guide the search
    - branching rules to split the problem into subproblems
          * full strong branching
          * inference branching
          * least/most fractional branching
          * pseudo cost branching
          * reliability branching
    - relaxators to incorporate relaxations additional to the LP relaxation (e.g. SDP)
    - presolvers to simplify the solved problem
    - file readers to understand different input file formats
          * MPS format
          * LP format
          * ZIMPL models (needs ZIMPL library)
    - event handlers to get informed each time a node was solved, a specific
      variable changed its bounds, a new solution was found, ...
* every existing unit is implemented as a user extension, leading to an
  interface flexible enough to meet the needs of most additional user extensions
* cut pool management
* arbitrarily many children per node, branching on constraints
* possibility to solve or not to solve the LP relaxation at each single node
* conflict analysis to learn from infeasible subproblems

I would be glad, if you try to implement your own cutting plane separators,
primal heuristics, branching rules, constraint handlers, and so on with the SCIP
framework and send it to me such that I can incorporate the code into the official
version of SCIP.
Although there is only a doxygen documentation, you should be able (with my help)
to implement your code (in C or C++) as plugin for SCIP.


Regards,  Tobias Achterberg


-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany