/builds/gcg/gcg/CHANGELOG

Go to the documentation of this file.

/**@page RN35 Release notes for GCG 3.5
@section RN350 GCG 3.5.0
*************************
 
New features:
-------------
 
- New website documentation
- 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).
- 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.
- 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.
- Use the user's default application to open pdf files
 
New/changed parameters:
-----------------------
 
- New parameters 'branching/orig/usestrong' and 'branching/ryanfoster/usestrong' to enable strong branching for original variable branching and Ryan-Foster branching
- New parameters 'branching/bpstrong/...' to alter strong branching behavior
- New parameter 'detection/enabled' for easier en-/disabling of the detection
- New Parameter 'detection/postprocess' enables the postprocessing of decompositions
- Removed paramaters 'detection/detectors/<name>/legacymode'
- Removed parameter 'detection/conssadjcalculated'
- Removed parameter 'detection/legacymode/onlylegacymode'
- Removed parameter 'detection/legacymode/enabled'
- Removed parameter 'detection/legacymode/stairlinkingheur'
- Removed parameter 'visual/report/showtype'
- Removed parameter 'constraints/decomp/createbasicdecomp'
- Removed parameters 'detection/detectors/<name>/origenabled'
- Moved parameters 'detection/consclassifier/<name>/enabled' to 'detection/classification/consclassifier/<name>/enabled'
- Removed parameters 'detection/consclassifier/<name>/origenabled'
- Moved parameters 'detection/varclassifier/<name>/enabled' to 'detection/classification/varclassifier/<name>/enabled'
- Removed parameters 'detection/varclassifier/<name>/origenabled'
- Moved parameter 'detection/allowclassifierduplicates/enabled' to 'detection/classification/allowduplicates'
- Moved parameter 'detection/maxnclassesfornblockcandidates' to 'detection/blocknrcandidates/maxnclasses'
- Moved parameter 'detection/addblocknr' to 'set/detection/blocknrcandidates/addblocknr'
- Moved parameter 'detection/maxnclassesperclassifier' to 'detection/classification/maxnclassesperpartition'
- Moved parameter 'detection/maxnclassesperclassifierforlargeprobs' to 'detection/classification/maxnclassesperpartitionforlargeprobs'
- Moved parameter 'detection/strong_detection/dualvalrandommethod' to 'detection/score/strong_detection/dualvalrandommethod'
- Moved parameter 'detection/strong_detection/coeffactororigvsrandom' to 'detection/score/strong_detection/coeffactororigvsrandom'
- Moved parameter 'detection/scoretype' to 'detection/score/scoretype'
 
New/changed menu commands:
-----------------------
 
- Removed 'toolbox' feature from 'explore' menu
- Removed command 'toolbox'
- Removed command 'write/miplib2017features'
- Removed command 'write/miplib2017plotsanddecs'
- Removed command 'write/miplib2017shortbasefeatures'
- Removed command 'write/miplib2017featurefilepath'
- Removed command 'write/miplib2017matrixfilepath'
- Removed command 'write/miplib2017decompfilepath'
- Removed command 'write alloriginaldecompositions'
- Removed command 'write allpresolveddecompositions'
- Renamed command 'write reportdecompositions' to 'write report'
- Renamed command 'write selecteddecompositions' to 'write selected'
 
Visualization and testing:
--------------------------
 
- check/compareversions.sh runs tests on several git versions, summarizes performace results
 
Code cleanup:
-------------
 
- Cleaned up 'explore' menu
- Refactored detection loop
- Removed legacymode, including detectors 'connected', 'staircase', 'random', 'cutpacking', 'colors', 'mcl'
- Renamed class Seeed to PARTIALDECOMP
- Renamed class Seeedpool to DETPROBDATA
- Renamed SEEED_WRAPPER to PARTIALDECOMP_WRAPPER
- Renamed {Index,Cons,Var}Classifier to {Index,Cons,Var}Partition
- Refactored dialog handler
- Moved GCG version define to 'def.h', moved 'GCGprintVersion' to 'gcg_general.h/c'
 
New/modified API functions:
---------------------------
- New functions: 'GCGtransformProb', 'GCGpresolve', 'GCGdetect', 'GCGsolve'
- Renamed 'GCGgetGap' to 'GCGgetVarGap' and 'GCGsetGap' to 'GCGsetVarGap'
- New functions: 'GCGgetDualbound', 'GCGgetPrimalbound', 'GCGgetGap'
 
Bug fixes
---------
- Fixed function 'ObjPricerGcg::computeCurrentDegeneracy'
- Relaxator: Do not construct and flush the LP if it is already constructed
 
 
@page RN30 Release notes for GCG 3.0
@section RN305 GCG 3.0.5
*************************
 
Bug fixes
---------
 
- Skip structure detection if the original problem is already solved after presolving.
 
 
@section RN304 GCG 3.0.4
*************************
 
Bug fixes
---------
 
- Fix segmentation fault.
- Fix commands 'transform' and 'presolve': Check SCIP_STAGE before calling SCIPdialogExecTransform() and SCIPdialogExecPresolve().
 
 
@section RN303 GCG 3.0.3
*************************
 
Bug fixes
---------
 
- Fix several segmentation faults. 
- Skip Farkas pricing only if at least one solution of the original problem was successfully added to the master variable space.
- Interrupt the pricing loop if SCIP reports that the solving process should be stopped.
- Disable the column pool in probing mode.
- 'write matrix' and 'write transmatrix' set PDF as file format in the created gnuplot file.
 
 
@section RN302 GCG 3.0.2
*************************
 
Bug fixes
---------
 
- Fix segmentation fault due to missing relaxsol event handler in BENDERS and ORIGINAL mode.
- Fix cmake module FindBLISS to handle GMP dependency correctly.
- Fix branching on directly transferred master variables in generic branching.
- Fix in pricer_gcg when calculating stabilized dual objective value.
- Fix a parameter bug concerning heuristic pricing.
- Fix: sort pricing solvers before initialization of pricing controller.
- Handle fixed master variables correctly when transforming values of original variables into values of master variables.
- Transfer solutions to the master problem only if it is not solved already.
 
 
 
@section RN301 GCG 3.0.1
*************************
 
Command line interface
-----------------------
 
- 'write matrix' and 'write transmatrix' for writing a gnuplot file showing the (original and presolved) coefficient matrix
 
New/changed parameters
-----------------------
 
- new parameter "relaxing/gcg/mipdiscretization" indicates whether to use discretization with continuous variables (only has an effect if "relaxing/gcg/discretization" is enabled)
 
Performance improvements
-------------------------
 
- Improved performance of creating Gnuplot matrix visualizations
- Corrected transfer from feasible master solutions to the original problem
- Improved performnace of calculating foreseeing decomposition scores
 
Code cleanup
------------
 
- Clean up scaling code in Gnuplot reader
 
Bug fixes
---------
 
- Fix segmentation faults in aggressive detection
- Fix toolbox method for assigning variables per regular expression
- Fix issue with setting variables as linking variables in decomposition toolbox
- Call hmetis only if at matrix should be decomposed into at least two blocks
- Fix issues with hmetis in aggressive detection
- Deal with empty or duplicate constraint names
- Fix an assertion in detection concerning a non-existent hashmap
- Fix memory error in relaxator concerning a filename string that was not freed
- Fix bug in reader_dec for original problem
- Handle double stored external branching candidates correctly in ZI rounding heuristic
- Fix issue with non-violated cuts in separation storage
- Fix NULL pointer error in two 'if' clauses in seeed pool
- Fix memory leak in event_relaxsol
- Use correct method to free event handler data in event_relaxsol.
- Fix parallelization in pricing loop by allowing only one job per pricing problem at a time
- Add a missing Makefile dependency
 
 
@section RN300 GCG 3.0.0
*************************
 
Features
--------
 
- new roundwise modular structure detection scheme:
  - detectors can implement three optional methods:
    - propagateSeeed : given a partial decomposition d the detector returns a set of decompositions that are a refinement of d
    - finsishSeeed: given a partial decomposition d the detector returns a set of decompositions that are a refinement of d and complete
    - postprocessSeeed: given a complete decomposition d the detector returns a set of complete decompositions
  - 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 )
  - 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
  - after last round the postprocessing method of the corresponding detectors is called on each complete decomposition
  - duplicates of partial and complete are identified
  - 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
  - detection process can run parallelized (in presence of multiple partial decompositions)
  - structure information concerning the original problem can be used when searching structure in the transformed problem, e.g. by "detect presolve detect"
  - more user interaction (see point "Command line interface" below for more information):
        - by command "explore" and inspecting found decompositions,
        - give partial decompositions,
        - directly modify found partial decompositions
  - 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 ) )
  - new scores to evaluate found decompositions
- solve the problem with one single block if no decomposition is available ('SCIP mode')
- extended isomorph detector by the possibility to identify blocks which are identical
  w.r.t. signs (but not necessarily values) of coefficients.
- extended backtracking mechanism in diving heuristics:
  single backtracking in addition to limited discrepancy search in master variable diving;
  added branching on another variable and limited disc. search to original variable diving
- added menu item "write reportdecompositions" that creates a report of all decompositions in form of a .tex file
- Benders' decomposition mode has been added. The Benders' decomposition mode is activated by setting
  "relaxing/gcg/mode" to 1. When using the Benders' decomposition mode, the decompositions found by the detectors are
  used as the master and subproblems.
- Original mode has been added. The original mode allows the user to solve the original problem directly without any
  decomposition being performed. The original mode is selected by setting "relaxing/gcg/mode" to 2.
- new pricing scheme:
  - the pricing loop is now managed by a new class, the 'pricing controller'
  - 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)
  - pricing jobs are organized in a priority queue, which is maintained by the pricing controller
  - the latter now also decides over premature abortion of the pricing loop
- own data structure for pricing problems which also holds solving statistics and results
- 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.
- new possibility to sort pricing problems: reliability sorting based only on the last few pricing rounds
- possibility to solve pricing problems 'chunk'-wise, i.e. to only regard a certain subset of pricing problems in a pricer call
- add price store similar to SCIP's sepa store for better column management
- interface change in pricing solvers:
  - solvers now pass their columns directly to the pricing storage rather than returning an array
  - GCG_DECL_SOLVERSOLVE and GCG_DECL_SOLVERSOLVEHEUR callbacks now also take the master SCIP instance as an input
  - 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
- new return type GCG_PRICINGSTATUS which replaces SCIP_STATUS in the pricing solvers
 
- add additional pricing and variable statistics
- add hybridization of dual variable smoothing with an ascent method
- restructure column pool similar to SCIP's cut pool
- parametrize pricing solver priorities
- added parameter heuristics/restmaster/pbheur to use restricted master heuristic as price-and-branch heuristic
- imitate SCIP's separation procedure in the basis separator by storing the number separation rounds in probing per node
- artificial variables can now be added in the first Farkas pricing iteration to make the restricted master problem
  feasible (including various options on setting the big M objective coefficients of these variables)
- new pricing solver that solves independent set problems heuristically using the cliquer library
- enable discretization when original problem is a mixed integer program; continuous variables are convexified
- solve original LP relaxation in the root node to get a first dual bound and to run some heuristics in the original problem
 
Performance improvements
-------------------------
 
- structure detection (default) is now applicable to MIPs with much larger dimensions (150.000 x 500000)
 
Data structures
----------------
 
- new internal data structure to handle partial decompositions; see class_seeed.h for more details
- 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
- new internal data structure to handle constraint classification, each constraint classification is a partition of the constraints according a given criteria, used constraint classifiers:
        - number of nonzero entries
        - constraint type according to SCIP constraint handlers
        - constraint type according to MIPLIB2010 constraint classifiaction
        - constraint name: identity for names with removed digits
        - constraint name: levenshtein distance graph, for names according to nodes in the same connected component
- new internal data structure to handle variable classification, each variable classifier is a partition of the variables according to some criteria
        - SCIP variable type
        - objective coefficient
        - objective sign
 
Deleted and modified API functions
-----------------------------------
 
- 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
 
New API functions
-----------------
 
- 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
- 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
- detector callback POSTPROCESSSEEED, called after detection loop, to postprocess found finished  decompositions, given a complete decomposition this method returns a set of complete decompositions
 
Command line interface
-----------------------
 
- "explore" submenu to inspect and modify new decompositions
- "explore inspect" get information about decomposition on different detail levels
- "explore visualize" experimental feature, opens a gnuplot generated pdf visualization of specified decomposition, see /visual/pdfreader parametr
- "explore modify"  modify known (partial) decompositions by applying specified detector callbacks or assign certain variables/constraints by name
- "explore calc_strong" highly experimental feature, calculates a score that is based on strength and solving speed of the Dantzig-Wolfe subproblems
- "decomposition_toolbox" creates an empty decomposition (and modify afterwards)
- "write alloriginaldecompositions":  write all known original decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
- "write allpresolveddecompositions": write all known presolved decompositions to files (format is given by file extension, e.g. {dec,blk,ref,gp,tex})
- "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
- "write reportdecompositions":experimental feature,  write report of all finished decompositions to LaTeX format
- "set detection addblocknr": add candidates for the number of blocks (as a white space separated list)
 
 
Deleted and modified parameters
--------------------------------
 
- modified parameter "detectors/∗/priority" (detection was aborted if high priority detector was successful)
 
 
New/changed parameters
-----------------------
 
- 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)
- 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
- 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
- new parameter "detection/allowclassifierduplicates/enabled" indicates whether classifier duplicates are allowed (for statistical reasons)
- new parameter "detection/benders/enabled" indicates whether benders detection is enabled
- new parameter "detection/benders/onlybinmaster" indicates whether only decompositions with only binary variables in the master should be searched if benders detection is enabled
- new parameter "detection/benders/onlycontsubpr" indicates whether only decompositions with only continiuous variables in the subproblems should be searched if benders detection is enabled
- new parameter "detection/consclassifier/∗/enabled" indicates whether corresponding constraint classifier is enabled
- new parameter "detection/consclassifier/∗/origenabled" indicates whether corresponding constraint classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE )
- new parameter "detection/legacymode/enabled" indicates whether detection should additionally do legacy mode detection (detection of version 2.1.4)
- new parameter "detection/legacymode/onlylegacymode" indicates whether detection should only consist of legacy mode detection
- 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)
- 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)
- new parameter "detection/maxnclassesperclassifierforlargeprobs" same as "detection/maxnclassesperclassifier" but only for larger problems (atm with nvars + nconss >= 50000)
- new parameter "detection/maxrounds" to specifiy the number of refinement rounds during detection
 
- new parameter "detection/origprob/classificationenabled" indicates whether constraint and variable classification is also enabeled for opriginal problem
- 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
- 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
- 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)
- new parameter "detection/detectors/∗/enabled" is this detector enabled when detecting in the transformed problem
- new parameter "detection/detectors/∗/finishingenabled" is this detector enabled when finishing partial decompsositions in the original and transformed problem
- 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
- new paramater "detection/detectors/∗/legacymode" flag to indicate whether (old) DETECTSTRUCTURE method of detector should be used
- new parameter "detection/detectors/∗/maxcallround" maximum round the detector gets called in detection loop
- new parameter "detection/detectors/∗/mincallround" minimum  round the detector gets called in detection loop
- new parameter "detection/detectors/∗/origenabled" is this detector enabled when detecting in the original problem (overruled by "detection/origprob/enabled" )
- new parameter "detection/detectors/∗/origfreqcallround" same as "detectors/∗/freqcallround" for original problem
- new parameter "detection/detectors/∗/origmaxcallround" same as "detectors/∗/maxcallround" for original problem
- new parameter "detection/detectors/∗/origmincallround" same as "detectors/∗/mincallround" for original problem
- new parameter "detection/detectors/∗/overruleemphasis" flag to indicate whether emphasis settings for detector <%s> should be overruled by normal settings
- new parameter "detection/detectors/∗/postprocessingenabled" is this detector enabled when postprocessing in the original and the transformed problem
- new parameter "detection/detectors/∗/usefulrecall" indicates whether this detector is called on descendants of a partial decomposition
- new parameter "detection/detectors/connectedbase/useconssadj" should the constraint adjacency datastructure  be used (and not the constraint-variable-incidency)
- new parameter "detection/detectors/{hrgpartition,hrcgpartition,hcgpartition}/maxnblockcandidates" the maximal number of block number candidates that is used by this detector
- new parameter "detection/strong_detection/coeffactororigvsrandom": convex coefficient for original dual values (1-this is factor for random dual value)
- 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
- new parameter "detection/varclassifier/∗/enabled" indicates whether corresponding variable classifier is enabled
- new parameter "detection/varclassifier/∗/origenabled" indicates whether corresponding variable classifier is enabled for original problem (no effect if "detection/origprob/classificationenabled" is FALSE
 
 
- new parameters "pricing/masterpricer/maxcolsprob*" limit number of columns to be generated per pricing problem
- new parameter "pricing/masterpricer/heurpricingiters" replaces old parameter "pricing/masterpricer/heurpricing" and sets maximum number of heuristic pricing rounds within the pricing loop
- new parameter "pricing/masterpricer/maxheurdepth" limits maximum depth in the b&b tree at which heuristic pricing is performed
- changed parameter "pricing/masterpricer/sorting" to type 'char' and add an option to sort by reliability based only on the last few rounds
- new parameter "pricing/masterpricer/nroundscol" sets the number of pricing rounds considered in that case
- new parameter "pricing/masterpricer/chunksize" sets the size of the subset ('chunk') of pricing problems to be considered in a pricing round
- new parameter "pricing/masterpricer/stabilizationtree" to enable or disable stabilization beyond the root node
- new parameter "pricing/masterpricer/useartificualvars" to use artificial variables to make the RMP feasible
- new parameter "pricing/masterpricer/bigmartificial" to set big M objective of artificial variables
- new parameter "pricing/masterpricer/factorunreliable" to set factor to be used for the objective of unbounded variables
- new parameter "pricing/masterpricer/usemaxobj" to limit big M objective of artificial variables
 
- new parameter "relaxing/gcg/mode" is used to set the the Dantzig-Wolfe or Benders' decomposition mode of GCG.
 
- new parameter "set/visual/colorscheme" sets the color scheme of visualizations produced by the gp and tex reader
- new parameter "set/visual/draftmode" sets whether nonzeros are shown in visualizations produced by the gp and tex reader
- new parameter "set/visual/nonzeroradius" sets the radius of nonzeros in visualizations produced by the gp and tex reader
- new parameter "set/visual/pdfreader" sets a PDF reader that is used for opening visualizations
- new parameter "set/visual/nmaxdecompstowrite" sets maximum number of decompositions to write
- new parameter "set/visual/colors/colorblock" sets color for blocks in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorlines" sets color for lines in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorlinking" sets color for linking variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colormasterconss" sets color for master constraints in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colormastervars" sets color for master variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colornonzeros" sets color for nonzeros in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/coloropen" sets color for open areas in visualizations produced by the gp and tex reader
- new parameter "set/visual/colors/colorstairlinking" sets color for stairlinking variables in visualizations produced by the gp and tex reader
- new parameter "set/visual/famtree/maxndecomps" sets maximum number of finished decompositions in family tree
- new parameter "set/visual/report/maxndecomps" sets maximum number of decompositions shown in report
- new parameter "set/visual/report/showstatistics" sets whether statistics for each decomposition are included in report
- new parameter "set/visual/report/showtitle" sets whether a title page is included in report
- new parameter "set/visual/report/showtoc" sets whether a table of contents is included in report
- new parameter "set/visual/report/showtype" sets whether only decompositions of a certain type are included in report
- new parameter "set/visual/report/usegp" sets whether the report uses gnuplot or LaTeX/Tikz images in report
 
Code cleanup
------------
 
- use SCIP_STATISTIC for pricing statistics and add compiler flag STATISTICS; if STATISTICS is set to true,
  SCIP_STATISTIC will be defined
- add parameter in basis separator specifying the emphasis setting used for separation in probing; remove unnecessary
  distinctions on objective direction
- introduce new module solver.c for managing pricing solvers, to be compliant to how SCIP plugins are designed
- re-structured solver_mip
 
Bug fixes
---------
- fix a bug in the automatic update of the stabilization parameter alpha
- fix issue with pricing problem initialization in CPLEX pricing solver
- fix detection of knapsack subproblems in knapsack pricing solver by also accepting negative weights
- fix memory management in set covering heuristic
- fix a bug in GCG feasibility pump concerning wrong SCIP instances.
 
@page RN21 Release notes for GCG 2.1
@section RN214 GCG 2.1.4
*************************
 
- use SCIPaddRow() instead of deprecated SCIPaddCut()
 
@section RN213 GCG 2.1.3
*************************
 
- changed interface to SCIP 5.0.0
 
bug fixes
- fix memory bug in original diving event handler
- fix memory bug in DECdecompRemoveDeletedConss
- fix bugs in check script
- fix bug in checking if master is a set partitioning problem
- implement enforelax callbacks
- diving heuristics and branching rules compute fractionalities by themselves
 
 
@section RN212 GCG 2.1.2
*************************
 
- changed interface to SCIP 4.0.0
 
code cleanup
- cleanup for extreme point heuristics, moved code to own methods, added comments, remove redundant parameters
- reallocate memory for origvars array in pricingvardate more efficiently
- reallocate memory for original variable array in pricing variable data more efficiently
- reorder permutations in isomorph detector according to orbit size and add maxdecomps parameter
 
bug fixes
- changed/corrected variable fixing behaviour of Extreme Point RINS in case of aggregated blocks
- fixed handling of fixed variables in decompositions
- update include method of solver template
- fix GCGconsGet*() methods such that negated variables are handled correctly
- fix bug in transformation of master solution to original solution
- small bugfix in method that creates column graph from matrix
- fixed memory errors in unit tests
- fix memory issue with GCG_COL's
- fix the deletion of old columns in the column pool
- fix propagation of original variable bounds to the pricing problems:
  propapagte bounds only if identical variables have the same bounds,
  throw an error message otherwise
- in case of global bound changes on original variables, check if the current relaxation
  solution satisfies the new bound, and mark it invalid if not
- stop the reduced cost pricing clock correctly
- free redundant decompositions correctly
- fix identity check of decompositions
- fix bug in createPolishedDecomp()
- fix bug in isomorph detector
- avoid numerical troubles by rounding integral pricing solutions if possible
 
 
@section RN211 GCG 2.1.1
*************************
 
code cleanup
- simplified logic when assigning variables to blocks
 
bug fixes
- use only one hashmap when initializing pricing problems
- small bugfix in set covering heuristic
- fixed a bug in original variable diving heuristics
- fixed a time limit issue concerning the master problem that was introduced by the SCIP reoptimization feature
- reorganized detector callbacks and thus fixed memory leaks when reading a new instance
- fixed memory allocation in basis separator
 
@section RN210 GCG 2.1.0
*************************
 
features
- column pool
- new set covering heuristic
- basis cuts separator
- numerical tolerances of the original problem are used in the master and pricing problems
- new compiler flag CPLEXSOLVER to solve pricing problems with CPLEX
 
code cleanup
- re-organized constraint handlers for managing branching decisions in original and master problems
- simplified code and reduced memory consumption in cutpacking detector
 
bug fixes
- GCG columns are freed correctly in the pricer
 
@page RN20 Release notes for GCG 2.0
@section RN201 GCG 2.0.1
*************************
 
features
- decomposition and pricing problems are permuted when the permutation
  seed is set
- progress in dual bound is now displayed while solving the root node
- pricing solvers can be enabled or disabled via parameter
- display blocks found for decomposition in statistics
- new boundtype for fixed original variables due to branching
- use new GCG column structure instead SCIP solution structure in pricing
 
code cleanup
- simplify code in generic branching
- structure of method branchVar()
 
bug fixes
- fix bugs concerning stabilization
- disable stabilization when linking variables or variables belonging to no block are present
- CPLEX pricing solver is disabled as it is incompatible with generic branching
- fix memory issues
- fix bound propagation bugs
- fix bug in knapsack solver
- delete constraints added at presolving after the root node
- check feasibility of current solution in original problem if this fails in the transformed problem
- fix wrong aggregation when using bliss
- print warnings when pricing is aborted
- fix translation of original solution to master problem when pricing problems are aggregated
- better handling of infinite objective values in pricing
 
@section RN200 GCG 2.0
*************************
features
- GCG can now automatically create a decomposition to solve the LP with
  empty pricing problems. See the cons/decomp/createbasicdecomp parameter
- GCG can aggregate pricing problems using bliss which enables us to
  aggregate more pricing problems
- GCG can solve pricing problems in parallel
- GCG uses dual variable smoothing to stabilize dual values
- GCG can branch on integer aggregated problems using Vanderbeck's general
  branching rule
- GCG can solve integer knapsack problems as a dynamic program
- GCG features additional detectors which are able to detect significantly
  more structures such as staircase structures and problems that can be
  aggregated
- improved heuristics
- copy solutions from original problem to master problem
- improved handling of compile flags changes such as an automatic
  recompilation if, e.g., USRFLAGS change
- new solver for pricing problems that uses CPLEX to solve the MIP
  (enabled if LPS=cpx)
 
code cleanup
- moved some detection methods to a more global scope to make them reusable
- added testing framework to do regression testing (uses google test)
- extracted graph methods for reuse
- branching is now done in the master problem
- remove code that was never called
- Rename methods in order to state their intention
- provide a gcg.h file to easily use the most common methods
 
bug fixes
- memory allocation bugs
- bound change propagation fixes
- corrected copyright
- fixed a lot of code checker issues
- use an event handler to disable the master display
- override PARASCIP=true if OPENMP=true
- correct decomp documentation and simplify decomposition interfaces
 
@page RN11 Release notes for GCG 1.1
@section RN110 GCG 1.1
*************************
features
- add staircase structure information
- add staircase structure detection
- the set partitioning detector can create decompositions with one block
- GCG is now separated in a library and a main file so that you can link
  against it
 
bug fixes
- decompositions are now correctly classified
- clean up lots of errors related to inconsistent decompositions
- safe handling of empty problems
- fix detection of identical pricingproblems for aggregation
 
code cleanup
- use DECfilloutDecdecompFromHashmaps where appropriate to remove redundant
  code
- Provide DECfillOutFromConstoblock to enable creation of decomposition
  structures by just specifying constraint to block partition
- Add consistency check function for decompositions
- removed a bit of redundant and leftover code
 
@page RN10 Release notes for GCG 1.0
@section RN100 GCG 1.0
*************************
features
- include variable deletion code
- add a block diagonal detector (cons_connected)
- add a new default constraint based decomposition format with reader (dec)
- added new heuristics gcgrins and xprins
- decompositions from multiple detectors are compared in cons_decomp.h
- added block diagonal detection code, GCG solves these more intelligently
- added detection of standard problems to block detection code
- add additional statistics
- structure information can now contain presolving information
- GCG works with SCIP version 3.0
 
plugins
- reworked decdecomp structure handling
- merge recent SCIP heuristic changes to their GCG counterparts
 
bug fixes
- try to deal with the time limit of the master by looping until the
  original instance hits the time limit
- try to avoid infeasible problems if the timelimit is hit during farkas
  pricing
- fix bugs related to copying master solutions to the original problem
- fix bugs where solutions are not correctly freed
- fix bug: heuristics that use SCIPcopy really create a working copy
- fix propagation bugs
- fix issues with empty problems and problems solved in the root node
- rewrite relaxcolsel heuristic
- moved probing methods to relax_gcg.c and fixed heuristics to use them
- fix a vardata creation bug
- copy cuts in LNS heuristics correctly
- fixed bugs related to presolving
- fixed bugs related to linking variables
- fixed bugs in Ryan-Foster branching
- fix some memory issues
 
code cleanup
- updated the documentation
- cleaned up code (whitespace and code style changes)
- removed all vardata accesses from all files
- removed a lot of old code
- remove dead code and give the code some love
- refactored some parts to remove large methods
- cleaned up detector interface
- make sure code is clean with all our compilers and code checking tools
 
performance
- adjusted default parameters
- improve memory handling by switching to buffer memory in appropriate cases
  and away from buffer in others
 
interface
- make githash look nicer
- nicer decomposition output
 
Makefile and scripts
- add lint directory for static code analysis
- add SCIP target to makefile
- fix scripts for RWTH Aachens high performing cluster
- add possibility to create SCIP link automatically
- add small testset to enable small functionality tests
- add some modes to test script in order to create and collect
  decompositions
- fix clean rule to a safer version
 
 
@page RN09 Release notes for GCG 0.9
@section RN090 GCG 0.9
*************************
features
- included new heuristics
- included new reader for the ref file format
- added support for linking variables
- added generalized reliability branching using probing
- added constraint handler to enforce integral original variables
- allow for unbounded pricing problems
- branch also on pseudosolutions
- support probing for heuristics
- GCG works with SCIP version 2.0
 
bug fixes
- fixed multiple bugs related to timing issues
- fixed bugs related to working with the presolved problem
 
interface
- allow master to be accessed from the command line interface
- Change branding in interactive SHELL, display version and githash
- added more extensive test framework
- added gnuplot visualization reader
- added much more extensive documentation
 
 
@page RN08 Release notes for GCG 0.8
@section RN081 GCG 0.8.1
*************************
features
- polished source code
 
bug fixes
- some
 
 
@section RN080 GCG 0.8
*************************
bugfixes
- fixed some bugs for solving MIPs when branching on variables that were
  directly transferred to the master problem
 
@page RN07 Release notes for GCG 0.7
@section RN070 GCG 0.7
*************************
bugfixes
- some bugfixes
 
@page RN06 Release notes for GCG 0.6
@section RN060 GCG 0.6
*************************
feastures
- implemented dialog handler for GCG
- added concept of pricing solvers
- statistics about pricing are displayed at the end of solving
 
bugfixes
- quite a few
 
@page RN05 Release notes for GCG 0.5
@section RN050 GCG 0.5
*************************
bugfixes
- fixed problems with transfering bounds from the original program to the
  master program: when propagating a node, the bounds of all variables in
  the pricing problem and variables copied to the master are adjusted, for
  all master variables created by the pricer, it is checked whether they
  fulfill the current bounds
- fixed bug when disabling discretization approach
 
@page RN04 Release notes for GCG 0.4
@section RN040 GCG 0.4
*************************
design
- working SCIP represents the original problem
- read in problem is standard format (e.g., .lp-file, .mps-file) and
  corresponding blk-file
- the master problem is represented by a relaxator, which replaces the LP-solving
- separation is done by a separator included in the master SCIP, which calls the
  SCIPseparateSol() method in the original SCIP
- branching is done simultaneously in the master and in the original SCIP
- variables in the master are extreme points of conv(X) (and extreme rays, but
  functionality currently not implemented) -> convexification approach
- many identical pricing problems -> fat too much effort for pricing,
  especially farkas pricing!
- 2 constraint handler assure that nodes in the master SCIP are linked to
  nodes in the original SCIP and vice versa
- branching rules are implemented as branching rules in the master that
  have to define the additional callbacks specified in "type_branchgcg.h"
 
features
- in blk-file constraints can be forced to be copied to the master problem;
  all other constraints are added to a block, if they only contain variables
  of this block
- added possibility to use discretization approach, variables in the
  master then represent integer points in X, integrality in the master is
  demanded
- identification of identical blocks -> break symmetrie in the master
- 2 branching rules implemented so far:
  * branching on original variables (not possible if variable belongs to a
    block that has similar blocks in the problem), using pseudocost values
    to choose the variable to branch on
  * ryan-foster type of branching for identical blocks with set partitioning
    structure
- added GCGs own display plugin showing the number of LP iterations, of
  constraints, variables and cuts in the master*/