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

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)
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()
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)
Constraints:
- 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
- changed name of method SCIPconshdlrGetNVarTypes() to SCIPconshdlrGetNChgVarTypes()
Conflicts:
- method SCIPgetNConflictClausesFound() renamed to SCIPgetNConflictConssFound()
- method SCIPgetNConflictClausesFoundNode() renamed to SCIPgetNConflictConssFoundNode()
- method SCIPgetNConflictClausesApplied() renamed to SCIPgetNConflictConssApplied()

New API functions

SCIPsolveProbingLPWithPricing()
SCIPchgVarLbRoot() and SCIPchgVarUbRoot()
SCIPinRepropagation()
SCIPaddDialogInputLine() and SCIPaddDialogHistoryLine()
SCIPtransformProb() to create the transformed problem; enables the user, e.g., to add primal solutions before the presolving begins
SCIPcreateSolCopy()
SCIPareSolsEqual()
Getters:
- SCIPgetRowKnapsack(), SCIPgetRowLinear(), SCIPgetRowLogicor(), SCIPgetRowSetppc(), and SCIPgetRowVarbound() for obtaining the linear relaxation of a corresponding constraint
- SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdvarVarbound(), and SCIPgetVbdcoefVarbound()
- SCIPgetLPRootObjval(), SCIPgetLPRootColumnObjval() and SCIPgetLPRootLooseObjval()
- SCIPcolGetMinPrimsol() and SCIPcolGetMaxPrimsol()
- SCIPgetFocusDepth()
Score:
Reduced Cost:
- SCIPgetColRedcost()
- SCIPvarGetRootRedcost()
Variables:

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:
- fixed bug in SCIPcliqueSearchVar() [thanks to Anders Schack-Nielsen]
- fixed bug in SCIPcliqueAddVar() [thanks to Anders Schack-Nielsen]
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

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
new parameter printzeros for methods SCIPprintSol(), SCIPprintTransSol(), SCIPprintBestSol() and SCIPprintBestTransSol()
Constraints:
- replaced method SCIPconshdlrWasSeparationDelayed() by two methods SCIPconshdlrWasLPSeparationDelayed() and SCIPconshdlrWasSolSeparationDelayed()
- renamed method SCIPgetNGlobalConss() to SCIPgetNConss()

New API functions

SCIPgetCuts()
SCIPgetVarConflictScore() and SCIPgetVarConflictScoreCurrentRun()
SCIPvarSetData()
SCIPcreateUnknownSol()
SCIPgetNConflictClausesFoundNode()
SCIPvarSetDelorigData(), SCIPvarSetTransData() and SCIPvarSetDeltransData()
SCIPvarHasBinaryImplic()
SCIPgetFixedVars() and SCIPgetNFixedVars()
SCIPgetConss(), SCIPgetNOrigConss() and SCIPgetOrigConss()
SCIPsepaGetNConssFound() and SCIPsepaGetNDomredsFound()
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 > 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

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

SCIPgetNConflictClausesApplied()
SCIPgetNConflictClausesApplied()
SCIPhashtableExists()
SCIPhashmapExists()
SCIPnodeGetNumber()
SCIPsolveProbingLP() to solve the LP in a probing node (enables mixing of propagation and LP solving for diving heuristics)
SCIProwGetDualfarkas()
SCIPgetCurrentNode()
SCIPinterruptSolve()
SCIPpropagateProbingImplications()
SCIPgetLPI() which makes all methods in scip/lpi.h available to the user
SCIPgetRandomInt() and SCIPgetRandomReal()
SCIPstrtok()
SCIPheurGetNBestSolsFound()
Variables:
Messages and IO:
- SCIPerrorMessage()
- SCIPwarningMessage()
- SCIPdialogMessage()
- SCIPinfoMessage()
- SCIPsetMessagehdlr()
- SCIPsetDefaultMessagehdlr()
- SCIPgetMessagehdlr()
- 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
Cliques:
Constraint handler:
- 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
- SCIPconsGetValidDepth()
- SCIPsetConsInitial()
- SCIPsetConsSeparated()
- SCIPsetConsEnforced()
- SCIPsetConsChecked()
- SCIPsetConsPropagated()
- SCIPsetConsLocal()
- SCIPsetConsDynamic()
- SCIPsetConsRemoveable()

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:
- removed wrong asserts from lpi_cpx.c
- removed wrong assertion in varAddImplic()
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