Scippy

SCIP

Solving Constraint Integer Programs

Release notes for SCIP 0.8

SCIP 0.8.2

Features

  • additional flag delay for pricers
  • new propagator rootredcost which applies reduced cost fixing at the root node whenever a best new primal solution was found
  • new separator redcost which replaces the internal reduced cost strengthening
  • LP:
    • extensions to the LP are kept even if the LP is not solved at the current node; however, if the LP turned out to be numerically instable, the extensions of the current node are still discarded
    • added removal of bound-redundant rows from the LP during root node LP solving loop
    • new display column lpobj
  • Constraints:
    • slightly changed priorities of constraint handlers
    • now, conflict constraints are also created if they were generated in strong branching or diving with insertion depth equal to the current depth
    • new constraint handler bounddisjunction
  • Readers:
    • renamed sol file reader to fix file reader (reads partial solution files and fixes variables to the given values)
    • added sol file reader which reads complete solution files and adds the solutions to the solution pool
    • LP and MPS file readers are now able to parse lazy constraints and user cuts sections
  • Presolver:
    • knapsack presolver now generates cliques in the clique table (this essentially solves neos1.mps)
    • new presolver inttobinary
  • Heuristics:
    • new primal heuristic shifting
    • diving heuristics abort earlier (did not come back in reasonable time on fast0507)

Interface changes

  • new solution status code SCIP_STATUS_STALLNODELIMIT

New and changed callbacks

  • slightly modified semantics of the CONSINITLP callback in the constraint handlers

Deleted and changed API methods

New API functions

Command line interface

  • command line syntax changed to support batch modus without piping stdin with < or | operators
  • advanced command line syntax:
    • -l <logfile>: copy output into log file
    • -q: suppress screen messages
    • -s <settings>: load parameter settings (.set) file
    • -f <problem>: load and solve problem file
    • -b <batchfile>: load and execute dialog command batch file (can be used multiple times)
    • -c <command>: execute single line of dialog commands (can be used multiple times)

Interfaces to external software

Changed parameters

  • removed parameter propagating/redcostfreq, because reduced cost strengthening is now an external separator plugin
  • removed parameter conflict/maxunfixed
  • parameter conflict/maxclauses renamed to conflict/maxconss
  • parameter conflict/interclauses renamed to conflict/interconss
  • parameter conflict/reconvclauses replaced by conflict/reconvlevels
  • parameter conflict/uselp replaced by conflict/useinflp and conflict/useboundlp
  • changed default value of constraints/obsoleteage to -1
  • changed default value of branching/relpscost/conflictweight to 0.01
  • changed default value of branching/relpscost/inferenceweight to 0.0001
  • changed default value of branching/relpscost/cutoffweight to 0.0001
  • in bfs node selector, parameter minplungedepth is now stronger than maxplungedepth if they conflict

New parameters

  • constraints/linear/separateall
  • conflict/lpiterations
  • conflict/keepreprop
  • branching/relpscost/conflictweight, branching/relpscost/inferenceweight, branching/relpscost/cutoffweight and branching/relpscost/pscostweight
  • conflict/settlelocal
  • conflict/depthscorefac
  • limits/stallnodes

Build system

Makefile

  • removed ncurses and pthread libraries from the Makefile; pthread is now only linked if CPLEX is used

Fixed bugs

  • fixed numerical bug in SCIPrealToRational() [thanks to Anders Schack-Nielsen]
  • fixed bug in crossover heuristic with negative timelimit
  • removed bug in conflict analysis with wrong redundancy check
  • fixed bug that unexpected end of stdin (Ctrl-D or piped-in file without quit command) gives a segmentation fault
  • fixed bug with inconsistent data structures after a global bound was changed at a local subproblem and the local bounds are not contained anymore in the new global bounds
  • fixed dependency generation in example Makefiles
  • Knapsack:
    • fixed bug in knapsack presolving with redundancy check after applyFixings() [thanks to Anders Schack-Nielsen]
    • fixed bug in knapsack separator with empty initial covers
    • fixed bug in knapsack constraint disaggregation that may lead to acceptance of infeasible solutions
    • fixed bug in knapsack constraint handler where a modifiable constraint may be declared redundant
  • LP:
    • fixed bug with missing LP size updates after pricing or cut separation in probing [thanks to Marc Nuenkesser]
    • fixed bug in CPLEX interface with getting basis information after the LP was modified and restored
    • fixed bug with updating LP size in probing
    • fixed bug that SCIPgetLPSolstat() returns a valid status code even if the LP was not yet constructed for the current node
  • Variables:
    • fixed bug with invalid lazy updates after a restart where the LP is not solved again (e.g., due to all variables being fixed)
    • fixed bugs resulting from inactive general integer variables being member of the variable bounds array of a variable
    • fixed bug in updatePseudocost() with wrong lpgain distribution on multiple branching variables [thanks to Anders Schack-Nielsen]
    • fixed bug in objconshdlr.h where member variable scip_maxprerounds_ was declared as an SCIP_Bool instead of an int
    • branching on nearly-integral variables is now avoided in relpscost branching, which lead to a numerical assertion
  • Implication:
    • fixed bug with adding implications that fix the implication variable to the opposite value (due to the bug, it was returned that the whole problem is infeasible)
    • removed wrong assert in varRemoveImplicsVbs()
  • Cliques:
  • Readers:
    • fixed bug in MPS file reader with OBJSENSE
    • fixed bug in LP reader with potentially uninitialized pointers [thanks to Martin Mueller]
  • Constraints:
    • it is now possible to branch on constraints without the risk of going into an infinite loop, because constraints marked as initial will be put to the LP relaxation (of the child nodes) even if separation is prohibited by the parameter settings
    • fixed bug that locally valid varbound constraints produce VLB/VUB entries [thanks to Anders Schack-Nielsen]

SCIP 0.8.1

Features

  • improved performance of the priority queue in conflict analysis
  • slightly modified restartdfs node selector
  • Presolving:
    • new presolver implics to find bound changes and aggregations out of the implication graph
    • modified probing order in probing presolver
  • Constraints:
    • changed handling of added constraints in separation calls
    • modified bookkeeping of locally added and disabled constraints such that the order of enabling and disabling constraints stays the same
    • logic or constraint handler now adds implications on clauses with 2 literals to the implication graph
    • and/or constraint handlers now add implications to the implication graph
    • xor constraint handler now uses stronger LP relaxation without auxiliary variable for xor constraint with 2 operands
  • Heuristics:
    • added preliminary version of intdiving heuristic (disabled in default settings)
    • added crossover heuristic
  • Readers:
    • LP file reader now accepts the keyword Integer for defining the start of the integer variables section
    • new file reader for (partial) solutions

Examples and applications

  • added two small pricer examples (for C and C++)
  • updated example code (s.t. it compiles again)

Interface changes

New and changed callbacks

  • callback method CONSSEPA of constraint handler was split into two methods CONSSEPALP and CONSSEPASOL
  • callback method SEPAEXEC of separator was split into two methods SEPAEXECLP and SEPAEXECSOL

Deleted and changed API methods

New API functions

Command line interface

  • added write statistics command to default user dialogs

Changed parameters

  • modified meaning of parameter presolving/probing/maxtotaluseless
  • heuristics with freq = 0 and freqofs > 0 are now called in depth level freqofs instead of being called in the root node
  • added some parameters in local branching and RINS heuristic
  • new parameter values primal simplex and dual simplex in lp/initalgorithm and lp/resolvealgorithm

New parameters

  • branching/inference/conflictweight

Build system

Makefile

  • included version number in binary file name
  • tried to make the code Windows compatible

Fixed bugs

  • also removed history_length, if NO_REMOVE_HISTORY is defined to support older versions of the readline library
  • hopefully fixed bug with wrong path slash / under Windows
  • fixed bug with aggregating fixed variables
  • Implications:
    • fixed bug in transitive implication addition
    • fixed wrong assert with implications that imply a fixed variable
    • removed bug in implication addition
  • Readers:
    • fixed bug in ZIMPL model reader with wrong chdir, if .zpl file is in current directory
    • fixed bug in LP file reader with signed values without space between sign and value (e.g. +2x instead of + 2x)
    • fixed various bugs in LP file reader
    • fixed bug in LP file reader with explicit zero coefficients
  • Numerics:
    • fixed numerics in probing and linear constraint handler (rentacar was detected to be infeasible in presolving)
    • fixed numerics in check method of linear constraint handler
    • fixed bug with numerical error in LP resolve after probing or diving
  • Heuristics:
    • fixed bug with calling heuristics in depths smaller than their frequency offset
    • fixed bugs in local branching and RINS heuristic

Known bugs

  • if one uses column generation and restarts, a solution that contains variables that are only present in the transformed problem (i.e., variables that were generated by a pricer) is not pulled back into the original space correctly, since the priced variables have no original counterpart

SCIP 0.8.0

Features

  • adding variable bounds automatically adds the corresponding implication
  • changed restart dfs nodeselector to sort leaves by node number instead of node depth to aviod jumping around in the search tree after a restart was applied and the current dive ended due to infeasibility
  • new Message Handler plugin
  • added file reader for LP format
  • introduced subversion string
  • replaced all abort() calls by SCIPABORT(); this is defined in def.h to be assert(FALSE)
  • added possibility to disable certain features by using make USRFLAGS=-DNO_REMOVE_HISTORY, make USRFLAGS=-DNO_SIGACTION, make USRFLAGS=-DNO_RAND_R, or make USRFLAGS=-DNO_STRTOK_R
  • improved preprocessing abort criteria
  • added zlib support
  • Conflict Analysis:
    • conflict clauses are now collected in a conflict store, redundant clauses are eliminated and only the best conflict/maxclauses clauses are added permanently to the problem; the remaining clauses are only added temporarily, if they can be used for repropagation
    • modified the influence of the depth level in conflict analysis
    • slightly changed LP resolving loop in conflict analysis
    • if CPLEX returns that the LP exceeds the bound and if no additional LP solves are allowed in conflict analysis, we have to perform one additional simplex iteration to get the dual solution that actually violates the objective limit
  • Constraints:
    • reactivated multiaggregation in cons_linear.c on binary variables again (possible due to bug fix below)
    • improved preprocessing of variable bounds constraints
    • linear constraint handler now catches events of variables after the problem was completely transformed in order to avoid the whole bunch of LOCKSCHANGED events that are generated at problem transformation stage
    • added redundancy detection for pairs of constraints in setppc constraint handler
  • Presolving and Cliques:
    • changed linear constraint presolving s.t. redundant sides are not removed if constraint is an equality
    • new event type SCIP_EVENTTYPE_PRESOLVEROUND
    • modified probing presolver to not add implications that are already included in the implication graph and clique table
    • incorporated clique and implication information in knapsack constraint presolving
    • removed transitive clique generation, because this produces way too many cliques
  • Heuristics:
    • diving heuristics now apply propagation at each step
    • removed objfeaspump heuristic, because the functionality can be achieved by using the feaspump heuristic
    • diving heuristics are now applying propagation after each bound change
    • new primal heuristic octane
    • slightly changed feaspump heuristic, s.t. after finding a new best solution the target integral solution is modified randomly
  • Separation and Cuts:
    • improved debugging for infeasible cuts and propagations, given a primal feasible solution
    • improved knapsack cover separation
    • improved performance of c-MIR separator
    • cut pool is now also separated in root node (to find cuts again that were removed from the LP due to aging)

Interface changes

  • new event type SCIP_EVENTTYPE_VARDELETED
  • new event SCIP_EVENTTYPE_IMPLADDED
  • new event types SCIP_EVENTTYPE_GLBCHANGED and SCIP_EVENTTYPE_GUBCHANGED

New and changed callbacks

  • new callback parameter validnode for the CONFLICTEXEC method of conflict handlers, which should be passed to SCIPaddConsNode()

Deleted and changed API methods

New API functions

Command line interface

  • added command write solution to default dialog
  • added commands write problem and write transproblem to default dialog

Changed parameters

  • additional setting SCIP_VERBLEVEL_DIALOG in display/verblevel parameter
  • additional LP pricing setting partial
  • replaced parameter presolving/restartbdchgs with parameters presolving/maxrestarts and presolving/restartfac
  • replaced parameter constraints/linear/maxpresolaggrrounds with constraints/linear/maxpresolpairrounds
  • parameters constraints/agelimit and constraints/obsoleteage now iterprete the value 0 as a dynamic setting
  • number of fractional variables included in parameter separating/maxstallrounds
  • Changed default values:
    • changed default values of heuristics/∗/maxdiveavgquot and heuristics/∗/maxdiveavgquotnosol to 0
    • changed default values of constraints/agelimit and constraints/obsoleteage to 0
    • changed default values of heuristics/objpscostdiving/maxsols and heuristics/rootsoldiving/maxsols to -1
    • changed default value of separating/strongcg/maxroundsroot to 20
    • changed default value of separating/cmir/maxroundsroot to 10
    • changed default value of constraints/linear/maxaggrnormscale to 0.0, which means to not apply aggregation
    • changed default value of separating/maxstallrounds to 5
    • changed default value of presolving/probing/maxfixings to 50
    • changed default parameter values to MIP settings:
      • conflict/useprop = FALSE
      • conflict/usepseudo = FALSE
      • display/verblevel = 4
      • separating/poolfreq = 0
      • constraints/linear/sepafreq = 0
      • constraints/and/sepafreq = 0
      • constraints/conjunction/sepafreq = 0
      • constraints/knapsack/sepafreq = 0
      • constraints/knapsack/sepacardfreq = 0
      • constraints/logicor/sepafreq = 0
      • constraints/or/sepafreq = 0
      • constraints/setppc/sepafreq = 0
      • constraints/varbound/sepafreq = 0
      • constraints/xor/sepafreq = 0
      • separating/clique/freq = 0
      • separating/cmir/freq = 0
      • separating/gomory/freq = 0
      • separating/impliedbounds/freq = 0
      • separating/strongcg/freq = 0

New parameters

  • branching/fullstrong/reevalage
  • conflict/maxclauses
  • conflict/allowlocal
  • constraints/knapsack/disaggregation
  • presolving/probing/maxtotaluseless
  • separating/cmir/maxfails, separating/cmir/maxfailsroot and separating/cmir/trynegscaling

Data structures

  • MAJOR CHANGE: preceeded all data types with SCIP_: you may use shell script reptypes_scip.sh to rename the SCIP data types in your own source code (But use with care! Create a backup copy of your source first!)

Build system

Makefile

  • modified the Makefile to accept an additional parameter VERBOSE={true,false}
  • added flags READLINE=true/false, ZLIB=true/false, ZIMPL=true/false to Makefile

Fixed bugs

  • fixed minor bugs in debug code of primal.c and sol.c
  • variables that are being multiaggregated are now automatically removed from all other variables' variable bound and implication arrays; this fixes bugs with methods, that rely on the fact, that the entries in the variable bound and implication arrays are active variables only
  • aggregations are now always performed in a way, such that the variable of more general type is aggregated (with type generality being cont > implint > int > bin); in this way, a binary variable's representant is always binary (which was not the case before and resulted in a bug in SCIPgetBinvarRepresentative())
  • removed bug in presol_probing.c: the vars of the sorted variables array have to be captured
  • fixed bug in the output of solutions with priced variables
  • fixed bug in propagation with parameters prop_maxrounds and prop_maxroundsroot
  • conflict analysis can now handle errors in LP solving calls
  • removed bug in SCIPvarAddVlb() and SCIPvarAddVub() with fractional vlb/vubcoefs
  • fixed bug that primal or dual rays might not be available because the wrong solver was used
  • included message.o in LPI library, s.t. one can link this library indepentent of SCIP
  • fixed bug that if diving heuristic that changes the objective values finds a solution, the cutoff is reinstalled in the LP solver (although the objective value has no meaning due to the objective function modification)
  • Feasibiltiy:
    • LP primal feasibility for bounds is now defined as absolute measure (was relative to the bound before); this fixes a bug (see alu8_9.mps), that an LP with an integral variable fixed to a large value yields an accepted solution with that variable slightly different than the fixed value; the integrality feasibility condition is measured with absolute differences, which leads to the fixed integer variable being fractional; this leads to an error if branching is performed on this variable
    • fixed bug with redundant self implications that wrongly lead to the detection of infeasibility
    • fixed bug with potential infinite loop if a separator is delayed and the LP is infeasible
  • Asserts:
  • Numerics:
    • locally fixed variables are no longer used as branching candidates even if their LP solution value is fractional (due to numerical reasons, see above)
    • fixed numerical bug in pseudo objective propagator with only slightly tightened bounds
    • removed bug that an LP might be declared to be solved even if it was marked erroneous due to numerical problems
  • Constraint Handlers:
    • fixed bug in linear constraint handler with variables fixed to infinity
    • fixed bug with constraint handlers that can only enforce their constraints by adding cuts, but the maximal number of cuts to separate is set to 0; now, cuts that are generated in the constraint enforcement are used in any case
    • fixed bug in knapsack constraint presolving with tightening coefficients and capacity
    • fixed bug with modifiable constraints in linear constraint handler preprocessing
    • fixed bug in linear constraint handler that global activities are not updated after global bound changes
  • Separation and Cuts:
    • global bound changes now lead to the removal of redundant implications (such that the asserts in sepa_implbounds.c are now correct)
    • due to usage of variable bounds, SCIPcalcMIR() may return LOOSE variables in the cut -> modified sepa_cmir.c, sepa_gomory.c and sepa_strongcg.c to use SCIPcreateEmptyRow() and SCIPaddVarsToRow() instead of SCIPcreateRow() which only works for COLs
    • fixed bug in clique separator that reduced performance
    • increased performance of clique separator by allowing only a certain number of zero-weighted fill ins