source: trunk/Samples/sample2.cpp @ 147

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

dynamic branching stuff

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