Scippy

SCIP

Solving Constraint Integer Programs

Release notes

Please consult the release report for version 5.0 that explains many of the new features in detail.

Notes for SCIP Release 5.0

Features
========

- SCIP can now automatically detect and exploit symmetries in MIPs

- add new heuristic MPEC that solves a MPEC reformulation of a mixed-binary nonlinear problem by regularized NLP reformulations

- new primal heuristic ALNS that orchestrates eight different LNS heuristics adaptively
  using algorithms for the multi-armed bandit problem

- added analysis of the clique table which identifies possible aggregations via the search for
  strongly connected components and may detect infeasible assignments on the way

- new presolving plugin presol_sparsify that tries to cancel nonzero coefficients in linear constraints by adding
  multiples of linear equalities

- utilizing linear inequalities to compute stronger linearizations for bilinear terms; the inequalities are computed in
  the OBBT propagator

- extended conflict analysis by analyzing dual solutions of boundexceeding LPs

- improved cut post-processing: apply coefficient tightening, enforce maximal dynamism

- added interface to the NLP solver WORHP

- added interface to the NLP solver FilterSQP

- added new plugin type "table" for adding user-defined statistics tables

- added macros to do computations with a higher precision by using double-double arithmetic

- new methods and interactive shell functionality to display linear constraint classification types;
  use SCIPclassifyConstraintTypesLinear() or 'display linclass' after reading a problem to classify linear constraint types

- new numerical solution violations get printed when checksol is called


Performance Improvements
========================

- new implementation of zerohalf separator

- faster implementation of CMIR cut generation heuristic

- improved cut selection and management

- enabled cutting plane separation in the tree

- disabled reformulation of products of a binary variable with a linear term that does not solely involve binary variables

- improved dual ray analysis

- use disjoint set to reduce peak memory usage and time to compute clique table connectedness information

- revised disaggregation of quadratic constraints: the number of created constraints can now be controlled and the
  disaggregated constraints are scaled in order to increase numerical accuracy

- removed bestrelaxsol and directly access relaxation solution instead to decrease overhead when using relaxation handlers

- use LP solution polishing during probing and diving mode to activate it during many primal heuristics; remains disabled
  during strong branching and OBBT

- for fast presolving emphasis, disable use of implications in logicor presolving

- use limit on the total number of nonzeros added to the clique table during the greedyCliqueAlgorithm of cons_knapsack.c

- speed up creation of LP in the computation of relative interior points

- drop events of disabled linear constraints to reduce event processing effort

- improved versions of the clique and variable bound pre-root heuristics that are often able to fix many more variables


Additional Notes
================

- default value for ZIMPL in the Makefile is now "false"

- added compilation flag SYM to specify which graph automorphism package (bliss, none) should be used

- improved Visual Studio compilation with CMake build system

- several new unit tests

- Many bug fixes, see CHANGELOG

A release report with an in-depth description of many of the new features in version 4.0 is available on Optimization Online.

Notes for SCIP Release 4.0.1

Features
========

- New option in the interactive shell to validate the solution against an
  external primal and dual reference value

- Updated and new interfaces to Mosek, GAMS, Gurobi and Glop (Google OR tools)

- New parsing functionality for cardinality constraint handler in CIP format


Performance Improvements
========================

- Performance improvements mainly for nonlinear components


Additional Notes
================

- New CMake build system alongside the usual Makefile setup

- Many bug fixes, see CHANGELOG
Notes for SCIP Release 4.0

Features
========

- Introduced support for partial or infeasible user solutions, which SCIP tries to complete/repair heuristically

- Many improvements and new example code for custom relaxation handlers

- Improved conflict analysis through central conflict pool and dual ray analysis for primal infeasible LPs

- New solution polishing to improve integrality of LP solutions

- New Concurrent solving mode to launch several SCIPs with different settings in parallel

- Added adaptive solving behavior of SCIP based on solving phases and heuristic transitions

- New constraint handlers cardinality and components

- New primal heuristics GINS, LP face, Complete Sol, Locks, Repair, and Multistart

- Revised pseudo random number generation and introduced central random seed for all plugins

- New presolvers that disaggregate SOC constraints and reformulate QP's by adding KKT conditions

- New presolving step for variables contained in a single quadratic constraint with proper square coefficients

- New separators for gauge cuts, convex projection cuts and perspective cuts for indicator constraints

- New propagator for OBBT on convex NLP relaxation

- Extended statistic output displayable via the interactive shell

- Additional I/O-functionalities for debugging and logging in SCIP and in the AMPL interface

- Added new debug output function SCIPdebugMsg that outputs the sub-SCIP level; now used within SCIP


Performance Improvements
========================

- Improved tuning of propagation and heuristic timings

- Constraint compression reduces memory usage in problem copies used inside primal heuristics

- Linear time methods for (weighted) median selection and inplace partitioning of joint arrays of various types, used for knapsack approximation algorithms

- Improved greedy knapsack solution for the flow cover separation

- Connectedness of the clique table for faster and better clique partitioning

- Extended the presolving timings by an additional timing FINAL for self-contained reductions

- Improved and extended stuffing inside of linear constraint handler

- Tuned propagation methods of several constraint handlers and the absolute-value expression

- Changed handling of coupling constraints in cons_indicator

- Clique separator always constructs a dense clique table, which proved to be faster on several MIP benchmarks

- 1-opt heuristic is iterated as long as new incumbents are found

- Randomized tie-breaking in different parts of the code to reduce performance variability


Additional Notes
================

- Improved build system, separate directories for shared and static libraries

- New makefile targets LINKCCSCIPALL and LINKCXXSCIPALL to link all SCIP components into an external project

- Add make help command to list all parameters of the SCIP makefile

- SCIP uses the lpi_spx2 interface by default

- Interfaces for Python and Java are, among others, now available via http://www.github.com/scip-interfaces

- Improved Gurobi interface that can handle ranged rows (requires Gurobi >= 7.0.2)

- New unit testing system built on the Criterion framework

- Revised documentation of the SCIP C-API to group methods more comprehensively by topics

- Many bug fixes, see CHANGELOG

Please consult the release report for version 3.2 that explains many of the new features in detail.

Notes for SCIP Release 3.2.1


Interface Changes
=================

- SCIPsolveLinearProb now uses a 1-dimensional matrix representation

- renamed MIP matrix structure to SCIP_MATRIX

- changed the numeric values for PRESOLTIMING flags

Features
========

- significantly improved Python interface to support user callbacks
  as well as linear and quadratic expressions

- new interactive shell command "write history" to write the command line history
  (only when compiled with Readline)

- several improvements of SCIP-Jack (STP application)

- several improvements of PolySCIP (former MultiObjective application)

- improved disjunctive cut separator by the 'monoidal cut strengthening'
  procedure of Balas and Jeroslow

Bug Fixes
=========

- handle cutoffs in cons_indicator detected by infeasible inequalities

- fixed wrong objective sense when copying the original problem

- (root) reduced cost propagators are not run anymore when doing branch-and-price,
  since they may install upper bounds on variables which might interfere with the
  pricing (they may be enabled again by their force parameters)

- fixed some problems using reoptimization on infeasible instances or
  instances solved in presolving

- fixed library problems on Windows operating systems

- many small bug fixes, see CHANGELOG
Notes for SCIP Release 3.2


Features
========

- added reoptimization feature for optimization problems with changed objective function or tighter feasible region

- new primal heuristics distribution diving, indicator, bound

- improved clique and variable bound heuristics

- new branching rules distribution, multaggr and a new rule for SOS1 constraints

- new separator eccuts

- new presolvers tworowbnd, dualagg, implfree, redvub, stuffing

- added presolving levels (FAST, MEDIUM, and EXHAUSTIVE) to allow better balancing of presolvers

- generalized upgrade from (SOC-representable) quadratic constraints to SOC constraints

- extended probing mode to allow separation and objective coefficient changes

- transfer of history information from and to sub-SCIPs

- new reliability notions in hybrid reliability pseudo cost branching

- started support for user-defined operators in expression trees/graphs

- added matrix module for getting access to the internal mixed inter linear problem matrix

- two new applications for multi-objective optimization (PolySCIP) and the Steiner Tree Problem in Graphs

- added output information for BAK: Branch-and-bound Analysis Kit


Performance Improvements and Bug Fixes
======================================

- decreasing total memory usage of SCIP by using more buffer data structures

- adjust diving heuristics to solve fewer LPs

- improved vartype upgradability from continuous to implicit variables

- using sparsity information of the SoPlex LP

- new presolving/propagation algorithm using the gcd for ranged rows and equations in cons_linear

- improved treatment of nonlinearities in hybrid reliability pseudo cost branching

- improved propagation of SOS1 constraint handler using the information from a conflict graph

- improved separation procedure of SOS1 constraint handler

- improved separation procedure for convex quadratic constraints

- better presolving coordination by presolving levels

- and many bug fixes, see CHANGELOG


Additional Notes
================

- moved some examples to an application directory

- original problem can now be permuted directly after reading

- better handling of large values returned by the LP solver

- extended statistic output of interactive shell
Notes for SCIP Release 3.1


Features
========

- new primal heuristics random rounding, proximity, and dual value

- new branching rule cloud branching

- added support for strong branching with domain propagation in full strong and
  reliability pseudo cost branching

- new node selectors breadthfirst and uct

- computation of primal-dual integral

- added possibility to add objective offset to original problem

- the original problem can now be copied

- upgrading can now be disabled for single linear constraints

- the rank of cuts is now stored and taken into account to improve numerical stability

- dual solution values can now be obtained in the interactive shell after solving a pure
  LP without presolving

- extended test scripts by statistical tests


Interfaces
==========

- new SoPlex 2.0 interface, can be enabled with LPS=spx2

- beta version of a python interface

- beta version of a Java native interface

- added copy of GAMS interface from COIN-OR/GAMSlinks project;
  GAMS-reader in SCIP can now read model instances from .gms files

- moved LP interfaces to separate directory src/lpi


Performance Improvements and Bug Fixes
======================================

- major improvements in pseudo-boolean constraint handler

- many presolving improvements in constraint handlers

- performance improvement in domain propagation by marking constraints for propagation

- dual fixing presolver was turned into a propagator

- added more constraint upgrading possibilities

- allow multiaggregation of binary variables

- strong branching LP solutions are checked for integrality

- improved handling of initial constraints created during solving

- improved LP reoptimization for branch-and-price applications

- improved numerical stability checks for LP solution

- disabled scaling in feasibility check of nonlinear constraint handlers

- and many bug fixes, see CHANGELOG


Additional Notes
================

- new SCIP Optimization Suite homepages

- new textbook Gomory mixed integer cuts example

- very few interface changes, see CHANGELOG
Notes for SCIP Release 3.0.2


Interface Changes
=================

- removed problematic function SCIPsetSlackVarIndicator() from cons_indicator


Features
========

- can now output the solutions in the solution pool in the interactive shell

- updated Mosek LP interface to compile with Mosek 7

- display some syntax errors when reading erroneous CIP files

- cons_xor now uses the integral variable in propagation

- added methods SCIPmarkColNotRemovableLocal() and SCIPmarkRowNotRemovableLocal()
  to forbid removal of a column/row from the LP in the current node


Bug Fixes
=========

- fixed bug in cons_integral: check integrality of implicit integer variables when
  a solution is checked for feasibility

- fixed bugs in parsing bounds from CIP-files, in reader_gms, and AMPL interface

- fixed bugs with freeing C++ object data for problem and variables

- fixed bugs in solution counting

- forbid branching on variables with huge bounds

- unlinking a solution now copies values smaller than SCIPepsilon() to avoid that
  feasible solutions in the transformed problem become infeasible in the original
  problem

- many small bug fixes, see CHANGELOG
Notes for SCIP Release 3.0.1


Interfaces
==========

- new method SCIPgetNLimSolsFound() to get number of solutions that
  respect the objective limit

- when using an objective limit, heuristic characters are not
  displayed any longer for worse solutions


Features
========

- added delayed cutpool which only gets separated if the sepastore is
  empty after a separation round


Performance Improvements and Bug Fixes
======================================

- better handling of generalized (Lagrangian) variable bounds

- fixed several issues in cumulative constraint handler

- fixed bug which caused deletion of ranged rows parallel to objective

- fixed several numeric issues

- fixed bug with LP not being flushed after bound changes on columns
  that are not in the LPI

- fixed inconsistent behavior of methods
  SCIPlpiIs{PrimalFeasible,DualFeasible,Optimal,...}

- fixed bug in copying nonlinear constraints during presolve (resulted
  in wrongly declaring instances as infeasible when using component
  presolve)

- fixed bug in CppAD in connection with abspower constraints

- many small bug fixes, see CHANGELOG
Notes for SCIP Release 3.0


Features
========

- new presolvers convertinttobin, components, domcol, gateextraction

- new primal heuristics nlpdiving and zeroobj

- new constraint handler superindicator for indicators on arbitrary constraints

- new shell command "change minuc" to minimize the number of unsatisfied constraints

- new propagators obbt and genvbounds for MINLP

- new reader for OSiL files

- extended vbounds propagator to cliques and implications

- GUB cover cuts

- better handling of memory limits, in particular for large problems

- parameters can now be fixed

- new statistics and new statistic output messages

- full version of cumulative constraint handler


Interfaces
==========

- new AMPL interface

- beta version of a functional MATLAB interface

- introduced basic inclusion and creation methods to simplify usage of the SCIP library


Performance Improvements and Bug Fixes
======================================

- improved scaling of linear constraints

- reworked probing algorithm

- improved reading time

- better handling of numerical tolerances for LP solver

- several performance improvements for Pseudo-Boolean optimization

- many bug fixes


Additional Notes
================

- first release of GCG, a generic branch-cut-and-price solver built on top of SCIP

- first release of UG, a framework for solving mixed integer programs, mixed integer
  nonlinear programs, and constraint integer programs in parallel

- new examples for scheduling and usage of the callable library with nonlinear problems

- new SCIP T-shirts

- renamed ZIB Optimization Suite to SCIP Optimization Suite
Notes for SCIP Release 2.1.1


Interfaces
==========

- changed parameter <propagating/pseudoobj/maxcands> to
  <propagating/pseudoobj/minuseless> (see prop_pseudoobj.c) due to revision
  of the pseudo objective propagator

- added parameter <heuristics/undercover/fixingorder>

Performance Improvements and Bug Fixes
======================================

- revised pseudo objective propagator 

- improvements in undercover heuristic

- fixed numeric issue in aggregations

- fixed compilation issues with negate() function in intervalarith.c on
  exotic platforms

- fixed handling of unbounded solutions, including double-checking their
  feasibility and that the primal ray is a valid unboundedness proof and
  reoptimizing the LP with modified settings if the solution is not
  feasible

- several other bug fixes see CHANGELOG
Notes for SCIP Release 2.1


Features
========

- Major extensions for nonlinear CIP
  + New constraint handlers for nonlinear equations with algebraic expressions (only Beta),
    absolute power constraints, and bivariate nonlinear constraints (only Beta)
  + New expression graph data structure for domain propagation and reformulation
  + Simple convexity check and simplification for expression trees and graphs
  + New option for n-ary branching on nonlinear variables (within pseudocost branching rule)
  + New interval arithmetic functions for bivariate quadratic expressions

- New funtionalities in the interactive shell (modify current CIP instance, write NLP relaxation)

- In branch-and-price algorithms, created variables can now be deleted (beta version)

- New constraint handlers for pseudoboolean and disjunction constraints (both beta)

- New original solution storage capability, which allows transfering solutions between SCIP runs

- New separator for close cuts and a new function to compute relative interior points of the LP

- Propagators are now also called in node presolving

- Extended support of lazy bounds

- New targets "(un)install" in Makefile, support for valgrind in testing environment

- New scripts for running tests with GAMS


Interfaces
==========

- Improved SOPLEX interface (LP simplifier)

- Improved CPLEX interface, including measures for numerical stability

- New reader for (standard) bounds on variables 

- Improved support for wbo format for weighted PBO problems, IBM's xml-solution
  format, and pip and zimpl format for polynomial mixed-integer programs

- Extended reader for Flatzinc models to handle cumulative constraints

- Extended reader for CIP models to handle various new constraints, including all types of linear constraints

- Extended writer for GAMS and pip format to write more types of nonlinear constraints


Performance Improvements and Bug Fixes
======================================

- Improved LNS and undercover heuristics

- Improved knapsack cover cuts 

- Reorganized filtering process of separation storage (allows adding cuts for different solutions)

- Improved presolving for various constraint handlers

- Improved propagation methods for variable bound constraints

- Improved performance for quadratic constraints

- More robust sorting functions 

- Many bug fixes


Additional Notes
================

- The display of statistics for presolvers, propagators, constraints and LP
  solving has changed. For details see the CHANGELOG file.

- The interface contains several additional callback functions and
  parameters for plugins. Some effort may be required to compile your old
  projects with SCIP 2.1. For details see section "Changes between version
  2.0 and 2.1" in the doxygen documentation. See also the CHANGELOG file
  for additional information.

- Linking against Clp and Ipopt has been simplified. Only the directory where the
  package has been installed need to be provided now. For details see the INSTALL file.

- The check scripts expect *.test and *.solu files now in the directory check/testset.
Notes for SCIP Release 2.0.2

Performance Improvements
========================

- knapsack constraints are now propagated and separated faster;
  SCIPsolveKnapsackExactly() now works faster and requires less memory

- reduced memory usage of shift-and-propagate heuristic

- improved twoopt-heuristic by considering larger search domains

- the SoPlex interface now has the capability to provide a primal ray,
  provided it is compiled against the next SoPlex release (>= 1.5.0.2)


See the CHANGELOG file for a list of bugfixes.
Notes for SCIP Release 2.0.1


Interfaces
==========

- allow access of transformed constraints in SCIP_STAGE_TRANSFORMED

- replaced parameter <constraints/quadratic/minefficacy> by
  <constraints/quadratic/minefficacysepa> and
  <constraints/quadratic/minefficacyenfo>

- added possible values 'a' and 'e' for <constraints/soc/nlpform> to enable
  automatic choice and convex exponential-sqrt form for SOC constraint
  representation in NLP

Performance Improvements and Bug Fixes
======================================

- SCIP with SoPlex as LP solver now uses auto pricing by default (start
  with devex, switch to steepest edge after some iterations); this fixes
  timeouts on instances where devex converges very slowly

- fixing lifting of new knapsack items which are negated items of already
  included items, this could lead to very long presolving

- fixed performance issue in presolving w.r.t. to computing the number of
  new fixings, aggregated, and so on before a constraint handler presolver
  is called

- in case of adding constraints during pricing with initial flag set to
  TRUE, we add now these constraints after the pricing round to the LP

- changed parameter values in clique separator in order to avoid very large
  branch-and-bound trees

Notes for SCIP Release 2.0


Features
========

- SCIP can now copy instances (e.g. for heuristics)

- New rounding and propagation heuristics, rapid learning

- Added the feasibility pump to 2.0

- New constraint handlers for linking constraints (only Beta), cumulative constraints,
  and for breaking orbitopal symmetries

- New separators for oddcycle cuts and Chvatal-Gomory cuts using sub-MIPs

- New propagator for variable bounds

- Solution counting extended to constraint integer programs, this also
  includes constraint integer programs which contain continuous variables

- External branching candidates (of interest if a relaxator or constraint
  handler wants to provide branching candidates)

- New branch-and-price example which includes Ryan/Foster branching (binpacking example)

- New example illustrating the use of an event handler (example/Eventhdlr)

- More support for nonlinear CIPs:
  + Improved constraint handler for quadratic constraints
  + New constraint handler for second order cone constraints
  + New MINLP heuristics (undercover, subnlp)
  + Preliminary support for non-linear relaxations (via expression trees)
  + Automatic branching on solutions from arbitrary relaxations and on continuous variables


Interfaces
==========

- Improved SoPlex interface

- Improved Xpress interface

- Improved CPLEX interface

- NLP solver interface (NLPI) now independent of SCIP like LPI

- Enhanced user interface for callable library: manual restarts,
  predefined settings, and many other features

- Support of wbo format for weighted PBO problems, IBM's xml-solution
  format, and pip format for polynomial mixed-integer programs

- Extended reader for Flatzinc models

- Extended reader for .lp and .mps files for semicontinuous variables
  and quadratic objective or constraints


Performance Improvements and Bug Fixes
======================================

- Several improvements in presolving

- Enhanced handling of indicator constraints

- Improved zerohalf cuts

- Many bug fixes


Additional Notes
================

- A bug in the Makefiles of older versions of the SCIP examples may cause
  data loss. If you have a custom Makefile, please ensure that the target
  "clean" is changed as described here:
  http://scip.zib.de/download/bugfixes/scip-1.2.0/make.txt.

- The additional NLPI library requires a change in the Makefile of SCIP's project:
  The $(MAINFILE) target now has $(NLPILIBFILE) as additional dependency and the linking
  command requires $(LINKCXX_l)$(NLPILIB)$(LINKLIBSUFFIX) as additional argument.

- The interface contains several additional callback functions and
  parameters for plugins. Some effort may be required to compile your
  own projects with SCIP 2.0. For details see the CHANGELOG file. See
  also "Changes between version 1.2 and 2.0" in the doxygen
  documentation for additional information.
Notes for SCIP Release 1.2


Features
========

- Preliminary support of non-convex MIQCPs: Constraint handler for
  quadratic constraints, NLP heuristic, and Ipopt interface

- Improved support of branch-and-price: SCIP now supports lazy bounds, early 
  branching/incomplete pricing, and primal heuristics during pricing loop

- Constraint handler for indicator constraints and parsing them from *.lp
  and *.zpl files

- Heuristics which are applied before root LP

- Black-box lexicographic dual simplex algorithm

- Copy constructors and i/o functionality for constraints


Interfaces
==========

- First version of LP interfaces to Gurobi and QSopt

- Major performance improvements in LP interfaces to Clp, Mosek, and SoPlex

- Reader for Flatzinc and GAMS models

- Adjusted interface to Zimpl version 3.0.0

- On http://code.google.com/p/python-zibopt/source/checkout you find a beta 
  version of a python interface to SCIP implemented by Ryan J. O'Neil.
  

Performance Improvements and Bug Fixes
======================================

- Enhanced MCF cuts: stable version, used by default

- Improved hybrid branching

- Increased numerical stability for Big M formulations

- Several improvements in presolving

- Many bug fixes


For details see the CHANGELOG file. Some of the interface functions
were changed. See "Changes between version 1.1 and 1.2" in the doxygen
documentation for additional information.
Notes for SCIP Release 1.1


General
=======

- Extended the capabilities of SCIP to output problems in different
  formats (LP, MPS, CIP, ...). You can output the original and
  transformed problem. Furthermore, generic names can be given to the
  variables and constraints.

- New constraint handlers for SOS type 1 and 2 constraints.

- There is a new file make/make.projects supporting the compilation of
  projects using SCIP.

- SCIP can now count integer feasible solutions for IPs/CIPs (without
  continuous variables).

- The feasibility test for solutions at the end of the execution now
  outputs more useful information. This made some changes in the
  interface of constraint handlers necessary.

- Added an example for the graph coloring problem, showing the usage
  of column generation.

- Pseudo-Boolean problems can be read and handled by SCIP.

- New heuristic DINS.

- New cutting plane separator MCF (beta version).


Performance Improvements and Bug Fixes
======================================

- Improved sorting functions. They now use quick-sort/shell-sort
  depending on the size.

- The preprocessing has been revised. It now applies bound
  computations in a numerically more stable way. The pairwise
  comparison of linear, logicor, and setppc constraints has been
  improved.

- The timing calls have been reworked.

- The LP-interfaces to Clp and SoPlex have been revised and adapted
  to the changes in these solvers.

- Many internal performance improvements.

- Many internal bug fixes.


For details see the CHANGELOG file. Some of the interface functions
were changed. See "Changes between version 1.0 and 1.1" in the doxygen
documentation for more information.