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