SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Release notes 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. |
