source: trunk/README.md @ 2892

Last change on this file since 2892 was 2892, checked in by stefan, 21 months ago

update changelog for 2.10.5 release

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