Changeset 2140 for stable


Ignore:
Timestamp:
Feb 22, 2015 4:04:41 PM (4 years ago)
Author:
tkr
Message:

Merging r2138 and r2139 from trunk

Location:
stable/2.9
Files:
3 edited
1 copied

Legend:

Unmodified
Added
Removed
  • stable/2.9

  • stable/2.9/Cbc

  • stable/2.9/Cbc/README

    r1939 r2140  
    1 CBC README
    2 ==========
     1# CBC Version 2.9.2 README
    32
    43Welcome to the README for the COIN Branch and Cut Solver (CBC). CBC is
     
    76be redistributed freely.
    87
    9 DOCUMENTATION
    10 =============
    11 
    12 For a quick start guide, please see the INSTALL file in this distribution. A (somehwat outdated) user's manual is available here:
     8## DOCUMENTATION
     9
     10For a quick start guide, please see the INSTALL file in this distribution. A
     11(somehwat outdated) user's manual is available here:
    1312
    1413http://www.coin-or.org/Cbc
     
    2322http://projects.coin-or.org/Cbc
    2423
    25 WHAT'S NEW
    26 ==========
    27 
    28 Release 2.8.3:
    29 
    30 1. Fix for handling SOS.
    31 
    32 Release 2.8.2:
    33 
    34 1. Fixed recognition of Glpk source in main configure.
    35 
    36 2. Minor bugfixes in CoinUtils, Clp, and Cbc.
    37 
    38 Release 2.8.1:
    39 
    40    Ted, please fill this in!
    41 
    42 Release 2.8.0:
    43 
    44 1. Introduced new secondaryStatus 8 to indicate that solving stopped due to an iteration limit.
    45 
    46 2. Solution pool is now accessible via the command line and the CbcMain* interface.
    47 
    48 3. New mipstart option to read an initial feasible solution from a file. Only values for discrete
    49    variables need to be provided.
    50 
    51 4. Added Proximity Search heuristic by Fischetti and Monaci (off by default):
    52    The simplest way to switch it on using stand-alone version is "-proximity on".
    53 
    54    Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement heuristic recently proposed by
    55    Fischetti and Monaci (2012). The idea is to define a sub-MIP without additional constraints but with a
    56    modified objective function intended to attract the search in the proximity of the incumbent. The approach
    57    works well for 0-1 MIPs whose solution landscape is not too irregular (meaning the there is reasonable
    58    probability of finding an improved solution by flipping a small number of binary variables), in particular
    59    when it is applied to the first heuristic solutions found at the root node.
    60    
    61 5. An implementation of Zero-Half-Cuts by Alberto Caprara is now available.
    62    By default, these cuts are off.  To use add to your command line -zerohalfCuts root (or other options) or just -zero.
    63    So far, they may help only on a small subset of problems and may need some tuning.
    64 
    65    The implementation of these cuts is described in
    66    G. Andreello, A. Caprara, and M. Fischetti
    67    "Embedding Cuts in a Branch and Cut Framework: a Computational Study with {0,1/2}-Cuts"
    68    INFORMS Journal on Computing 19(2), 229-238, 2007
    69    http://dx.doi.org/10.1287/ijoc.1050.0162
    70 
    71 6. An alternative implementation of a reduce and split cut generator by Giacomo Nannicini is now available.
    72    By default, these cuts are off.  To use add to your command line -reduce2AndSplitCuts root (or other options).
    73 
    74    The implementation of these cuts is described in
    75    G. Cornuejols and G. Nannicini
    76    "Practical strategies for generating rank-1 split cuts in mixed-integer linear programming"
    77    Mathematical Programming Computation 3(4), 281-318, 2011
    78    http://dx.doi.org/10.1007/s12532-011-0028-6
    79 
    80 7. An alternative robust implementation of a Gomory cut generator by Giacomo Nannicini is now available.
    81    By default, these cuts are off.  To use add to your command line -GMI root (or other options).
    82 
    83    The implementation of these cuts is described in
    84    G. Cornuejols, F. Margot, and G. Nannicini
    85    "On the safety of Gomory cut generators"
    86    http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications
    87 
    88 8. To encourage the use of some of the more exotic/expensive cut generators a parameter -slowcutpasses has been added.
    89    The idea is that the code does these cuts just a few times - less than the more usual cuts.  The default is 10.
    90    The cut generators identified by "may be slow" at present are just Lift and project and ReduceAndSplit (both versions).
    91    
    92 9. Allow initialization of random seed by user.  Pseudo-random numbers are used in Cbc and Clp.  In Clp they
    93    are used to break ties in degenerate problems, while in Cbc heuristics such as the Feasibility Pump use them   
    94    to decide whether to round up or down.  So if a different pseudo-random seed is given to Clp then you may get
    95    a different continuous optimum and so different cuts and heuristic solutions. This can be switched on by
    96    setting randomSeed for Clp and/or randomCbcSeed for Cbc.  The special value of 0 tells code to use time of day
    97    for initial seed.
    98    
    99 10. Building on this idea, Andrea Lodi, Matteo Fischetti, Michele Monaci, Domenico Salvagnin, Yuji Shinano, and Andrea Tramontani
    100    suggest that this idea be improved by running at the root node with multiple copies of solver, each
    101    with its own different seed and then passing in the solutions and cuts so that the main solver has a richer
    102    set of solutions and possibly stronger cuts.  This is switched on by setting -multipleRootPasses.  These can also
    103    be done in parallel.
    104  
    105 11. Few changes to presolve for special variables and badly scaled problems (in CoinUtils).
    106 
    107 12. New option -extraVariables <number> which switches on a trivial re-formulation that introduces extra integer variables
    108     to group together variables with same cost.
    109 
    110 13. For some problems, cut generators and general branching work better if the problem would be infeasible if the cost is too high.
    111     If the new option -constraintFromCutoff is set, the objective function is added as a constraint which rhs is set to the current
    112     cutoff value (objective value of best known solution).
    113 
    114 Release 2.7.8:
    115    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.7&new_path=%2Freleases%2F2.7.8 to see all changes.
    116 
    117 1. Change message when LP simplex iteration limit is hit from "Exiting on maximum nodes"
    118    to "Exiting on maximum number of iterations"
    119 
    120 2. Fix for using overlapping SOS.
    121 
    122 3. Fixes in buildsystem.
    123 
    124 Release 2.7.7:
    125    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.6&new_path=%2Freleases%2F2.7.7 to see all changes.
    126 
    127 1. Fix to report interruption on user event if SIGINT is received by CbcSolver.
    128    model->status() should now be 5 if this event happened.
    129    Added method CbcModel::sayEventHappened() to make cbc stop due to an 'user event'.
    130 
    131 2. Other minor fixes.
    132 
    133 Release 2.7.6:
    134    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.5&new_path=%2Freleases%2F2.7.6 to see all changes.
    135 
    136 1. Fixes to build system.
    137 
    138 2. Other minor fixes.
    139 
    140 Release 2.7.5:
    141    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.4&new_path=%2Freleases%2F2.7.5 to see all changes.
    142 
    143 1. Fixes to get AMPL interface working again.
    144 
    145 2. More fixes to MSVC++ files.
    146 
    147 Release 2.7.4:
    148    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.3&new_path=%2Freleases%2F2.7.4 to see all changes.
    149 
    150 1. Minor bugfixes.
    151 
    152 Release 2.7.3:
    153    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.2&new_path=%2Freleases%2F2.7.3 to see all changes.
    154 
    155 1. Minor bugfixes.
    156 
    157 2. Fixes to MSVC++ files.
    158 
    159 Release 2.7.2:
    160    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.1&new_path=%2Freleases%2F2.7.2 to see all changes.
    161 
    162 1. Allow row/column names for GMPL models.
    163 
    164 2. Added CbcModel::haveMultiThreadSupport() to indicate whether Cbc library has been compiled with multithread support.
    165 
    166 3. Added CbcModel::waitingForMiniBranchAndBound() to indicate whether sub-MIP heuristic is currently running.
    167 
    168 4. Cbc shell should work with readline if configured with --enable-gnu-packages.
    169 
    170 5. Support for compressed input files (.gz, .bz2) is now enabled by default.
    171 
    172 6. Fix problems with relative gap tolerance > 100% and further bugs.
    173 
    174 7. Fixes for MSVC++ Version 9 files.
    175 
    176 8. Minor fixes in buildsystem; update to BuildTools 0.7.1.
    177 
    178 Release 2.7.1:
    179    Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.0&new_path=%2Freleases%2F2.7.1 to see all changes.
    180 
    181 1. Fixes to MSVC++ files
    182 
    183 Release 2.7.0:
    184 
    185 1. License has been changed to the EPL.
    186 
    187 2. Support for MSVC++ version 10 added.
    188 
    189 3. Support for BuildTools version 0.7 to incorporate recent enhancements,
    190 including proper library versioning in Linux, prohibiting installation of
    191 private headers, etc.
    192 
    193 4. Updated externals to new stable versions of dependent projects.
    194 
    195 5. Improvements to heuristics.
    196 
    197 6. New options for cut generation.
    198 
    199 7. Improved reporting of results.
    200 
    201 8. Improvements to documentation.
    202 
    203 9. Minor bug fixes.
    204 
    205 SUPPORT
    206 =======
    207 
    208 1. List Serve
     24## SUPPORT
     25
     26### List Serve
    20927
    21028CBC users should use the Cbc mailing list. To subscribe, go to
    21129http://list.coin-or.org/mailman/listinfo/cbc
    21230
    213 3. Bug Reports
     31### Bug Reports
    21432
    21533Bug reports should be reported on the CBC development web site at
    21634
    21735https://projects.coin-or.org/Cbc/newticket
     36
     37## CHANGELOG
     38
     39 * Release 5.9.2
     40
     41   * Fix for proper installation with {{{DESTDIR}}}
     42
     43 * Release 5.9.1
     44
     45   * Fix for dependency linking
     46   * Minor bug fixes
     47
     48 * Release 5.9.0
     49   * Major algorithmic improvements
     50
     51 * Release 5.8.13
     52   * Improved message handling
     53   * Miscellaneous bug fixes.
     54
     55 * Release 5.8.12
     56   * Update for dependencies.
     57
     58 * Release 5.8.11
     59   * Major overhaul of C interface
     60   * Fixes to SOS
     61   * Miscellaneous bug fixes
     62
     63 * Release 5.8.10
     64   * More changes related to thread safety.
     65   * Fix bug in build system with Visual Studio compiler.
     66   * Miscellaneous bug fixes.
     67
     68 * Release 5.8.9
     69   * Attempt to make Cbc thread safe.
     70   * Add parallel examples.
     71   * Add CbcSolverUsefulInfo.
     72   * Bug fixes.
     73
     74 * Release 5.8.8
     75
     76   * Added example to show how to use Cbc with installed libraries in MSVC++
     77   * Fixed inconsistency in addition of libCbcSolver to dependencies in
     78     {{{cbc_addlibs.txt}}}.
     79
     80 * Release 5.8.7
     81
     82   * Changed so that Doxygen builds LaTex
     83   * Fixes for build system
     84
     85 * Release 5.8.6
     86
     87   * Added option to explicitly link dependencies to comply with packaging
     88     requirements on Fedora and Debian, as well as allow building of MinGW
     89     DLLs.
     90
     91 * Release 5.8.5
     92   * Minor fixes to build system
     93
     94 * Release 5.8.4
     95   * Small bug fixes
     96   * Upgrades to build system
     97
     98 * Release 2.8.3:
     99
     100   * Fix for handling SOS.
     101
     102 * Release 2.8.2:
     103
     104   * Fixed recognition of Glpk source in main configure.
     105   * Minor bug fixes in CoinUtils, Clp, and Cbc.
     106
     107 * Release 2.8.1:
     108
     109   * Minor bug fixes
     110
     111 * Release 2.8.0:
     112
     113   * Introduced new secondaryStatus 8 to indicate that solving stopped due to
     114     an iteration limit.
     115   * Solution pool is now accessible via the command line and the CbcMain*
     116     interface.
     117   * New mipstart option to read an initial feasible solution from a file.
     118     Only values for discrete variables need to be provided.
     119
     120   * Added Proximity Search heuristic by Fischetti and Monaci (off by
     121     default): The simplest way to switch it on using stand-alone version is
     122     ```-proximity on```.
     123
     124     Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement
     125     heuristic recently proposed by Fischetti and Monaci (2012). The idea is
     126     to define a sub-MIP without additional constraints but with a modified
     127     objective function intended to attract the search in the proximity of the
     128     incumbent. The approach works well for 0-1 MIPs whose solution landscape
     129     is not too irregular (meaning the there is reasonable probability of
     130     finding an improved solution by flipping a small number of binary
     131     variables), in particular when it is applied to the first heuristic
     132     solutions found at the root node.
     133   
     134   * An implementation of Zero-Half-Cuts by Alberto Caprara is now available.
     135     By default, these cuts are off. To use add to your command line
     136     -zerohalfCuts root (or other options) or just -zero. So far, they may
     137     help only on a small subset of problems and may need some tuning.
     138
     139     The implementation of these cuts is described in G. Andreello, A.
     140     Caprara, and M. Fischetti "Embedding Cuts in a Branch and Cut Framework:
     141     a Computational Study with {0,1/2}-Cuts" INFORMS Journal on Computing
     142     19(2), 229-238, 2007 http://dx.doi.org/10.1287/ijoc.1050.0162
     143
     144   * An alternative implementation of a reduce and split cut generator by
     145     Giacomo Nannicini is now available. By default, these cuts are off. To
     146     use add to your command line -reduce2AndSplitCuts root (or other
     147     options).
     148
     149     The implementation of these cuts is described in G. Cornuejols and G.
     150     Nannicini "Practical strategies for generating rank-1 split cuts in
     151     mixed-integer linear programming" Mathematical Programming Computation
     152     3(4), 281-318, 2011 http://dx.doi.org/10.1007/s12532-011-0028-6
     153
     154   * An alternative robust implementation of a Gomory cut generator by Giacomo
     155     Nannicini is now available. By default, these cuts are off. To use add to
     156     your command line -GMI root (or other options).
     157
     158     The implementation of these cuts is described in G. Cornuejols, F.
     159     Margot, and G. Nannicini "On the safety of Gomory cut generators"
     160     http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications
     161
     162   * To encourage the use of some of the more exotic/expensive cut generators
     163     a parameter -slowcutpasses has been added. The idea is that the code does
     164     these cuts just a few times - less than the more usual cuts. The default
     165     is 10. The cut generators identified by "may be slow" at present are just
     166     Lift and project and ReduceAndSplit (both versions).
     167   
     168   * Allow initialization of random seed by user. Pseudo-random numbers are
     169     used in Cbc and Clp. In Clp they are used to break ties in degenerate
     170     problems, while in Cbc heuristics such as the Feasibility Pump use them
     171     to decide whether to round up or down. So if a different pseudo-random
     172     seed is given to Clp then you may get a different continuous optimum and
     173     so different cuts and heuristic solutions. This can be switched on by
     174     setting randomSeed for Clp and/or randomCbcSeed for Cbc. The special
     175     value of 0 tells code to use time of day for initial seed.
     176   
     177   * Building on this idea, Andrea Lodi, Matteo Fischetti, Michele Monaci,
     178     Domenico Salvagnin, Yuji Shinano, and Andrea Tramontani suggest that this
     179     idea be improved by running at the root node with multiple copies of
     180     solver, each with its own different seed and then passing in the
     181     solutions and cuts so that the main solver has a richer set of solutions
     182     and possibly stronger cuts. This is switched on by setting
     183     -multipleRootPasses. These can also be done in parallel.
     184 
     185   * Few changes to presolve for special variables and badly scaled problems
     186     (in CoinUtils).
     187
     188   * New option -extraVariables <number> which switches on a trivial
     189    re-formulation that introduces extra integer variables to group together
     190    variables with same cost.
     191
     192   * For some problems, cut generators and general branching work better if
     193     the problem would be infeasible if the cost is too high. If the new
     194     option -constraintFromCutoff is set, the objective function is added as a
     195     constraint which rhs is set to the current cutoff value (objective value
     196     of best known solution).
     197
     198 * Release 2.7.8:
     199
     200   * Change message when LP simplex iteration limit is hit from "Exiting on
     201     maximum nodes" to "Exiting on maximum number of iterations"
     202   * Fix for using overlapping SOS.
     203   * Fixes in buildsystem.
     204
     205 * Release 2.7.7:
     206
     207   * Fix to report interruption on user event if SIGINT is received by
     208     CbcSolver. model->status() should now be 5 if this event happened. Added
     209     method CbcModel::sayEventHappened() to make cbc stop due to an 'user
     210     event'.
     211
     212   * Other minor fixes.
     213
     214 * Release 2.7.6:
     215
     216   * Fixes to build system.
     217
     218   * Other minor fixes.
     219
     220 * Release 2.7.5:
     221
     222   * Fixes to get AMPL interface working again.
     223
     224   * More fixes to MSVC++ files.
     225
     226 * Release 2.7.4:
     227
     228   * Minor bugfixes.
     229
     230 * Release 2.7.3:
     231
     232   * Minor bugfixes.
     233
     234   * Fixes to MSVC++ files.
     235
     236 * Release 2.7.2:
     237
     238   * Allow row/column names for GMPL models.
     239
     240   * Added CbcModel::haveMultiThreadSupport() to indicate whether Cbc library
     241     has been compiled with multithread support.
     242
     243   * Added CbcModel::waitingForMiniBranchAndBound() to indicate whether
     244     sub-MIP heuristic is currently running.
     245
     246   * Cbc shell should work with readline if configured with
     247     ```--enable-gnu-packages```.
     248
     249   * Support for compressed input files (.gz, .bz2) is now enabled by default.
     250
     251   * Fix problems with relative gap tolerance > 100% and further bugs.
     252
     253   * Fixes for MSVC++ Version 9 files.
     254
     255   * Minor fixes in buildsystem; update to BuildTools 0.7.1.
     256
     257 * Release 2.7.1:
     258
     259   * Fixes to MSVC++ files
     260
     261 * Release 2.7.0:
     262
     263   * License has been changed to the EPL.
     264
     265   * Support for MSVC++ version 10 added.
     266
     267   * Support for BuildTools version 0.7 to incorporate recent enhancements,
     268     including proper library versioning in Linux, prohibiting installation of
     269     private headers, etc.
     270
     271   * Updated externals to new stable versions of dependent projects.
     272
     273   * Improvements to heuristics.
     274
     275   * New options for cut generation.
     276
     277   * Improved reporting of results.
     278
     279   * Improvements to documentation.
     280
     281   * Minor bug fixes.
     282
     283
Note: See TracChangeset for help on using the changeset viewer.