SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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.