Changes between Version 11 and Version 12 of CBCCodeOrganization


Ignore:
Timestamp:
Dec 6, 2009 10:58:08 PM (12 years ago)
Author:
dfylstra
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • CBCCodeOrganization

    v11 v12  
    3939Heuristics can either find, or (by fixing variables etc.) help find integer solutions early.  CBC has a class for each heuristic, derived from the base class CbcHeuristic which is defined in CbcHeuristic.hpp.  The base class defines some common options/controls that determine how often the heuristic should be run.  It also defines the methods solution() - called to execute the heuristic, shouldHeurRun() - a lightweight test to determine whether the heuristic is worth running at this node, and smallBranchAndBound() which is discussed below.
    4040
    41 Three special heuristic classes are defined in CbcHeuristic.hpp:  CbcRounding, CbcHeuristicPartial and CbcSerendipity.  Others are defined in their own .hpp and .cpp files: CBCHeuristicDive, CBCHeuristicDiveCoefficient, CBCHeuristicDiveFractional, CBCHeuristicDiveGuided, CBCHeuristicDiveLineSearch, CBCHeuristicDivePseudoCost, CBCHeuristicDiveVectorLength, CBCHeuristicFPump (the Feasibility Pump), CBCHeuristicGreedy, CBCHeuristicLocal, CBCHeuristicPivotAndFix, CBCHeuristicRandRound, and CBCHeuristicRINS (Relaxation Induced Neighborhood Search).
     41Three special heuristic classes are defined in CbcHeuristic.hpp:  CbcRounding, CbcHeuristicPartial and CbcSerendipity.  Others are defined in their own .hpp and .cpp files: CBCHeuristicDive, CBCHeuristicDiveCoefficient, CBCHeuristicDiveFractional, CBCHeuristicDiveGuided, CBCHeuristicDiveLineSearch, CBCHeuristicDivePseudoCost, CBCHeuristicDiveVectorLength, CBCHeuristicFPump (the Feasibility Pump), CBCHeuristicGreedy, CBCHeuristicLocal, CBCHeuristicPivotAndFix, CBCHeuristicRandRound, and four heuristics originally in CBCHeuristicRINS.cpp (Relaxation Induced Neighborhood Search): CBCHeuristicRINS, CBCHeuristicRENS, CBCHeuristicDINS and CBCHeuristicVND.
    4242
    4343Heuristics that successfully fix several variables, thereby creating a smaller problem, will call the CbcHeuristic method smallBranchAndBound(), which does a "small/inner" Branch and Bound search starting from the heuristic result, seeking a new integer solution.  Again there must be enough fixing to make the problem materially smaller; the test is new(rows+columns)/old(rows+columns) < fractionSmall_, adjusted by a multiplier for large problems.  This "inner" Branch and Bound explores at most numberNodes_ (default 200).