source: trunk/Samples/sample2.cpp @ 117

Last change on this file since 117 was 117, checked in by forrest, 15 years ago

decided oddd hole too slow

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.6 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7
8#include <cassert>
9#include <iomanip>
10
11
12// For Branch and bound
13#include "OsiSolverInterface.hpp"
14#include "CbcModel.hpp"
15#include "CbcBranchUser.hpp"
16#include "CbcCompareUser.hpp"
17#include "CbcCutGenerator.hpp"
18#include "CbcHeuristicUser.hpp"
19#ifdef COIN_USE_CLP
20#include "OsiClpSolverInterface.hpp"
21#endif
22#ifdef COIN_USE_OSL
23#include "OsiOslSolverInterface.hpp"
24#endif
25
26// Cuts
27
28#include "CglGomory.hpp"
29#include "CglProbing.hpp"
30#include "CglKnapsackCover.hpp"
31#include "CglOddHole.hpp"
32#include "CglClique.hpp"
33#include "CglFlowCover.hpp"
34#include "CglMixedIntegerRounding.hpp"
35// Preprocessing
36#include "CglPreProcess.hpp"
37
38// Heuristics
39
40#include "CbcHeuristic.hpp"
41
42#include  "CoinTime.hpp"
43
44//#############################################################################
45
46
47/************************************************************************
48
49This main program reads in an integer model from an mps file.
50
51It then sets up some Cgl cut generators and calls branch and cut.
52
53Branching is simple binary branching on integer variables.
54
55Node selection is depth first until first solution is found and then
56based on objective and number of unsatisfied integer variables.
57In this example the functionality is the same as default but it is
58a user comparison function.
59
60Variable branching selection is on maximum minimum-of-up-down change
61after strong branching on 5 variables closest to 0.5.
62
63A simple rounding heuristic is used.
64
65
66************************************************************************/
67
68// ****** define comparison to choose best next node
69
70int main (int argc, const char *argv[])
71{
72
73  // Define your favorite OsiSolver
74 
75#ifdef COIN_USE_CLP
76  OsiClpSolverInterface solver1;
77#elif COIN_USE_OSL
78  OsiOslSolverInterface solver1;
79#endif
80
81  // Read in model using argv[1]
82  // and assert that it is a clean model
83  std::string mpsFileName = "../../Mps/Sample/p0033.mps";
84  if (argc>=2) mpsFileName = argv[1];
85  int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(),"");
86  assert(numMpsReadErrors==0);
87  double time1 = CoinCpuTime();
88
89  /* Options are:
90     preprocess to do preprocessing
91     time in minutes
92     if 2 parameters and numeric taken as time
93  */
94  bool preProcess=false;
95  double minutes=-1.0;
96  int nGoodParam=0;
97  for (int iParam=2; iParam<argc;iParam++) {
98    if (!strcmp(argv[iParam],"preprocess")) {
99      preProcess=true;
100      nGoodParam++;
101    } else if (!strcmp(argv[iParam],"time")) {
102      if (iParam+1<argc&&isdigit(argv[iParam+1][0])) {
103        minutes=atof(argv[iParam+1]);
104        if (minutes>=0.0) {
105          nGoodParam+=2;
106          iParam++; // skip time
107        }
108      }
109    }
110  }
111  if (nGoodParam==0&&argc==3&&isdigit(argv[2][0])) {
112    // If time is given then stop after that number of minutes
113    minutes = atof(argv[2]);
114    if (minutes>=0.0) 
115      nGoodParam=1;
116  }
117  if (nGoodParam!=argc-2&&argc>=2) {
118    printf("Usage <file> [preprocess] [time <minutes>] or <file> <minutes>\n");
119    exit(1);
120  }
121  solver1.initialSolve();
122  // Reduce printout
123  solver1.setHintParam(OsiDoReducePrint,true,OsiHintTry);
124  // See if we want preprocessing
125  OsiSolverInterface * solver2=&solver1;
126  CglPreProcess process;
127  if (preProcess) {
128    /* Do not try and produce equality cliques and
129       do up to 5 passes */
130    solver2 = process.preProcess(solver1,false,5);
131    if (!solver2) {
132      printf("Pre-processing says infeasible\n");
133      exit(2);
134    }
135    solver2->resolve();
136  }
137  CbcModel model(*solver2);
138  model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
139  // Set up some cut generators and defaults
140  // Probing first as gets tight bounds on continuous
141
142  CglProbing generator1;
143  generator1.setUsingObjective(true);
144  generator1.setMaxPass(3);
145  // Number of unsatisfied variables to look at
146  generator1.setMaxProbe(10);
147  // How far to follow the consequences
148  generator1.setMaxLook(50);
149  // Only look at rows with fewer than this number of elements
150  generator1.setMaxElements(200);
151  generator1.setRowCuts(3);
152
153  CglGomory generator2;
154  // try larger limit
155  generator2.setLimit(300);
156
157  CglKnapsackCover generator3;
158
159  // Decided too slow
160  //CglOddHole generator4;
161  //generator4.setMinimumViolation(0.005);
162  //generator4.setMinimumViolationPer(0.00002);
163  // try larger limit
164  //generator4.setMaximumEntries(200);
165
166  CglClique generator5;
167  generator5.setStarCliqueReport(false);
168  generator5.setRowCliqueReport(false);
169
170  CglMixedIntegerRounding mixedGen;
171  CglFlowCover flowGen;
172 
173  // Add in generators
174  // Experiment with -1 and -99 etc
175  model.addCutGenerator(&generator1,-1,"Probing");
176  model.addCutGenerator(&generator2,-1,"Gomory");
177  model.addCutGenerator(&generator3,-1,"Knapsack");
178  //model.addCutGenerator(&generator4,-1,"OddHole");
179  model.addCutGenerator(&generator5,-1,"Clique");
180  model.addCutGenerator(&flowGen,-1,"FlowCover");
181  model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
182  // Say we want timings
183  int numberGenerators = model.numberCutGenerators();
184  int iGenerator;
185  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
186    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
187    generator->setTiming(true);
188  }
189#ifdef COIN_USE_CLP
190  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (model.solver());
191  // go faster stripes
192  if (osiclp->getNumRows()<300&&osiclp->getNumCols()<500) {
193    osiclp->setupForRepeatedUse(2,0);
194    printf("trying slightly less reliable but faster version (? Gomory cuts okay?)\n");
195    printf("may not be safe if doing cuts in tree which need accuracy (level 2 anyway)\n");
196  }
197#endif
198
199  // Allow rounding heuristic
200
201  CbcRounding heuristic1(model);
202  model.addHeuristic(&heuristic1);
203
204  // And local search when new solution found
205
206  CbcLocalSearch heuristic2(model);
207  model.addHeuristic(&heuristic2);
208
209  // Redundant definition of default branching (as Default == User)
210  CbcBranchUserDecision branch;
211  model.setBranchingMethod(&branch);
212
213  // Definition of node choice
214  CbcCompareUser compare;
215  model.setNodeComparison(compare);
216
217  // Do initial solve to continuous
218  model.initialSolve();
219
220  // Could tune more
221  model.setMinimumDrop(min(1.0,
222                             fabs(model.getMinimizationObjValue())*1.0e-3+1.0e-4));
223
224  if (model.getNumCols()<500)
225    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
226  else if (model.getNumCols()<5000)
227    model.setMaximumCutPassesAtRoot(100); // use minimum drop
228  else
229    model.setMaximumCutPassesAtRoot(20);
230  //model.setMaximumCutPasses(5);
231
232  // Switch off strong branching if wanted
233  // model.setNumberStrong(0);
234  // Do more strong branching if small
235  if (model.getNumCols()<5000)
236    model.setNumberStrong(10);
237
238  model.solver()->setIntParam(OsiMaxNumIterationHotStart,100);
239
240  // If time is given then stop after that number of minutes
241  if (minutes>=0.0) {
242    std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
243    model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
244  }
245  // Switch off most output
246  if (model.getNumCols()<3000) {
247    model.messageHandler()->setLogLevel(1);
248    //model.solver()->messageHandler()->setLogLevel(0);
249  } else {
250    model.messageHandler()->setLogLevel(2);
251    model.solver()->messageHandler()->setLogLevel(1);
252  }
253  //model.messageHandler()->setLogLevel(2);
254  //model.solver()->messageHandler()->setLogLevel(2);
255  //model.setPrintFrequency(50);
256#ifdef DEBUG_CUTS
257  // Set up debugger by name (only if no preprocesing)
258  if (!preProcess) {
259    std::string problemName ;
260    model.solver()->getStrParam(OsiProbName,problemName) ;
261    model.solver()->activateRowCutDebugger(problemName.c_str()) ;
262  }
263#endif
264
265  // Do complete search
266 
267  model.branchAndBound();
268
269  std::cout<<mpsFileName<<" took "<<CoinCpuTime()-time1<<" seconds, "
270           <<model.getNodeCount()<<" nodes with objective "
271           <<model.getObjValue()
272           <<(!model.status() ? " Finished" : " Not finished")
273           <<std::endl;
274
275  // Print more statistics
276  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
277           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
278
279  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
280    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
281    std::cout<<generator->cutGeneratorName()<<" was tried "
282             <<generator->numberTimesEntered()<<" times and created "
283             <<generator->numberCutsInTotal()<<" cuts of which "
284             <<generator->numberCutsActive()<<" were active after adding rounds of cuts";
285    if (generator->timing())
286      std::cout<<" ( "<<generator->timeInCutGenerator()<<" seconds)"<<std::endl;
287    else
288      std::cout<<std::endl;
289  }
290  // Print solution if finished - we can't get names from Osi!
291
292  if (model.getMinimizationObjValue()<1.0e50) {
293    // post process
294    OsiSolverInterface * solver;
295    if (preProcess) {
296      process.postProcess(*model.solver());
297      // Solution now back in solver1
298      solver = & solver1;
299    } else {
300      solver = model.solver();
301    }
302    int numberColumns = solver->getNumCols();
303   
304    const double * solution = solver->getColSolution();
305   
306    int iColumn;
307    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
308   
309    std::cout<<"--------------------------------------"<<std::endl;
310    for (iColumn=0;iColumn<numberColumns;iColumn++) {
311      double value=solution[iColumn];
312      if (fabs(value)>1.0e-7&&solver->isInteger(iColumn)) 
313        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
314    }
315    std::cout<<"--------------------------------------"<<std::endl;
316 
317    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
318  }
319  return 0;
320}   
Note: See TracBrowser for help on using the repository browser.