source: trunk/README.md @ 2609

Last change on this file since 2609 was 2609, checked in by tkr, 4 months ago

Fixing up README

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.3
176   * Improve performance of some primal heuristics, incl. feasibility pump, by making integer slacks continuous
177   * Added additional timelimit checks
178   * Fixed initialization of Cbc_clone result
179   * Additional bugfixes
180
181 * Release 2.10.2
182   * Bugfixes
183
184 * Release 2.10.1
185   * Fixed Cbc_clone in C interface
186   * Fixed CbcMain1() call in examples/driver3.cpp
187   * Fixed possible issue with MIPstart if presolve added variables
188   * More minor bugfixes
189
190 * Release 2.10.0
191   * Improved handling of SOS, starting point, and symmetries
192   * Improved performance of primal heuristics regarding the handling of
193     implicit integer variables
194   * Mini-B&B is now disabled when solving with multiple threads
195   * Changed default value for zero half cuts parameter from off to ifmove
196   * Added CbcModel::postProcessedSolver() to obtained LP after presolve
197   * New option "PrepNames" to indicate whether column names should be
198     kept in the pre-processed model
199   * New option "sosPrioritize" to determine how to prioritize SOS
200   * Added new event "generatedCuts"
201   * CbcSolver can now read compressed .lp files (GZIP, BZIP2)
202   * New functions in the C interface: Cbc_readLp, Cbc_writeLp,
203     Cbc_addCol, Cbc_addRow, Cbc_getNumIntegers, Cbc_bestSolution,
204     Cbc_getObjValue, Cbc_getRowNz, Cbc_getRowIndices, Cbc_getRowCoeffs,
205     Cbc_getRowRHS, Cbc_getRowSense, Cbc_getColNz, Cbc_getColIndices,
206     Cbc_getColCoeffs, Cbc_getReducedCost, Cbc_numberSavedSolutions,
207     Cbc_savedSolution, Cbc_savedSolutionObj, Cbc_setMIPStart,
208     Cbc_setMIPStartI, Cbc_addCutCallback, Osi_getNumCols, Osi_getColName,
209     Osi_getColLower, Osi_getColUpper, Osi_isInteger, Osi_getNumRows,
210     Osi_getRowNz, Osi_getRowIndices, Osi_getRowCoeffs, Osi_getRowRHS,
211     Osi_getRowSense, Osi_getColSolution, OsiCuts_addRowCut,
212     Cbc_getAllowableGap, Cbc_setAllowableGap, Cbc_getAllowableFractionGap,
213     Cbc_setAllowableFractionGap, Cbc_getAllowablePercentageGap,
214     Cbc_setAllowablePercentageGap, Cbc_getCutoff, Cbc_setCutoff,
215     Cbc_getMaximumNodes, Cbc_setMaximumNodes, Cbc_getMaximumSolutions,
216     Cbc_setMaximumSolutions, Cbc_getLogLevel, Cbc_setLogLevel,
217     Cbc_getMaximumSeconds, Cbc_setMaximumSeconds
218   * New action "guess" checks properties of the model to decide the best
219     parameters for solving the LP relaxation.
220   * New example inc.cpp to illustrate solution callback
221   * New example driver5.cpp to illustrate user-defined branching rule
222   * New example clpdriver.cpp to illustrate use of ClpEventHandler
223   * Added support for using OsiHiGHS with CbcGeneric
224   * Added MSVC 14 project files
225   * Bugfixes
226
227 * Release 2.9.10
228   * Fix a numerical issue
229   * Fix some memory leaks
230   * Fix issue when root node is obviously infeasible
231   * Performance improvements for mini-B&B
232   * Fix name of bound in final message
233   * Fix names in preprocessed problem
234
235 * Release 2.9.9
236
237   * Fixes for SOS2
238   * Updates to mipstart
239   * Switching to new build system
240   * Updates for CI
241
242 * Release 2.9.8
243
244   * Update to most current releases of dependencies
245   * Small bug fixes
246   * Add support for automatic build and test with Travis and Appveyor
247
248 * Release 2.9.7
249
250   * Small bug fixes
251   * Option to switch to line buffered output
252
253 * Release 2.9.6
254
255   * Small bug fixes
256
257 * Release 2.9.5
258
259   * Small bug fixes
260
261 * Release 2.9.4
262
263   * Small fixes for stability
264   * Fixes for Doygen documentation generation
265
266 * Release 2.9.3
267
268   * Minor bug fixes
269
270 * Release 2.9.2
271
272   * Fix for proper installation with ```DESTDIR```
273
274 * Release 2.9.1
275
276   * Fix for dependency linking
277   * Minor bug fixes
278
279 * Release 2.9.0
280
281   * Introduced specialized branching methods for dealing with "big Ms".
282   * Introduced new methods for dealing with symmetry (requires installation of [nauty](http://pallini.di.uniroma1.it/))
283   * Introduction of conflict cuts (off by default, turn on with `-constraint conflict`)
284
285 * Release 2.8.13
286
287   * Improved message handling
288   * Miscellaneous bug fixes.
289
290 * Release 2.8.12
291
292   * Update for dependencies.
293
294 * Release 2.8.11
295
296   * Major overhaul of C interface
297   * Fixes to SOS
298   * Miscellaneous bug fixes
299
300 * Release 2.8.10
301
302   * More changes related to thread safety.
303   * Fix bug in build system with Visual Studio compiler.
304   * Miscellaneous bug fixes.
305
306 * Release 2.8.9
307
308   * Attempt to make Cbc thread safe.
309   * Add parallel examples.
310   * Add CbcSolverUsefulInfo.
311   * Bug fixes.
312
313 * Release 2.8.8
314
315   * Added example to show how to use Cbc with installed libraries in MSVC++
316   * Fixed inconsistency in addition of libCbcSolver to dependencies in
317     {{{cbc_addlibs.txt}}}.
318
319 * Release 2.8.7
320
321   * Changed so that Doxygen builds LaTex
322   * Fixes for build system
323
324 * Release 2.8.6
325
326   * Added option to explicitly link dependencies to comply with packaging
327     requirements on Fedora and Debian, as well as allow building of MinGW
328     DLLs.
329
330 * Release 2.8.5
331
332   * Minor fixes to build system
333
334 * Release 2.8.4
335
336   * Small bug fixes
337   * Upgrades to build system
338
339 * Release 2.8.3:
340
341   * Fix for handling SOS.
342
343 * Release 2.8.2:
344
345   * Fixed recognition of Glpk source in main configure.
346   * Minor bug fixes in CoinUtils, Clp, and Cbc.
347
348 * Release 2.8.1:
349
350   * Minor bug fixes
351
352 * Release 2.8.0:
353
354   * Introduced new secondaryStatus 8 to indicate that solving stopped due to
355     an iteration limit.
356   * Solution pool is now accessible via the command line and the CbcMain*
357     interface.
358   * New mipstart option to read an initial feasible solution from a file.
359     Only values for discrete variables need to be provided.
360
361   * Added Proximity Search heuristic by Fischetti and Monaci (off by
362     default): The simplest way to switch it on using stand-alone version is
363     ```-proximity on```.
364
365     Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement
366     heuristic recently proposed by Fischetti and Monaci (2012). The idea is
367     to define a sub-MIP without additional constraints but with a modified
368     objective function intended to attract the search in the proximity of the
369     incumbent. The approach works well for 0-1 MIPs whose solution landscape
370     is not too irregular (meaning the there is reasonable probability of
371     finding an improved solution by flipping a small number of binary
372     variables), in particular when it is applied to the first heuristic
373     solutions found at the root node.
374
375   * An implementation of Zero-Half-Cuts by Alberto Caprara is now available.
376     By default, these cuts are off. To use add to your command line
377     -zerohalfCuts root (or other options) or just -zero. So far, they may
378     help only on a small subset of problems and may need some tuning.
379
380     The implementation of these cuts is described in G. Andreello, A.
381     Caprara, and M. Fischetti "Embedding Cuts in a Branch and Cut Framework:
382     a Computational Study with {0,1/2}-Cuts" INFORMS Journal on Computing
383     19(2), 229-238, 2007 http://dx.doi.org/10.1287/ijoc.1050.0162
384
385   * An alternative implementation of a reduce and split cut generator by
386     Giacomo Nannicini is now available. By default, these cuts are off. To
387     use add to your command line -reduce2AndSplitCuts root (or other
388     options).
389
390     The implementation of these cuts is described in G. Cornuejols and G.
391     Nannicini "Practical strategies for generating rank-1 split cuts in
392     mixed-integer linear programming" Mathematical Programming Computation
393     3(4), 281-318, 2011 http://dx.doi.org/10.1007/s12532-011-0028-6
394
395   * An alternative robust implementation of a Gomory cut generator by Giacomo
396     Nannicini is now available. By default, these cuts are off. To use add to
397     your command line -GMI root (or other options).
398
399     The implementation of these cuts is described in G. Cornuejols, F.
400     Margot, and G. Nannicini "On the safety of Gomory cut generators"
401     http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications
402
403   * To encourage the use of some of the more exotic/expensive cut generators
404     a parameter -slowcutpasses has been added. The idea is that the code does
405     these cuts just a few times - less than the more usual cuts. The default
406     is 10. The cut generators identified by "may be slow" at present are just
407     Lift and project and ReduceAndSplit (both versions).
408
409   * Allow initialization of random seed by user. Pseudo-random numbers are
410     used in Cbc and Clp. In Clp they are used to break ties in degenerate
411     problems, while in Cbc heuristics such as the Feasibility Pump use them
412     to decide whether to round up or down. So if a different pseudo-random
413     seed is given to Clp then you may get a different continuous optimum and
414     so different cuts and heuristic solutions. This can be switched on by
415     setting randomSeed for Clp and/or randomCbcSeed for Cbc. The special
416     value of 0 tells code to use time of day for initial seed.
417
418   * Building on this idea, Andrea Lodi, Matteo Fischetti, Michele Monaci,
419     Domenico Salvagnin, Yuji Shinano, and Andrea Tramontani suggest that this
420     idea be improved by running at the root node with multiple copies of
421     solver, each with its own different seed and then passing in the
422     solutions and cuts so that the main solver has a richer set of solutions
423     and possibly stronger cuts. This is switched on by setting
424     -multipleRootPasses. These can also be done in parallel.
425
426   * Few changes to presolve for special variables and badly scaled problems
427     (in CoinUtils).
428
429   * New option -extraVariables <number> which switches on a trivial
430    re-formulation that introduces extra integer variables to group together
431    variables with same cost.
432
433   * For some problems, cut generators and general branching work better if
434     the problem would be infeasible if the cost is too high. If the new
435     option -constraintFromCutoff is set, the objective function is added as a
436     constraint which rhs is set to the current cutoff value (objective value
437     of best known solution).
438
439 * Release 2.7.8:
440
441   * Change message when LP simplex iteration limit is hit from "Exiting on
442     maximum nodes" to "Exiting on maximum number of iterations"
443   * Fix for using overlapping SOS.
444   * Fixes in buildsystem.
445
446 * Release 2.7.7:
447
448   * Fix to report interruption on user event if SIGINT is received by
449     CbcSolver. model->status() should now be 5 if this event happened. Added
450     method CbcModel::sayEventHappened() to make cbc stop due to an 'user
451     event'.
452
453   * Other minor fixes.
454
455 * Release 2.7.6:
456
457   * Fixes to build system.
458
459   * Other minor fixes.
460
461 * Release 2.7.5:
462
463   * Fixes to get AMPL interface working again.
464
465   * More fixes to MSVC++ files.
466
467 * Release 2.7.4:
468
469   * Minor bugfixes.
470
471 * Release 2.7.3:
472
473   * Minor bugfixes.
474
475   * Fixes to MSVC++ files.
476
477 * Release 2.7.2:
478
479   * Allow row/column names for GMPL models.
480
481   * Added CbcModel::haveMultiThreadSupport() to indicate whether Cbc library
482     has been compiled with multithread support.
483
484   * Added CbcModel::waitingForMiniBranchAndBound() to indicate whether
485     sub-MIP heuristic is currently running.
486
487   * Cbc shell should work with readline if configured with
488     ```--enable-gnu-packages```.
489
490   * Support for compressed input files (.gz, .bz2) is now enabled by default.
491
492   * Fix problems with relative gap tolerance > 100% and further bugs.
493
494   * Fixes for MSVC++ Version 9 files.
495
496   * Minor fixes in buildsystem; update to BuildTools 0.7.1.
497
498 * Release 2.7.1:
499
500   * Fixes to MSVC++ files
501
502 * Release 2.7.0:
503
504   * License has been changed to the EPL.
505
506   * Support for MSVC++ version 10 added.
507
508   * Support for BuildTools version 0.7 to incorporate recent enhancements,
509     including proper library versioning in Linux, prohibiting installation of
510     private headers, etc.
511
512   * Updated externals to new stable versions of dependent projects.
513
514   * Improvements to heuristics.
515
516   * New options for cut generation.
517
518   * Improved reporting of results.
Note: See TracBrowser for help on using the repository browser.