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

Last change on this file since 1173 was 1173, checked in by forrest, 10 years ago

add $id

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