1 | CBC README |
---|
2 | ========== |
---|
3 | |
---|
4 | Welcome to the README for the COIN Branch and Cut Solver (CBC). CBC is |
---|
5 | distributed under the Eclipse Public License and is freely redistributable. |
---|
6 | All source code and documentation is Copyright IBM and others. This README may |
---|
7 | be redistributed freely. |
---|
8 | |
---|
9 | DOCUMENTATION |
---|
10 | ============= |
---|
11 | |
---|
12 | For a quick start guide, please see the INSTALL file in this distribution. A (somehwat outdated) user's manual is available here: |
---|
13 | |
---|
14 | http://www.coin-or.org/Cbc |
---|
15 | |
---|
16 | More up-to-date automatically generated documentation of the source code can |
---|
17 | be found here: |
---|
18 | |
---|
19 | http://www.coin-or.org/Doxygen/Cbc/ |
---|
20 | |
---|
21 | Further information can be found here: |
---|
22 | |
---|
23 | http://projects.coin-or.org/Cbc |
---|
24 | |
---|
25 | WHAT'S NEW |
---|
26 | ========== |
---|
27 | |
---|
28 | Release 2.8.0: |
---|
29 | |
---|
30 | 1. Introduced new secondaryStatus 8 to indicate that solving stopped due to an iteration limit. |
---|
31 | |
---|
32 | 2. Solution pool is now accessible via the command line and the CbcMain* interface. |
---|
33 | |
---|
34 | 3. New mipstart option to read an initial feasible solution from a file. Only values for discrete |
---|
35 | variables need to be provided. |
---|
36 | |
---|
37 | 4. Added Proximity Search heuristic by Fischetti and Monaci (off by default): |
---|
38 | The simplest way to switch it on using stand-alone version is "-proximity on". |
---|
39 | |
---|
40 | Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement heuristic recently proposed by |
---|
41 | Fischetti and Monaci (2012). The idea is to define a sub-MIP without additional constraints but with a |
---|
42 | modified objective function intended to attract the search in the proximity of the incumbent. The approach |
---|
43 | works well for 0-1 MIPs whose solution landscape is not too irregular (meaning the there is reasonable |
---|
44 | probability of finding an improved solution by flipping a small number of binary variables), in particular |
---|
45 | when it is applied to the first heuristic solutions found at the root node. |
---|
46 | |
---|
47 | 5. An implementation of Zero-Half-Cuts by Alberto Caprara is now available. |
---|
48 | By default, these cuts are off. To use add to your command line -zerohalfCuts root (or other options) or just -zero. |
---|
49 | So far, they may help only on a small subset of problems and may need some tuning. |
---|
50 | |
---|
51 | The implementation of these cuts is described in |
---|
52 | G. Andreello, A. Caprara, and M. Fischetti |
---|
53 | "Embedding Cuts in a Branch and Cut Framework: a Computational Study with {0,1/2}-Cuts" |
---|
54 | INFORMS Journal on Computing 19(2), 229-238, 2007 |
---|
55 | http://dx.doi.org/10.1287/ijoc.1050.0162 |
---|
56 | |
---|
57 | 6. An alternative implementation of a reduce and split cut generator by Giacomo Nannicini is now available. |
---|
58 | By default, these cuts are off. To use add to your command line -reduce2AndSplitCuts root (or other options). |
---|
59 | |
---|
60 | The implementation of these cuts is described in |
---|
61 | G. Cornuejols and G. Nannicini |
---|
62 | "Practical strategies for generating rank-1 split cuts in mixed-integer linear programming" |
---|
63 | Mathematical Programming Computation 3(4), 281-318, 2011 |
---|
64 | http://dx.doi.org/10.1007/s12532-011-0028-6 |
---|
65 | |
---|
66 | 7. An alternative robust implementation of a Gomory cut generator by Giacomo Nannicini is now available. |
---|
67 | By default, these cuts are off. To use add to your command line -GMI root (or other options). |
---|
68 | |
---|
69 | The implementation of these cuts is described in |
---|
70 | G. Cornuejols, F. Margot, and G. Nannicini |
---|
71 | "On the safety of Gomory cut generators" |
---|
72 | http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications |
---|
73 | |
---|
74 | 8. Allow initialization of random seed by user. Pseudo-random numbers are used in Cbc and Clp. In Clp they |
---|
75 | are used to break ties in degenerate problems, while in Cbc heuristics such as the Feasibility Pump use them |
---|
76 | to decide whether to round up or down. So if a different pseudo-random seed is given to Clp then you may get |
---|
77 | a different continuous optimum and so different cuts and heuristic solutions. This can be switched on by |
---|
78 | setting randomSeed for Clp and/or randomCbcSeed for Cbc. The special value of 0 tells code to use time of day |
---|
79 | for initial seed. |
---|
80 | |
---|
81 | 9. Building on this idea Andrea Lodi, Matteo Fischetti, Michele Monaci, Domenico Salvagnin and Andrea Tramontani |
---|
82 | suggest that this idea be be improved by running at the root node with multiple copies of solver, each |
---|
83 | with its own different seed and then passing in the solutions and cuts so that the main solver has a richer |
---|
84 | set of solutions and possibly stronger cuts. This is switched on by setting multipleRootPasses. These can also |
---|
85 | be done in parallel. |
---|
86 | |
---|
87 | 10. Few changes to presolve for special variables and badly scaled problems (in CoinUtils). |
---|
88 | |
---|
89 | 11. New option -extraVariables <number> which switches on a trivial re-formulation to group variables with same cost together. |
---|
90 | |
---|
91 | |
---|
92 | Release 2.7.8: |
---|
93 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.7&new_path=%2Freleases%2F2.7.8 to see all changes. |
---|
94 | |
---|
95 | 1. Change message when LP simplex iteration limit is hit from "Exiting on maximum nodes" |
---|
96 | to "Exiting on maximum number of iterations" |
---|
97 | |
---|
98 | 2. Fix for using overlapping SOS. |
---|
99 | |
---|
100 | 3. Fixes in buildsystem. |
---|
101 | |
---|
102 | Release 2.7.7: |
---|
103 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.6&new_path=%2Freleases%2F2.7.7 to see all changes. |
---|
104 | |
---|
105 | 1. Fix to report interruption on user event if SIGINT is received by CbcSolver. |
---|
106 | model->status() should now be 5 if this event happened. |
---|
107 | Added method CbcModel::sayEventHappened() to make cbc stop due to an 'user event'. |
---|
108 | |
---|
109 | 2. Other minor fixes. |
---|
110 | |
---|
111 | Release 2.7.6: |
---|
112 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.5&new_path=%2Freleases%2F2.7.6 to see all changes. |
---|
113 | |
---|
114 | 1. Fixes to build system. |
---|
115 | |
---|
116 | 2. Other minor fixes. |
---|
117 | |
---|
118 | Release 2.7.5: |
---|
119 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.4&new_path=%2Freleases%2F2.7.5 to see all changes. |
---|
120 | |
---|
121 | 1. Fixes to get AMPL interface working again. |
---|
122 | |
---|
123 | 2. More fixes to MSVC++ files. |
---|
124 | |
---|
125 | Release 2.7.4: |
---|
126 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.3&new_path=%2Freleases%2F2.7.4 to see all changes. |
---|
127 | |
---|
128 | 1. Minor bugfixes. |
---|
129 | |
---|
130 | Release 2.7.3: |
---|
131 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.2&new_path=%2Freleases%2F2.7.3 to see all changes. |
---|
132 | |
---|
133 | 1. Minor bugfixes. |
---|
134 | |
---|
135 | 2. Fixes to MSVC++ files. |
---|
136 | |
---|
137 | Release 2.7.2: |
---|
138 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.1&new_path=%2Freleases%2F2.7.2 to see all changes. |
---|
139 | |
---|
140 | 1. Allow row/column names for GMPL models. |
---|
141 | |
---|
142 | 2. Added CbcModel::haveMultiThreadSupport() to indicate whether Cbc library has been compiled with multithread support. |
---|
143 | |
---|
144 | 3. Added CbcModel::waitingForMiniBranchAndBound() to indicate whether sub-MIP heuristic is currently running. |
---|
145 | |
---|
146 | 4. Cbc shell should work with readline if configured with --enable-gnu-packages. |
---|
147 | |
---|
148 | 5. Support for compressed input files (.gz, .bz2) is now enabled by default. |
---|
149 | |
---|
150 | 6. Fix problems with relative gap tolerance > 100% and further bugs. |
---|
151 | |
---|
152 | 7. Fixes for MSVC++ Version 9 files. |
---|
153 | |
---|
154 | 8. Minor fixes in buildsystem; update to BuildTools 0.7.1. |
---|
155 | |
---|
156 | Release 2.7.1: |
---|
157 | Look at https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.0&new_path=%2Freleases%2F2.7.1 to see all changes. |
---|
158 | |
---|
159 | 1. Fixes to MSVC++ files |
---|
160 | |
---|
161 | Release 2.7.0: |
---|
162 | |
---|
163 | 1. License has been changed to the EPL. |
---|
164 | |
---|
165 | 2. Support for MSVC++ version 10 added. |
---|
166 | |
---|
167 | 3. Support for BuildTools version 0.7 to incorporate recent enhancements, |
---|
168 | including proper library versioning in Linux, prohibiting installation of |
---|
169 | private headers, etc. |
---|
170 | |
---|
171 | 4. Updated externals to new stable versions of dependent projects. |
---|
172 | |
---|
173 | 5. Improvements to heuristics. |
---|
174 | |
---|
175 | 6. New options for cut generation. |
---|
176 | |
---|
177 | 7. Improved reporting of results. |
---|
178 | |
---|
179 | 8. Improvements to documentation. |
---|
180 | |
---|
181 | 9. Minor bug fixes. |
---|
182 | |
---|
183 | SUPPORT |
---|
184 | ======= |
---|
185 | |
---|
186 | 1. List Serve |
---|
187 | |
---|
188 | CBC users should use the Cbc mailing list. To subscribe, go to |
---|
189 | http://list.coin-or.org/mailman/listinfo/cbc |
---|
190 | |
---|
191 | 3. Bug Reports |
---|
192 | |
---|
193 | Bug reports should be reported on the CBC development web site at |
---|
194 | |
---|
195 | https://projects.coin-or.org/Cbc/newticket |
---|