/builds/gcg/gcg/CHANGELOG
Go to the documentation of this file.
9 - Added several strong branching based branching candidate selection heuristics: strong branching with column generation, strong branching without column generation, hybrid strong/pseudocost branching, reliability branching, hierarchical strong branching, hybrid hierarchical strong/pseudocost branching, hierarchical reliability branching (primarily for original variable branching and Ryan-Foster branching).
10 - New detector neighborhoodmaster: calculating cons-cons adjacency (if not already done), sorting according size of neighborhood. Searching two consecutive constraints with largest size difference (according neighborhood size) in sorted constraints. All constraints having a larger neighborhood than the second one are assigned to the master.
11 - On reading an incomplete decomposition, the program will not necessarily assign all open elements to the master problem but detect the rest of the structure.
17 - New parameters 'branching/orig/usestrong' and 'branching/ryanfoster/usestrong' to enable strong branching for original variable branching and Ryan-Foster branching
29 - Moved parameters 'detection/consclassifier/<name>/enabled' to 'detection/classification/consclassifier/<name>/enabled'
31 - Moved parameters 'detection/varclassifier/<name>/enabled' to 'detection/classification/varclassifier/<name>/enabled'
33 - Moved parameter 'detection/allowclassifierduplicates/enabled' to 'detection/classification/allowduplicates'
34 - Moved parameter 'detection/maxnclassesfornblockcandidates' to 'detection/blocknrcandidates/maxnclasses'
36 - Moved parameter 'detection/maxnclassesperclassifier' to 'detection/classification/maxnclassesperpartition'
37 - Moved parameter 'detection/maxnclassesperclassifierforlargeprobs' to 'detection/classification/maxnclassesperpartitionforlargeprobs'
38 - Moved parameter 'detection/strong_detection/dualvalrandommethod' to 'detection/score/strong_detection/dualvalrandommethod'
39 - Moved parameter 'detection/strong_detection/coeffactororigvsrandom' to 'detection/score/strong_detection/coeffactororigvsrandom'
68 - Removed legacymode, including detectors 'connected', 'staircase', 'random', 'cutpacking', 'colors', 'mcl'
105 - Fix commands 'transform' and 'presolve': Check SCIP_STAGE before calling SCIPdialogExecTransform() and SCIPdialogExecPresolve().
115 - Skip Farkas pricing only if at least one solution of the original problem was successfully added to the master variable space.
133 - Handle fixed master variables correctly when transforming values of original variables into values of master variables.
144 - 'write matrix' and 'write transmatrix' for writing a gnuplot file showing the (original and presolved) coefficient matrix
149 - new parameter "relaxing/gcg/mipdiscretization" indicates whether to use discretization with continuous variables (only has an effect if "relaxing/gcg/discretization" is enabled)
192 - propagateSeeed : given a partial decomposition d the detector returns a set of decompositions that are a refinement of d
193 - finsishSeeed: given a partial decomposition d the detector returns a set of decompositions that are a refinement of d and complete
194 - postprocessSeeed: given a complete decomposition d the detector returns a set of complete decompositions
195 - there is a current pool of partial decompositions (i.e. some conss and vars are open, initilized by empty decomposition (all vars and conss are open) or user decomposition )
196 - in every detection round the refinement method of each active detector is called on each current partial detection and returns a (possibly empty) set of decompositions (possibly still partial but strictly more refined); afterwards the finishing method of each detector is called on each partial decomposition
197 - after last round the postprocessing method of the corresponding detectors is called on each complete decomposition
199 - constraint and variable classification according to several criteria reveals more problem structure, and in particular yield candidates for the number of blocks, that are used by graph partitioning detectors
201 - structure information concerning the original problem can be used when searching structure in the transformed problem, e.g. by "detect presolve detect"
202 - more user interaction (see point "Command line interface" below for more information):
206 - new visualization methods for decompositions ('visualize' command in 'explore' submenu, family tree (experimental feature: finished decompositions can be seen as leaves in a forest, partial decompositions as inner nodes, ancestor descendant pairs are connected by edge ) )
214 - added menu item "write reportdecompositions" that creates a report of all decompositions in form of a .tex file
215 - Benders' decomposition mode has been added. The Benders' decomposition mode is activated by setting
216 "relaxing/gcg/mode" to 1. When using the Benders' decomposition mode, the decompositions found by the detectors are
218 - Original mode has been added. The original mode allows the user to solve the original problem directly without any
219 decomposition being performed. The original mode is selected by setting "relaxing/gcg/mode" to 2.
222 - pricing is now done by performing 'pricing jobs', which hold a pricing problem, a solver to be applied and some parameters (such as whether the solver is to be applied heuristically)
226 - extension of heuristic pricing, which can now be performed in multiple rounds; in particular, the MIP and the CPLEX pricing solver can now be applied multiple times per pricing loop, with increasing node, solution limits or decreasing gap limts.
227 - new possibility to sort pricing problems: reliability sorting based only on the last few pricing rounds
228 - possibility to solve pricing problems 'chunk'-wise, i.e. to only regard a certain subset of pricing problems in a pricer call
232 - GCG_DECL_SOLVERSOLVE and GCG_DECL_SOLVERSOLVEHEUR callbacks now also take the master SCIP instance as an input
233 - new callback GCG_DECL_SOLVERUPDATE, called by the pricer when constraint, bound or objective function changes occur on a pricing problem; also fixes a bug in the CPLEX pricing solver
240 - added parameter heuristics/restmaster/pbheur to use restricted master heuristic as price-and-branch heuristic
241 - imitate SCIP's separation procedure in the basis separator by storing the number separation rounds in probing per node
242 - artificial variables can now be added in the first Farkas pricing iteration to make the restricted master problem
243 feasible (including various options on setting the big M objective coefficients of these variables)
244 - new pricing solver that solves independent set problems heuristically using the cliquer library
245 - enable discretization when original problem is a mixed integer program; continuous variables are convexified
246 - solve original LP relaxation in the root node to get a first dual bound and to run some heuristics in the original problem
251 - structure detection (default) is now applicable to MIPs with much larger dimensions (150.000 x 500000)
256 - new internal data structure to handle partial decompositions; see class_seeed.h for more details
257 - new internal data structure to handle detection loops for different formulations (at the moment original and transformed formulation); see class_seeedpool.h for more information
258 - new internal data structure to handle constraint classification, each constraint classification is a partition of the constraints according a given criteria, used constraint classifiers:
263 - constraint name: levenshtein distance graph, for names according to nodes in the same connected component
264 - new internal data structure to handle variable classification, each variable classifier is a partition of the variables according to some criteria
272 - detector callback DETECTSTRUCTURE is only called in optional legacy mode (legacy mode is detection of version 2.1.4 and completely indepedent from new detecion loop), detectors written by the user should be useable if their parameter detection/detectors/∗/legacymode is set to TRUE
277 - detector callback PROPAGATESEEED, called during detection loop to refine partial decompositions, given a partial decomposition d the detector returns a set of decompositions that are a refinement of d
278 - detector callback FINISHSEEED, called during detection loop to finish partial decompositions, given a partial decomposition d the detector returns a set of complete decompositions that are a refinement of d
279 - detector callback POSTPROCESSSEEED, called after detection loop, to postprocess found finished decompositions, given a complete decomposition this method returns a set of complete decompositions
286 - "explore visualize" experimental feature, opens a gnuplot generated pdf visualization of specified decomposition, see /visual/pdfreader parametr
287 - "explore modify" modify known (partial) decompositions by applying specified detector callbacks or assign certain variables/constraints by name
288 - "explore calc_strong" highly experimental feature, calculates a score that is based on strength and solving speed of the Dantzig-Wolfe subproblems
290 - "write alloriginaldecompositions": write all known original decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
291 - "write allpresolveddecompositions": write all known presolved decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
292 - "write familytree": experimental feature, write all (partial) decompositions contained in family tree to files (.gp/.tex) and create family tree file (.tex), and corresponding makefile and docu
293 - "write reportdecompositions":experimental feature, write report of all finished decompositions to LaTeX format
294 - "set detection addblocknr": add candidates for the number of blocks (as a white space separated list)
300 - modified parameter "detectors/∗/priority" (detection was aborted if high priority detector was successful)
306 - new parameter "constraints/decomp/createbasicdecomp" indicates whether to create a decomposition with all constraints in the master if no other specified (useful to have included comparison)
307 - new parameter "detection/aggregation/limitnconssperblock" if this limit on the number of constraints of a block is exceeded the aggregation information for this block is not calculated
308 - new parameter "detection/aggregation/limitnvarsperblock" if this limit on the number of variables of a block is exceeded the aggregation information for this block is not calculated
309 - new parameter "detection/allowclassifierduplicates/enabled" indicates whether classifier duplicates are allowed (for statistical reasons)
310 - new parameter "detection/benders/enabled" indicates whether benders detection is enabled
311 - new parameter "detection/benders/onlybinmaster" indicates whether only decompositions with only binary variables in the master should be searched if benders detection is enabled
312 - new parameter "detection/benders/onlycontsubpr" indicates whether only decompositions with only continiuous variables in the subproblems should be searched if benders detection is enabled
313 - new parameter "detection/consclassifier/∗/enabled" indicates whether corresponding constraint classifier is enabled
314 - new parameter "detection/consclassifier/∗/origenabled" indicates whether corresponding constraint classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE )
315 - new parameter "detection/legacymode/enabled" indicates whether detection should additionally do legacy mode detection (detection of version 2.1.4)
316 - new parameter "detection/legacymode/onlylegacymode" indicates whether detection should only consist of legacy mode detection
317 - new parameter "detection/maxnclassesfornblockcandidates" to specify the maximum number of classes per classifier (if this number is exceeed two smallest classes are merged until it is reached, both classifier are kept)
318 - new parameter "detection/maxnclassesperclassifier" to specify the maximum number of classes per classifier (if this number is exceeed two smallest classes are merged until it is reached, both classifier are kept)
319 - new parameter "detection/maxnclassesperclassifierforlargeprobs" same as "detection/maxnclassesperclassifier" but only for larger problems (atm with nvars + nconss >= 50000)
320 - new parameter "detection/maxrounds" to specifiy the number of refinement rounds during detection
322 - new parameter "detection/origprob/classificationenabled" indicates whether constraint and variable classification is also enabeled for opriginal problem
323 - new parameter "detection/origprob/enabled" indicates whether to detect structures in original problem found decomps are tried to translate to transformed problem; only useful if presolving is enabled
324 - new parameter "detection/origprob/weightinggpresolvedoriginaldecomps" weighting method when comparing decompositions for presolved and unpresolved problem: 0: NO_MODIF, 1: FRACTION_OF_NNONZEROS, 2: FRACTION_OF_NROWS, 3: FAVOUR_PRESOLVED
325 - new parameter "detection/scoretype" indicates which score should be used for comparing (partial) decompositions (0: max white, 1: border area, 2: classic, 3: max foreseeing white, 4: ppc-max-white, 5: max foreseeing white with aggregation info, 6: ppc-max-white with aggregation info, 7: experimental benders score)
326 - new parameter "detection/detectors/∗/enabled" is this detector enabled when detecting in the transformed problem
327 - new parameter "detection/detectors/∗/finishingenabled" is this detector enabled when finishing partial decompsositions in the original and transformed problem
328 - new parameter "detection/detectors/∗/freqcallround" frequency the detector gets called in detection loop ,ie it is called in round r if and only if mincallround <= r <= maxcallround AND (r - mincallround) mod freqCallRound == 0
329 - new paramater "detection/detectors/∗/legacymode" flag to indicate whether (old) DETECTSTRUCTURE method of detector should be used
330 - new parameter "detection/detectors/∗/maxcallround" maximum round the detector gets called in detection loop
331 - new parameter "detection/detectors/∗/mincallround" minimum round the detector gets called in detection loop
332 - new parameter "detection/detectors/∗/origenabled" is this detector enabled when detecting in the original problem (overruled by "detection/origprob/enabled" )
333 - new parameter "detection/detectors/∗/origfreqcallround" same as "detectors/∗/freqcallround" for original problem
334 - new parameter "detection/detectors/∗/origmaxcallround" same as "detectors/∗/maxcallround" for original problem
335 - new parameter "detection/detectors/∗/origmincallround" same as "detectors/∗/mincallround" for original problem
336 - new parameter "detection/detectors/∗/overruleemphasis" flag to indicate whether emphasis settings for detector <%s> should be overruled by normal settings
337 - new parameter "detection/detectors/∗/postprocessingenabled" is this detector enabled when postprocessing in the original and the transformed problem
338 - new parameter "detection/detectors/∗/usefulrecall" indicates whether this detector is called on descendants of a partial decomposition
339 - new parameter "detection/detectors/connectedbase/useconssadj" should the constraint adjacency datastructure be used (and not the constraint-variable-incidency)
340 - new parameter "detection/detectors/{hrgpartition,hrcgpartition,hcgpartition}/maxnblockcandidates" the maximal number of block number candidates that is used by this detector
341 - new parameter "detection/strong_detection/coeffactororigvsrandom": convex coefficient for original dual values (1-this is factor for random dual value)
342 - new parameter "detection/strong_detection/dualvalrandommethod": method for random dual values use for strong decomposition: 1) naive, 2) expected equality exponential distributed, 3) expected overestimation exponential distributed
343 - new parameter "detection/varclassifier/∗/enabled" indicates whether corresponding variable classifier is enabled
344 - new parameter "detection/varclassifier/∗/origenabled" indicates whether corresponding variable classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE
347 - new parameters "pricing/masterpricer/maxcolsprob*" limit number of columns to be generated per pricing problem
348 - new parameter "pricing/masterpricer/heurpricingiters" replaces old parameter "pricing/masterpricer/heurpricing" and sets maximum number of heuristic pricing rounds within the pricing loop
349 - new parameter "pricing/masterpricer/maxheurdepth" limits maximum depth in the b&b tree at which heuristic pricing is performed
350 - changed parameter "pricing/masterpricer/sorting" to type 'char' and add an option to sort by reliability based only on the last few rounds
351 - new parameter "pricing/masterpricer/nroundscol" sets the number of pricing rounds considered in that case
352 - new parameter "pricing/masterpricer/chunksize" sets the size of the subset ('chunk') of pricing problems to be considered in a pricing round
353 - new parameter "pricing/masterpricer/stabilizationtree" to enable or disable stabilization beyond the root node
354 - new parameter "pricing/masterpricer/useartificualvars" to use artificial variables to make the RMP feasible
355 - new parameter "pricing/masterpricer/bigmartificial" to set big M objective of artificial variables
356 - new parameter "pricing/masterpricer/factorunreliable" to set factor to be used for the objective of unbounded variables
357 - new parameter "pricing/masterpricer/usemaxobj" to limit big M objective of artificial variables
359 - new parameter "relaxing/gcg/mode" is used to set the the Dantzig-Wolfe or Benders' decomposition mode of GCG.
361 - new parameter "set/visual/colorscheme" sets the color scheme of visualizations produced by the gp and tex reader
362 - new parameter "set/visual/draftmode" sets whether nonzeros are shown in visualizations produced by the gp and tex reader
363 - new parameter "set/visual/nonzeroradius" sets the radius of nonzeros in visualizations produced by the gp and tex reader
364 - new parameter "set/visual/pdfreader" sets a PDF reader that is used for opening visualizations
365 - new parameter "set/visual/nmaxdecompstowrite" sets maximum number of decompositions to write
366 - new parameter "set/visual/colors/colorblock" sets color for blocks in visualizations produced by the gp and tex reader
367 - new parameter "set/visual/colors/colorlines" sets color for lines in visualizations produced by the gp and tex reader
368 - new parameter "set/visual/colors/colorlinking" sets color for linking variables in visualizations produced by the gp and tex reader
369 - new parameter "set/visual/colors/colormasterconss" sets color for master constraints in visualizations produced by the gp and tex reader
370 - new parameter "set/visual/colors/colormastervars" sets color for master variables in visualizations produced by the gp and tex reader
371 - new parameter "set/visual/colors/colornonzeros" sets color for nonzeros in visualizations produced by the gp and tex reader
372 - new parameter "set/visual/colors/coloropen" sets color for open areas in visualizations produced by the gp and tex reader
373 - new parameter "set/visual/colors/colorstairlinking" sets color for stairlinking variables in visualizations produced by the gp and tex reader
374 - new parameter "set/visual/famtree/maxndecomps" sets maximum number of finished decompositions in family tree
375 - new parameter "set/visual/report/maxndecomps" sets maximum number of decompositions shown in report
376 - new parameter "set/visual/report/showstatistics" sets whether statistics for each decomposition are included in report
377 - new parameter "set/visual/report/showtitle" sets whether a title page is included in report
378 - new parameter "set/visual/report/showtoc" sets whether a table of contents is included in report
379 - new parameter "set/visual/report/showtype" sets whether only decompositions of a certain type are included in report
380 - new parameter "set/visual/report/usegp" sets whether the report uses gnuplot or LaTeX/Tikz images in report
385 - use SCIP_STATISTIC for pricing statistics and add compiler flag STATISTICS; if STATISTICS is set to true,
387 - add parameter in basis separator specifying the emphasis setting used for separation in probing; remove unnecessary
389 - introduce new module solver.c for managing pricing solvers, to be compliant to how SCIP plugins are designed
396 - fix detection of knapsack subproblems in knapsack pricing solver by also accepting negative weights
426 - cleanup for extreme point heuristics, moved code to own methods, added comments, remove redundant parameters
429 - reorder permutations in isomorph detector according to orbit size and add maxdecomps parameter
432 - changed/corrected variable fixing behaviour of Extreme Point RINS in case of aggregated blocks
464 - fixed a time limit issue concerning the master problem that was introduced by the SCIP reoptimization feature
479 - re-organized constraint handlers for managing branching decisions in original and master problems