source: trunk/README.md @ 2632

Last change on this file since 2632 was 2617, checked in by stefan, 4 months ago

add readme entry for r2616

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