source: trunk/README.md @ 2566

Last change on this file since 2566 was 2566, checked in by stefan, 6 months ago

fix last readme change

  • nodelimit did not change, just solution limit, and that's of little interest
File size: 19.5 KB
Line 
1# CBC
2
3Cbc (*C*oin-or *b*ranch and *c*ut) is an open-source mixed integer linear programming solver written in C++.
4It can be used as a callable library or using a stand-alone executable.
5It can be called through
6AIMMS (through the [AIMMSlinks](https://github.com/coin-o/AIMMSlinks) project),
7AMPL (natively),
8[CMPL](https://github.com/coin-or/Cmpl),
9GAMS (through the [GAMSlinks](https://github.com/coin-or/GAMSlinks) project),
10[JuMP](https://github.com/JuliaOpt/JuMP.jl),
11Mathematica,
12[MiniZinc](http://www.minizinc.org/),
13MPL (through the [CoinMP](https://github.com/coin-or/CoinMP) project),
14[PuLP](https://github.com/coin-or/PuLP), and
15[OpenSolver for Excel](http://opensolver.org), among others.
16
17Cbc links to a number of other COIN-OR projects for additional functionality, including:
18 * [Clp](https://github.com/coin-or/Clp) (the default solver for LP relaxations)
19 * [Cgl](https://github.com/coin-or/Cgl) (for cut generation)
20 * [CoinUtils](https://github.com/coin-or/CoinUtils) (for reading input files and various utilities)
21For more information on supported platforms, links to dependent projects, current version, and more, click [here](http://www.coin-or.org/projects/Cbc.xml)
22
23Cbc is developed by [John Forrest](http://www.fastercoin.com), now retired from IBM Research.
24The project is currently managed by John Forrest, [Ted Ralphs](http://coral.ie.lehigh.edu/~ted/), Haroldo Gambini Santos, and the rest of the Cbc team (Dan Fylstra (Frontline), Lou Hafer (SFU), Bill Hart (Sandia), Bjarni Kristjannson (Maximal), Cindy Phillips (Sandia), Matthew Saltzman (Clemson), Edwin Straver (Frontline), Jean-Paul Watson (Sandia)).
25
26Cbc is written in C++ and is released as open source code under the [Eclipse Public License (EPL)](http://www.opensource.org/licenses/eclipse-1.0) and is freely redistributable.
27All source code and documentation is Copyright IBM and others. This README may be redistributed freely.
28
29Cbc is available from the [COIN-OR initiative](http://www.coin-or.org/).
30The Cbc website is https://github.com/coin-or/Cbc.
31
32## CITE
33
34[![DOI](https://zenodo.org/badge/30382416.svg)](https://zenodo.org/badge/latestdoi/30382416)
35
36## CURRENT BUILD STATUS
37
38[![Build Status](https://travis-ci.org/coin-or/Cbc.svg?branch=master)](https://travis-ci.org/coin-or/Cbc)
39
40[![Build status](https://ci.appveyor.com/api/projects/status/l2hwifsxwhswng8y/branch/master?svg=true)](https://ci.appveyor.com/project/tkralphs/cbc/branch/master)
41
42
43## DOWNLOAD
44
45Binaries for most platforms are available for download from [Bintray](https://bintray.com/coin-or/download/Cbc): [ ![Download](https://api.bintray.com/packages/coin-or/download/Cbc/images/download.svg) ](https://bintray.com/coin-or/download/Cbc/2.10)
46
47 * *Linux*: On !Debian/Ubuntu, Cbc is available in the package `coinor-cbc` and can be installed with apt. On Fedora, Cbc is available in the package `coin-or-Cbc`.
48 * *Windows*: The easiest way to get Cbc on Windows is to download the Windows installer for the [COIN-OR Optimization Suite](http://www.coin-or.org/download/binary/CoinAll), which provides Visual Studio compatible libraries and binaries.
49 * *Mac OS X*: The easiest way to get Cbc on Mac OS X is through Homebrew
50   * `brew tap coin-or-tools/coinor`
51   * `brew install cbc`
52 * AMPL also provides stand-alone [Cbc executables](http://ampl.com/products/solvers/open-source/#cbc) that can be used with (or without) AMPL.
53 * The [GAMS](http://www.gams.com) distribution includes Cbc.
54Due to license incompatibilities, pre-compiled binaries lack some functionality.
55If binaries are not available for your platform for the latest version and you would like to request them to be built and posted, feel free to let us know on the mailing list.
56
57*Source code* can be obtained either by
58
59 * Downloading a snapshot of the source code for the latest release version of Cbc from the [Cbc source code download page](http://www.coin-or.org/download/source/Cbc), or
60 * Checking out the code from [Github](https://github.com/coin-or/Cbc)
61
62The recommended method is to use Git because it makes it easier to obtain updates. Below are some quick start guides for building on common platforms. *More detailed build instructions are [BuildAndInstall here].*
63
64
65## BUILDING from source
66
67### Using CoinBrew
68
69To build Cbc from source, obtain the `coinbrew` script from
70https://coin-or.github.io/coinbrew/
71and run
72
73
74    /path/to/coinbrew fetch --main-proj=Cbc
75    /path/to/coinbrew build --main-proj=Cbc --test
76    /path/to/coinbrew install --main-proj=Cbc
77
78
79The `coinbrew` script will fetch [these](Dependencies) additional projects.
80
81### Without CoinBrew (Expert users)
82
83 0. Install [these Dependencies](Dependencies)
84 1. Obtain the source code, e.g., from https://github.com/coin-or/Cbc
85 2. Run `./configure -C` to generate makefiles
86 3. Run `make` to build the CoinUtils library
87 4. Run `make test` to build and run the CoinUtils unit test program
88 5. Run `make install` to install library and header files.
89
90### With Microsoft Visual Studio
91
92For Microsoft Visual C++ users, there are project files for version 10 available in the `MSVisualStudio` directory.
93First, obtain the source code using either a Windows git client or download a snapshot.
94In MSVC++ Version 10, open the solution file (this should be converted to whatever version of MSVC+ you are using) and build the Cbc project.
95The code should build out of the box with default settings.
96
97It is also possible to build Cbc with the Visual Studio compiler from the command line using the procedure for Unix-like environments, using the Msys2 shell or CYGWIN.
98This is the recommended and best-supported way of building Cbc in Windows from source.
99
100If you want to build a *parallel version* of CBC using Visual Studio you can following instructions: (thanks to Tobias Stengel and Alexis Guigue).
101
102Assumptions:
103
104- A VS solution with all necessary projects (libCbc, libClp, libCbcSolver, libCgl, libCoinUtils, libOsi, libOsiCbc, libOsiClp). The project files can be found inside the "MSVisualStudio" folders.
105
106Steps (based on VS 2013):
107
1081. for each of the lib* projects do:
109   add `CBC_THREAD` under Properties -> Configuration Properties -> C/C++ -> Preprocessor -> Preprocessor Definitions (a subset of the lib* projects may be sufficient, but it doesn't hurt to do it for all)
110
1112. Link against a pthreads library.
112   [PThreadsWin32](https://www.sourceware.org/pthreads-win32/) works (even in 64 bits systems) and is distributed under the LGPL.
113   If you decide to use the precompiled binaries: both pthreadVC2 and pthreadVS2 seem to work.
114   Otherwise: third party VS project files for pthreads4win can be found on github.
115
116   Note: If you use C++/Cli, make sure that no callback (eventHandlers, custom cut generators, custom heuristics, ...) contains managed code.
117   Otherwise your code will crash at runtime with AssembyNotFoundExceptions inside the native threads created by Cbc. Even if not, problems with the GC are likely.
118
1193. If you link statically against pthreads4win, you have to define PTW32_STATIC_LIB when building your program/Cbc (e.g. via Properties -> C/C++/Preprocessor ->  Preprocessor Definitions) AND - only if you build pthreads yourself - when building pthreads.
120   Linking pthreads dynamically works without additional preprocessor definitions.
121
1224. pass "-threads" "yourNumber" to CbcMain1
123
124
125## DOCUMENTATION
126
127 * [INSTALL](INSTALL) file (partially outdated)
128 * [User's Guide](https://coin-or.github.io/Cbc) (from 2005)
129 * [Doxygen generated documentation](http://www.coin-or.org/Doxygen/Cbc/hierarchy.html)
130 * Source code [examples](Cbc/examples)
131 * [Cbc command-line guide](https://projects.coin-or.org/CoinBinary/export/1059/OptimizationSuite/trunk/Installer/files/doc/cbcCommandLine.pdf)
132
133
134## SUPPORT
135
136### List Serve
137
138CBC users should use the Cbc mailing list. To subscribe, go to
139http://list.coin-or.org/mailman/listinfo/cbc
140
141### Bug Reports
142
143Bug reports should be reported on the CBC development web site at
144
145https://github.com/coin-or/Cbc/issues
146
147## CHANGELOG
148
149 * Release 2.10.3 (in preparation)
150   * Improve performance of some primal heuristics, incl. feasibility pump, by making integer slacks continuous
151   * Bugfixes
152
153 * Release 2.10.2
154   * Bugfixes
155
156 * Release 2.10.1
157   * Fixed Cbc_clone in C interface
158   * Fixed CbcMain1() call in examples/driver3.cpp
159   * Fixed possible issue with MIPstart if presolve added variables
160   * More minor bugfixes
161
162 * Release 2.10.0
163   * Improved handling of SOS, starting point, and symmetries
164   * Improved performance of primal heuristics regarding the handling of
165     implicit integer variables
166   * Mini-B&B is now disabled when solving with multiple threads
167   * Changed default value for zero half cuts parameter from off to ifmove
168   * Added CbcModel::postProcessedSolver() to obtained LP after presolve
169   * New option "PrepNames" to indicate whether column names should be
170     kept in the pre-processed model
171   * New option "sosPrioritize" to determine how to prioritize SOS
172   * Added new event "generatedCuts"
173   * CbcSolver can now read compressed .lp files (GZIP, BZIP2)
174   * New functions in the C interface: Cbc_readLp, Cbc_writeLp,
175     Cbc_addCol, Cbc_addRow, Cbc_getNumIntegers, Cbc_bestSolution,
176     Cbc_getObjValue, Cbc_getRowNz, Cbc_getRowIndices, Cbc_getRowCoeffs,
177     Cbc_getRowRHS, Cbc_getRowSense, Cbc_getColNz, Cbc_getColIndices,
178     Cbc_getColCoeffs, Cbc_getReducedCost, Cbc_numberSavedSolutions,
179     Cbc_savedSolution, Cbc_savedSolutionObj, Cbc_setMIPStart,
180     Cbc_setMIPStartI, Cbc_addCutCallback, Osi_getNumCols, Osi_getColName,
181     Osi_getColLower, Osi_getColUpper, Osi_isInteger, Osi_getNumRows,
182     Osi_getRowNz, Osi_getRowIndices, Osi_getRowCoeffs, Osi_getRowRHS,
183     Osi_getRowSense, Osi_getColSolution, OsiCuts_addRowCut,
184     Cbc_getAllowableGap, Cbc_setAllowableGap, Cbc_getAllowableFractionGap,
185     Cbc_setAllowableFractionGap, Cbc_getAllowablePercentageGap,
186     Cbc_setAllowablePercentageGap, Cbc_getCutoff, Cbc_setCutoff,
187     Cbc_getMaximumNodes, Cbc_setMaximumNodes, Cbc_getMaximumSolutions,
188     Cbc_setMaximumSolutions, Cbc_getLogLevel, Cbc_setLogLevel,
189     Cbc_getMaximumSeconds, Cbc_setMaximumSeconds
190   * New action "guess" checks properties of the model to decide the best
191     parameters for solving the LP relaxation.
192   * New example inc.cpp to illustrate solution callback
193   * New example driver5.cpp to illustrate user-defined branching rule
194   * New example clpdriver.cpp to illustrate use of ClpEventHandler
195   * Added support for using OsiHiGHS with CbcGeneric
196   * Added MSVC 14 project files
197   * Bugfixes
198
199 * Release 2.9.10
200   * Fix a numerical issue
201   * Fix some memory leaks
202   * Fix issue when root node is obviously infeasible
203   * Performance improvements for mini-B&B
204   * Fix name of bound in final message
205   * Fix names in preprocessed problem
206
207 * Release 2.9.9
208
209   * Fixes for SOS2
210   * Updates to mipstart
211   * Switching to new build system
212   * Updates for CI
213
214 * Release 2.9.8
215
216   * Update to most current releases of dependencies
217   * Small bug fixes
218   * Add support for automatic build and test with Travis and Appveyor
219
220 * Release 2.9.7
221
222   * Small bug fixes
223   * Option to switch to line buffered output
224
225 * Release 2.9.6
226
227   * Small bug fixes
228
229 * Release 2.9.5
230
231   * Small bug fixes
232
233 * Release 2.9.4
234
235   * Small fixes for stability
236   * Fixes for Doygen documentation generation
237
238 * Release 2.9.3
239
240   * Minor bug fixes
241
242 * Release 2.9.2
243
244   * Fix for proper installation with ```DESTDIR```
245
246 * Release 2.9.1
247
248   * Fix for dependency linking
249   * Minor bug fixes
250
251 * Release 2.9.0
252
253   * Introduced specialized branching methods for dealing with "big Ms".
254   * Introduced new methods for dealing with symmetry (requires installation of [nauty](http://pallini.di.uniroma1.it/))
255   * Introduction of conflict cuts (off by default, turn on with `-constraint conflict`)
256
257 * Release 2.8.13
258
259   * Improved message handling
260   * Miscellaneous bug fixes.
261
262 * Release 2.8.12
263
264   * Update for dependencies.
265
266 * Release 2.8.11
267
268   * Major overhaul of C interface
269   * Fixes to SOS
270   * Miscellaneous bug fixes
271
272 * Release 2.8.10
273
274   * More changes related to thread safety.
275   * Fix bug in build system with Visual Studio compiler.
276   * Miscellaneous bug fixes.
277
278 * Release 2.8.9
279
280   * Attempt to make Cbc thread safe.
281   * Add parallel examples.
282   * Add CbcSolverUsefulInfo.
283   * Bug fixes.
284
285 * Release 2.8.8
286
287   * Added example to show how to use Cbc with installed libraries in MSVC++
288   * Fixed inconsistency in addition of libCbcSolver to dependencies in
289     {{{cbc_addlibs.txt}}}.
290
291 * Release 2.8.7
292
293   * Changed so that Doxygen builds LaTex
294   * Fixes for build system
295
296 * Release 2.8.6
297
298   * Added option to explicitly link dependencies to comply with packaging
299     requirements on Fedora and Debian, as well as allow building of MinGW
300     DLLs.
301
302 * Release 2.8.5
303
304   * Minor fixes to build system
305
306 * Release 2.8.4
307
308   * Small bug fixes
309   * Upgrades to build system
310
311 * Release 2.8.3:
312
313   * Fix for handling SOS.
314
315 * Release 2.8.2:
316
317   * Fixed recognition of Glpk source in main configure.
318   * Minor bug fixes in CoinUtils, Clp, and Cbc.
319
320 * Release 2.8.1:
321
322   * Minor bug fixes
323
324 * Release 2.8.0:
325
326   * Introduced new secondaryStatus 8 to indicate that solving stopped due to
327     an iteration limit.
328   * Solution pool is now accessible via the command line and the CbcMain*
329     interface.
330   * New mipstart option to read an initial feasible solution from a file.
331     Only values for discrete variables need to be provided.
332
333   * Added Proximity Search heuristic by Fischetti and Monaci (off by
334     default): The simplest way to switch it on using stand-alone version is
335     ```-proximity on```.
336
337     Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement
338     heuristic recently proposed by Fischetti and Monaci (2012). The idea is
339     to define a sub-MIP without additional constraints but with a modified
340     objective function intended to attract the search in the proximity of the
341     incumbent. The approach works well for 0-1 MIPs whose solution landscape
342     is not too irregular (meaning the there is reasonable probability of
343     finding an improved solution by flipping a small number of binary
344     variables), in particular when it is applied to the first heuristic
345     solutions found at the root node.
346
347   * An implementation of Zero-Half-Cuts by Alberto Caprara is now available.
348     By default, these cuts are off. To use add to your command line
349     -zerohalfCuts root (or other options) or just -zero. So far, they may
350     help only on a small subset of problems and may need some tuning.
351
352     The implementation of these cuts is described in G. Andreello, A.
353     Caprara, and M. Fischetti "Embedding Cuts in a Branch and Cut Framework:
354     a Computational Study with {0,1/2}-Cuts" INFORMS Journal on Computing
355     19(2), 229-238, 2007 http://dx.doi.org/10.1287/ijoc.1050.0162
356
357   * An alternative implementation of a reduce and split cut generator by
358     Giacomo Nannicini is now available. By default, these cuts are off. To
359     use add to your command line -reduce2AndSplitCuts root (or other
360     options).
361
362     The implementation of these cuts is described in G. Cornuejols and G.
363     Nannicini "Practical strategies for generating rank-1 split cuts in
364     mixed-integer linear programming" Mathematical Programming Computation
365     3(4), 281-318, 2011 http://dx.doi.org/10.1007/s12532-011-0028-6
366
367   * An alternative robust implementation of a Gomory cut generator by Giacomo
368     Nannicini is now available. By default, these cuts are off. To use add to
369     your command line -GMI root (or other options).
370
371     The implementation of these cuts is described in G. Cornuejols, F.
372     Margot, and G. Nannicini "On the safety of Gomory cut generators"
373     http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications
374
375   * To encourage the use of some of the more exotic/expensive cut generators
376     a parameter -slowcutpasses has been added. The idea is that the code does
377     these cuts just a few times - less than the more usual cuts. The default
378     is 10. The cut generators identified by "may be slow" at present are just
379     Lift and project and ReduceAndSplit (both versions).
380
381   * Allow initialization of random seed by user. Pseudo-random numbers are
382     used in Cbc and Clp. In Clp they are used to break ties in degenerate
383     problems, while in Cbc heuristics such as the Feasibility Pump use them
384     to decide whether to round up or down. So if a different pseudo-random
385     seed is given to Clp then you may get a different continuous optimum and
386     so different cuts and heuristic solutions. This can be switched on by
387     setting randomSeed for Clp and/or randomCbcSeed for Cbc. The special
388     value of 0 tells code to use time of day for initial seed.
389
390   * Building on this idea, Andrea Lodi, Matteo Fischetti, Michele Monaci,
391     Domenico Salvagnin, Yuji Shinano, and Andrea Tramontani suggest that this
392     idea be improved by running at the root node with multiple copies of
393     solver, each with its own different seed and then passing in the
394     solutions and cuts so that the main solver has a richer set of solutions
395     and possibly stronger cuts. This is switched on by setting
396     -multipleRootPasses. These can also be done in parallel.
397
398   * Few changes to presolve for special variables and badly scaled problems
399     (in CoinUtils).
400
401   * New option -extraVariables <number> which switches on a trivial
402    re-formulation that introduces extra integer variables to group together
403    variables with same cost.
404
405   * For some problems, cut generators and general branching work better if
406     the problem would be infeasible if the cost is too high. If the new
407     option -constraintFromCutoff is set, the objective function is added as a
408     constraint which rhs is set to the current cutoff value (objective value
409     of best known solution).
410
411 * Release 2.7.8:
412
413   * Change message when LP simplex iteration limit is hit from "Exiting on
414     maximum nodes" to "Exiting on maximum number of iterations"
415   * Fix for using overlapping SOS.
416   * Fixes in buildsystem.
417
418 * Release 2.7.7:
419
420   * Fix to report interruption on user event if SIGINT is received by
421     CbcSolver. model->status() should now be 5 if this event happened. Added
422     method CbcModel::sayEventHappened() to make cbc stop due to an 'user
423     event'.
424
425   * Other minor fixes.
426
427 * Release 2.7.6:
428
429   * Fixes to build system.
430
431   * Other minor fixes.
432
433 * Release 2.7.5:
434
435   * Fixes to get AMPL interface working again.
436
437   * More fixes to MSVC++ files.
438
439 * Release 2.7.4:
440
441   * Minor bugfixes.
442
443 * Release 2.7.3:
444
445   * Minor bugfixes.
446
447   * Fixes to MSVC++ files.
448
449 * Release 2.7.2:
450
451   * Allow row/column names for GMPL models.
452
453   * Added CbcModel::haveMultiThreadSupport() to indicate whether Cbc library
454     has been compiled with multithread support.
455
456   * Added CbcModel::waitingForMiniBranchAndBound() to indicate whether
457     sub-MIP heuristic is currently running.
458
459   * Cbc shell should work with readline if configured with
460     ```--enable-gnu-packages```.
461
462   * Support for compressed input files (.gz, .bz2) is now enabled by default.
463
464   * Fix problems with relative gap tolerance > 100% and further bugs.
465
466   * Fixes for MSVC++ Version 9 files.
467
468   * Minor fixes in buildsystem; update to BuildTools 0.7.1.
469
470 * Release 2.7.1:
471
472   * Fixes to MSVC++ files
473
474 * Release 2.7.0:
475
476   * License has been changed to the EPL.
477
478   * Support for MSVC++ version 10 added.
479
480   * Support for BuildTools version 0.7 to incorporate recent enhancements,
481     including proper library versioning in Linux, prohibiting installation of
482     private headers, etc.
483
484   * Updated externals to new stable versions of dependent projects.
485
486   * Improvements to heuristics.
487
488   * New options for cut generation.
489
490   * Improved reporting of results.
491
492   * Improvements to documentation.
493
494   * Minor bug fixes.
Note: See TracBrowser for help on using the repository browser.