source: trunk/README.md @ 2520

Last change on this file since 2520 was 2520, checked in by stefan, 2 months ago

more updates to README

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