source: trunk/Cbc/examples/sample5.cpp @ 2496

Last change on this file since 2496 was 2469, checked in by unxusr, 8 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.8 KB
Line 
1// $Id: sample5.cpp 2469 2019-01-06 23:17:46Z forrest $
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include "CbcConfig.h"
7
8#include "CoinPragma.hpp"
9
10#include <cassert>
11#include <iomanip>
12
13// For Branch and bound
14#include "OsiSolverInterface.hpp"
15#include "CbcModel.hpp"
16#include "CbcBranchUser.hpp"
17#include "CbcCompareUser.hpp"
18#include "CbcCutGenerator.hpp"
19#include "CbcHeuristicLocal.hpp"
20#include "OsiClpSolverInterface.hpp"
21
22// Cuts
23
24#include "CglGomory.hpp"
25#include "CglProbing.hpp"
26#include "CglKnapsackCover.hpp"
27#include "CglOddHole.hpp"
28#include "CglClique.hpp"
29#include "CglFlowCover.hpp"
30#include "CglMixedIntegerRounding.hpp"
31
32// Heuristics
33
34#include "CbcHeuristic.hpp"
35
36// Methods of building
37
38#include "CoinBuild.hpp"
39#include "CoinModel.hpp"
40
41#include "CoinTime.hpp"
42
43/************************************************************************
44
45This main program creates an integer model and then solves it
46
47It then sets up some Cgl cut generators and calls branch and cut.
48
49Branching is simple binary branching on integer variables.
50
51Node selection is depth first until first solution is found and then
52based on objective and number of unsatisfied integer variables.
53In this example the functionality is the same as default but it is
54a user comparison function.
55
56Variable branching selection is on maximum minimum-of-up-down change
57after strong branching on 5 variables closest to 0.5.
58
59A simple rounding heuristic is used.
60
61
62************************************************************************/
63
64int main(int argc, const char *argv[])
65{
66
67  /* Define your favorite OsiSolver.
68
69     CbcModel clones the solver so use solver1 up to the time you pass it
70     to CbcModel then use a pointer to cloned solver (model.solver())
71  */
72
73  OsiClpSolverInterface solver1;
74  /* From now on we can build model in a solver independent way.
75     You can add rows one at a time but for large problems this is slow so
76     this example uses CoinBuild or CoinModel
77  */
78  OsiSolverInterface *solver = &solver1;
79  // Data (is exmip1.mps in Mps/Sample
80  // Objective
81  double objValue[] = { 1.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, -1.0 };
82  // Lower bounds for columns
83  double columnLower[] = { 2.5, 0.0, 0.0, 0.0, 0.5, 0.0, 0.0, 0.0 };
84  // Upper bounds for columns
85  double columnUpper[] = { COIN_DBL_MAX, 4.1, 1.0, 1.0, 4.0,
86    COIN_DBL_MAX, COIN_DBL_MAX, 4.3 };
87  // Lower bounds for row activities
88  double rowLower[] = { 2.5, -COIN_DBL_MAX, -COIN_DBL_MAX, 1.8, 3.0 };
89  // Upper bounds for row activities
90  double rowUpper[] = { COIN_DBL_MAX, 2.1, 4.0, 5.0, 15.0 };
91  // Matrix stored packed
92  int column[] = { 0, 1, 3, 4, 7,
93    1, 2,
94    2, 5,
95    3, 6,
96    4, 7 };
97  double element[] = { 3.0, 1.0, -2.0, -1.0, -1.0,
98    2.0, 1.1,
99    1.0, 1.0,
100    2.8, -1.2,
101    1.0, 1.9 };
102  int starts[] = { 0, 5, 7, 9, 11, 13 };
103  // Integer variables (note upper bound already 1.0)
104  int whichInt[] = { 2, 3 };
105  int numberRows = (int)(sizeof(rowLower) / sizeof(double));
106  int numberColumns = (int)(sizeof(columnLower) / sizeof(double));
107#define BUILD 2
108#if BUILD == 1
109  // Using CoinBuild
110  // First do columns (objective and bounds)
111  int i;
112  // We are not adding elements
113  for (i = 0; i < numberColumns; i++) {
114    solver->addCol(0, NULL, NULL, columnLower[i], columnUpper[i],
115      objValue[i]);
116  }
117  // mark as integer
118  for (i = 0; i < (int)(sizeof(whichInt) / sizeof(int)); i++)
119    solver->setInteger(whichInt[i]);
120  // Now build rows
121  CoinBuild build;
122  for (i = 0; i < numberRows; i++) {
123    int startRow = starts[i];
124    int numberInRow = starts[i + 1] - starts[i];
125    build.addRow(numberInRow, column + startRow, element + startRow,
126      rowLower[i], rowUpper[i]);
127  }
128  // add rows into solver
129  solver->addRows(build);
130#else
131  /* using CoinModel - more flexible but still beta.
132     Can do exactly same way but can mix and match much more.
133     Also all operations are on building object
134  */
135  CoinModel build;
136  // First do columns (objective and bounds)
137  int i;
138  for (i = 0; i < numberColumns; i++) {
139    build.setColumnBounds(i, columnLower[i], columnUpper[i]);
140    build.setObjective(i, objValue[i]);
141  }
142  // mark as integer
143  for (i = 0; i < (int)(sizeof(whichInt) / sizeof(int)); i++)
144    build.setInteger(whichInt[i]);
145  // Now build rows
146  for (i = 0; i < numberRows; i++) {
147    int startRow = starts[i];
148    int numberInRow = starts[i + 1] - starts[i];
149    build.addRow(numberInRow, column + startRow, element + startRow,
150      rowLower[i], rowUpper[i]);
151  }
152  // add rows into solver
153  solver->loadFromCoinModel(build);
154#endif
155
156  // Pass to solver
157  CbcModel model(*solver);
158  model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
159
160  // Set up some cut generators and defaults
161  // Probing first as gets tight bounds on continuous
162
163  CglProbing generator1;
164  generator1.setUsingObjective(true);
165  generator1.setMaxPass(3);
166  generator1.setMaxProbe(100);
167  generator1.setMaxLook(50);
168  generator1.setRowCuts(3);
169  //  generator1.snapshot(*model.solver());
170  //generator1.createCliques(*model.solver(),2,1000,true);
171  //generator1.setMode(0);
172
173  CglGomory generator2;
174  // try larger limit
175  generator2.setLimit(300);
176
177  CglKnapsackCover generator3;
178
179  CglOddHole generator4;
180  generator4.setMinimumViolation(0.005);
181  generator4.setMinimumViolationPer(0.00002);
182  // try larger limit
183  generator4.setMaximumEntries(200);
184
185  CglClique generator5;
186  generator5.setStarCliqueReport(false);
187  generator5.setRowCliqueReport(false);
188
189  CglMixedIntegerRounding mixedGen;
190  CglFlowCover flowGen;
191
192  // Add in generators
193  model.addCutGenerator(&generator1, -1, "Probing");
194  model.addCutGenerator(&generator2, -1, "Gomory");
195  model.addCutGenerator(&generator3, -1, "Knapsack");
196  model.addCutGenerator(&generator4, -1, "OddHole");
197  model.addCutGenerator(&generator5, -1, "Clique");
198  model.addCutGenerator(&flowGen, -1, "FlowCover");
199  model.addCutGenerator(&mixedGen, -1, "MixedIntegerRounding");
200
201  OsiClpSolverInterface *osiclp = dynamic_cast< OsiClpSolverInterface * >(model.solver());
202  // go faster stripes
203  if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) {
204    osiclp->setupForRepeatedUse(2, 0);
205    printf("trying slightly less reliable but faster version (? Gomory cuts okay?)\n");
206    printf("may not be safe if doing cuts in tree which need accuracy (level 2 anyway)\n");
207  }
208
209  // Allow rounding heuristic
210
211  CbcRounding heuristic1(model);
212  model.addHeuristic(&heuristic1);
213
214  // And local search when new solution found
215
216  CbcHeuristicLocal heuristic2(model);
217  model.addHeuristic(&heuristic2);
218
219  // Redundant definition of default branching (as Default == User)
220  CbcBranchUserDecision branch;
221  model.setBranchingMethod(&branch);
222
223  // Definition of node choice
224  CbcCompareUser compare;
225  model.setNodeComparison(compare);
226
227  // Do initial solve to continuous
228  model.initialSolve();
229
230  // Could tune more
231  model.setMinimumDrop(CoinMin(1.0,
232    fabs(model.getMinimizationObjValue()) * 1.0e-3 + 1.0e-4));
233
234  if (model.getNumCols() < 500)
235    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
236  else if (model.getNumCols() < 5000)
237    model.setMaximumCutPassesAtRoot(100); // use minimum drop
238  else
239    model.setMaximumCutPassesAtRoot(20);
240  //model.setMaximumCutPasses(5);
241
242  // Switch off strong branching if wanted
243  // model.setNumberStrong(0);
244  // Do more strong branching if small
245  if (model.getNumCols() < 5000)
246    model.setNumberStrong(10);
247
248  model.solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
249
250  // If time is given then stop after that number of minutes
251  if (argc > 2) {
252    int minutes = atoi(argv[2]);
253    std::cout << "Stopping after " << minutes << " minutes" << std::endl;
254    assert(minutes >= 0);
255    model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes);
256  }
257  // Switch off most output
258  if (model.getNumCols() < 3000) {
259    model.messageHandler()->setLogLevel(1);
260    //model.solver()->messageHandler()->setLogLevel(0);
261  } else {
262    model.messageHandler()->setLogLevel(2);
263    model.solver()->messageHandler()->setLogLevel(1);
264  }
265  double time1 = CoinCpuTime();
266
267  // Do complete search
268
269  model.branchAndBound();
270
271  std::cout << " Branch and cut took " << CoinCpuTime() - time1 << " seconds, "
272            << model.getNodeCount() << " nodes with objective "
273            << model.getObjValue()
274            << (!model.status() ? " Finished" : " Not finished")
275            << std::endl;
276
277  // Print more statistics
278  std::cout << "Cuts at root node changed objective from " << model.getContinuousObjective()
279            << " to " << model.rootObjectiveAfterCuts() << std::endl;
280
281  int numberGenerators = model.numberCutGenerators();
282  for (int iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
283    CbcCutGenerator *generator = model.cutGenerator(iGenerator);
284    std::cout << generator->cutGeneratorName() << " was tried "
285              << generator->numberTimesEntered() << " times and created "
286              << generator->numberCutsInTotal() << " cuts of which "
287              << generator->numberCutsActive() << " were active after adding rounds of cuts"
288              << std::endl;
289  }
290  // Print solution if any - we can't get names from Osi!
291
292  if (model.getMinimizationObjValue() < 1.0e50) {
293    int numberColumns = model.solver()->getNumCols();
294
295    const double *solution = model.solver()->getColSolution();
296
297    int iColumn;
298    std::cout << std::setiosflags(std::ios::fixed | std::ios::showpoint) << std::setw(14);
299
300    std::cout << "--------------------------------------" << std::endl;
301    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
302      double value = solution[iColumn];
303      if (fabs(value) > 1.0e-7 && model.solver()->isInteger(iColumn))
304        std::cout << std::setw(6) << iColumn << " " << value << std::endl;
305    }
306    std::cout << "--------------------------------------" << std::endl;
307
308    std::cout << std::resetiosflags(std::ios::fixed | std::ios::showpoint | std::ios::scientific);
309  }
310  return 0;
311}
Note: See TracBrowser for help on using the repository browser.