SCIP 0.8.2

Features

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
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
added removal of bound-redundant rows from the LP during root node LP solving loop
Plugins
- new primal heuristic "shifting"
- new separator "redcost" which replaces the internal reduced cost strengthening
- new propagator "rootredcost" which applies reduced cost fixing at the root node whenever a best new primal solution was found
- new constraint handler "bounddisjunction"
- knapsack presolver now generates cliques in the clique table (this essentially solves neos1.mps)
- LP and MPS file readers are now able to parse lazy constraints and user cuts sections
- diving heuristics abort earlier (did not come back in reasonable time on fast0507)
- 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
- additional flag "delay" for pricers
- new presolver "inttobinary"
- new display column "lpobj"

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

method SCIPgetNConflictClausesFound() renamed to SCIPgetNConflictConssFound()
method SCIPgetNConflictClausesFoundNode() renamed to SCIPgetNConflictConssFoundNode()
method SCIPgetNConflictClausesApplied() renamed to SCIPgetNConflictConssApplied()
methods SCIPisLbBetter() and SCIPisUbBetter() have an additional parameter and slightly different meaning (they now compare the bound improvement relatively to the width of the domain and the bound itself)
marking a constraint to be "initial" now means in addition, that if the constraint is added to a local node it will enter the LP at the time the node is first processed, even if parameters forbid separation at this node
SCIPgetNSols() now returns an int instead of SCIP_Longint
method SCIPreadProb() does not call SCIPfreeTransform() anymore; file readers that want to extend the existing problem must now call SCIPfreeTransform() themselves before modifying the original problem
method SCIPgetBinvarRepresentative() can now also be called in problem creation stage
additional parameter "maxpricerounds" in method SCIPsolveProbingLPWithPricing()
changed name of method SCIPpresolGetNVarTypes() to SCIPpresolGetNChgVarTypes()
changed name of method SCIPconshdlrGetNVarTypes() to SCIPconshdlrGetNChgVarTypes()
method SCIPsplitFilenames() now treats both versions of slashes, '/' and '\', as directory delimiters (under MinGW and CygWin, both are valid; so, we cannot treat file names anymore where the other slash is used as a regular character)

New API functions

SCIPgetRowKnapsack(), SCIPgetRowLinear(), SCIPgetRowLogicor(), SCIPgetRowSetppc(), and SCIPgetRowVarbound() for obtaining the linear relaxation of a corresponding constraint
SCIPgetNVarsAnd() and SCIPgetVarsAnd()
SCIPgetWeightsKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack() and SCIPgetWeightsKnapsack()
SCIPgetNVarsLinear(), SCIPgetVarsLinear() and SCIPgetValsLinear()
SCIPgetNVarsOr() and SCIPgetVarsOr()
SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdvarVarbound(), and SCIPgetVbdcoefVarbound()
SCIPgetNVarsXor() and SCIPgetVarsXor()
SCIPsolveProbingLPWithPricing()
SCIPcolGetMinPrimsol() and SCIPcolGetMaxPrimsol()
SCIPgetColRedcost()
SCIPvarGetRootRedcost()
SCIPgetLPRootObjval(), SCIPgetLPRootColumnObjval() and SCIPgetLPRootLooseObjval()
SCIPchgVarLbRoot() and SCIPchgVarUbRoot()
SCIPinRepropagation()
SCIPgetAvgPseudocostScore(), SCIPgetAvgPseudocostScoreCurrentRun(), SCIPgetAvgConflictScore(), SCIPgetAvgConflictScoreCurrentRun(), SCIPgetAvgInferenceScore(), SCIPgetAvgInferenceScoreCurrentRun(), SCIPgetAvgCutoffScore() and SCIPgetAvgCutoffScoreCurrentRun()
SCIPaddDialogInputLine() and SCIPaddDialogHistoryLine()
SCIPgetFocusDepth()
SCIPtransformProb() to create the transformed problem; enables the user, e.g., to add primal solutions before the presolving begins
SCIPcreateSolCopy()
SCIPareSolsEqual()

Command line interface

command line syntax changed to support batch modus without piping stdin with "<lt;" or "|" operators
advanced command line syntax: -l <lt;logfile>gt; : copy output into log file -q : suppress screen messages -s <lt;settings>gt; : load parameter settings (.set) file -f <lt;problem>gt; : load and solve problem file -b <lt;batchfile>gt;: 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 bug with invalid lazy updates after a restart where the LP is not solved again (e.g., due to all variables being fixed)
fixed bug in MPS file reader with OBJSENSE
fixed numerical bug in SCIPrealToRational() [thanks to Anders Schack-Nielsen]
fixed bug in crossover heuristic with negative timelimit
fixed bugs resulting from inactive general integer variables being member of the variable bounds array of a variable
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 in knapsack constraint disaggregation that may lead to acceptance of infeasible solutions
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 bug in LP reader with potentially uninitialized pointers [thanks to Martin Mueller]
fixed bug in SCIPcliqueSearchVar() [thanks to Anders Schack-Nielsen]
fixed bug in SCIPcliqueAddVar() [thanks to Anders Schack-Nielsen]
fixed bug in updatePseudocost() with wrong lpgain distribution on multiple branching variables [thanks to Anders Schack-Nielsen]
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 with missing LP size updates after pricing or cut separation in probing [thanks to Marc Nuenkesser]
fixed bug that locally valid varbound constraints produce VLB/VUB entries [thanks to Anders Schack-Nielsen]
fixed bug in knapsack constraint handler where a modifiable constraint may be declared redundant
fixed bug in knapsack presolving with redundancy check after applyFixings() [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
fixed bug in CPLEX interface with getting basis information after the LP was modified and restored
fixed bug in knapsack separator with empty initial covers
fixed bug that SCIPgetLPSolstat() returns a valid status code even if the LP was not yet constructed for the current node
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)
branching on nearly-integral variables is now avoided in relpscost branching, which lead to a numerical assertion
removed wrong assert in varRemoveImplicsVbs()
fixed bug with updating LP size in probing
fixed dependency generation in example Makefiles

SCIP 0.8.1

Features

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
improved performance of the priority queue in conflict analysis
Plugins
- new presolver "implics" to find bound changes and aggregations out of the implication graph
- 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
- modified probing order in probing presolver
- LP file reader now accepts the keyword "Integer" for defining the start of the integer variables section
- added preliminary version of "intdiving" heuristic (disabled in default settings)
- slightly modified restartdfs node selector
- added crossover heuristic
- 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

replaced method SCIPconshdlrWasSeparationDelayed() by two methods SCIPconshdlrWasLPSeparationDelayed() and SCIPconshdlrWasSolSeparationDelayed()
replaced method SCIPsepaWasDelayed() by SCIPsepaWasLPDelayed() and SCIPsepaWasSolDelayed()
additional parameter "sol" for methods SCIPaddCut(), SCIPgetCutEfficacy() and SCIPisCutEfficacious()
additional parameter "sol" for method SCIPseparateKnapsackCover()
primal solutions may now contain values marked to be unknown (value is SCIP_UNKNOWN); unknown values don't contribute to the objective value of the solution; an unknown solution value should be treated as an arbitrary value in the variable's bounds, e.g., in the calculation of the feasibility of a constraint, a value inside the variable's bounds should be selected that makes the constraint as feasible as possible
renamed method SCIPgetNGlobalConss() to SCIPgetNConss()
new parameter "printzeros" for methods SCIPprintSol(), SCIPprintTransSol(), SCIPprintBestSol() and SCIPprintBestTransSol()

New API functions

SCIPgetConss(), SCIPgetNOrigConss() and SCIPgetOrigConss()
SCIPgetCuts()
SCIPsepaGetNConssFound() and SCIPsepaGetNDomredsFound()
SCIPgetVarConflictScore() and SCIPgetVarConflictScoreCurrentRun()
SCIPvarSetData()
SCIPcreateUnknownSol()
SCIPgetNConflictClausesFoundNode()
SCIPvarSetDelorigData(), SCIPvarSetTransData() and SCIPvarSetDeltransData()
SCIPvarHasBinaryImplic()
SCIPgetFixedVars() and SCIPgetNFixedVars()
SCIPconstructLP() to force constructing the LP of the current node
SCIPisLPConstructed()

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 >gt; 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 'p'rimal simplex and 'd'ual 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

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
also removed history_length, if NO_REMOVE_HISTORY is defined to support older versions of the readline library
removed bug in implication addition
fixed wrong assert with implications that imply a fixed variable
fixed numerics in check method of linear constraint handler
hopefully fixed bug with wrong path slash '/' under Windows
fixed numerics in probing and linear constraint handler (rentacar was detected to be infeasible in presolving)
fixed bug with calling heuristics in depths smaller than their frequency offset
fixed bug with aggregating fixed variables
fixed bugs in local branching and RINS heuristic
fixed bug in LP file reader with explicit zero coefficients
fixed bug in transitive implication addition
fixed bug with numerical error in LP resolve after probing or diving

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

reactivated multiaggregation in cons_linear.c on binary variables again (possible due to bug fix below)
introduced subversion string
adding variable bounds automatically adds the corresponding implication
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
improved debugging for infeasible cuts and propagations, given a primal feasible solution
slightly changed LP resolving loop in conflict analysis
diving heuristics now apply propagation at each step
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
modified the influence of the depth level in conflict analysis
new event type SCIP_EVENTTYPE_PRESOLVEROUND
added zlib support
replaced all abort() calls by SCIPABORT(); this is defined in def.h to be assert(FALSE)
improved knapsack cover separation
changed linear constraint presolving s.t. redundant sides are not removed if constraint is an equality
incorporated clique and implication information in knapsack constraint presolving
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)
improved preprocessing of variable bounds constraints
removed transitive clique generation, because this produces way too many cliques
improved preprocessing abort criteria
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"
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
Plugins
- 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
- 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
- new Message Handler plugin
- modified probing presolver to not add implications that are already included in the implication graph and clique table
- added file reader for LP format

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

additional parameter "validnode" for SCIPaddConsLocal() and SCIPaddConsNode()
SCIPhashtableRemove() can now also be called, if the element does not exist in the table
SCIPhashmapRemove() can now also be called, if the element does not exist in the map
additional parameter "branchdir" for SCIPbranchVar()
replaced method SCIPmessage() by SCIPverbMessage() with additional parameter "file"
put block memory shell and tclique algorithm into separate subdirectories
new parameter "duringlploop" of SCIPincludeHeur() - heuristics can now run during the price-and-cut loop at a node

New API functions

new file i/o methods SCIPfopen(), SCIPfclose(), SCIPfprintf(), ... that operate on the data type SCIPFILE; these methods automatically use zlib methods if the zlib is enabled
SCIPgetDualfarkasLinear() of linear constraint handler
SCIPgetDualfarkasLogicor() of logicor constraint handler
SCIPgetDualfarkasSetppc() of setppc constraint handler
SCIPgetDualsolKnapsack() of knapsack constraint handler
SCIPgetDualfarkasKnapsack() of knapsack constraint handler
SCIPgetDualsolVarbound() of varbound constraint handler
SCIPgetDualfarkasVarbound() of varbound constraint handler
SCIPgetNConflictClausesApplied()
SCIPdelVar()
SCIPgetVarStrongbranchLPAge()
SCIPgetNConflictClausesApplied()
SCIPconsGetValidDepth()
SCIPhashtableExists()
SCIPhashmapExists()
SCIPvarIsTransformedOrigvar()
SCIPvarIsDeleted()
SCIPnodeGetNumber()
SCIPsolveProbingLP() to solve the LP in a probing node (enables mixing of propagation and LP solving for diving heuristics)
SCIProwGetDualfarkas()
SCIPgetCurrentNode()
SCIPinterruptSolve()
SCIPerrorMessage(), SCIPwarningMessage(), SCIPdialogMessage() and SCIPinfoMessage()
SCIPsetMessagehdlr(), SCIPsetDefaultMessagehdlr() and SCIPgetMessagehdlr()
SCIPpropagateProbingImplications()
SCIPvarGetNCliques(), SCIPvarGetCliques(), SCIPvarsHaveCommonClique(), SCIPvarHasImplic()
SCIPcliqueGetNVars(), SCIPcliqueGetVars(), SCIPcliqueGetValues(), SCIPcliqueGetId()
SCIPaddClique(), SCIPcalcCliquePartition()
SCIPgetLPI() which makes all methods in scip/lpi.h available to the user
SCIPgetRandomInt() and SCIPgetRandomReal()
SCIPstrtok()
SCIPsetConsInitial(), SCIPsetConsSeparated(), SCIPsetConsEnforced(), SCIPsetConsChecked(), SCIPsetConsPropagated(), SCIPsetConsLocal(), SCIPsetConsDynamic(), SCIPsetConsRemoveable()
SCIPheurGetNBestSolsFound()

Command line interface

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

Changed parameters

replaced parameter "presolving/restartbdchgs" with parameters "presolving/maxrestarts" and "presolving/restartfac"
changed default values of "heuristics/∗/maxdiveavgquot" and "heuristics/∗/maxdiveavgquotnosol" to 0
additional setting SCIP_VERBLEVEL_DIALOG in "display/verblevel" parameter
additional LP pricing setting "partial"
parameters "constraints/agelimit" and "constraints/obsoleteage" now iterprete the value 0 as a dynamic setting
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
number of fractional variables included in parameter "separating/maxstallrounds"
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
replaced parameter "constraints/linear/maxpresolaggrrounds" with "constraints/linear/maxpresolpairrounds"
changed default value of "constraints/linear/maxaggrnormscale" to 0.0, which means to not apply aggregation

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

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
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 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 >gt; implint >gt; int >gt; 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 wrong asserts from lpi_cpx.c
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 ->gt; modified sepa_cmir.c, sepa_gomory.c and sepa_strongcg.c to use SCIPcreateEmptyRow() and SCIPaddVarsToRow() instead of SCIPcreateRow() which only works for COLs
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
removed wrong assertion in varAddImplic()
conflict analysis can now handle errors in LP solving calls
fixed bug in linear constraint handler with variables fixed to infinity
fixed bug with potential infinite loop if a separator is delayed and the LP is infeasible
fixed numerical bug in pseudo objective propagator with only slightly tightened bounds
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
removed bug in SCIPvarAddVlb() and SCIPvarAddVub() with fractional vlb/vubcoefs
removed bug that an LP might be declared to be solved even if it was marked erroneous due to numerical problems
fixed bug with redundant self implications that wrongly lead to the detection of infeasibility
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)
fixed bug in knapsack constraint presolving with tightening coefficients and capacity
fixed bug with modifiable constraints in linear constraint handler preprocessing
fixed bug in clique separator that reduced performance
increased performance of clique separator by allowing only a certain number of zero-weighted fill ins
fixed bug in linear constraint handler that global activities are not updated after global bound changes