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

Last change on this file since 1574 was 1574, checked in by lou, 8 years ago

Change to EPL license notice.

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