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 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
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)
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
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
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()
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
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
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
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)