source: trunk/Samples/sample2.cpp @ 176

Last change on this file since 176 was 176, checked in by forrest, 16 years ago

as heuristics have moved

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.0 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 "CbcHeuristicLocal.hpp"
19#include "OsiClpSolverInterface.hpp"
20
21// Cuts
22
23#include "CglGomory.hpp"
24#include "CglProbing.hpp"
25#include "CglKnapsackCover.hpp"
26#include "CglRedSplit.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  CglRedSplit generator4;
154  // try larger limit
155  generator4.setLimit(200);
156
157  CglClique generator5;
158  generator5.setStarCliqueReport(false);
159  generator5.setRowCliqueReport(false);
160
161  CglMixedIntegerRounding2 mixedGen;
162  CglFlowCover flowGen;
163 
164  // Add in generators
165  // Experiment with -1 and -99 etc
166  model.addCutGenerator(&generator1,-1,"Probing");
167  model.addCutGenerator(&generator2,-1,"Gomory");
168  model.addCutGenerator(&generator3,-1,"Knapsack");
169  //model.addCutGenerator(&generator4,-1,"RedSplit");
170  model.addCutGenerator(&generator5,-1,"Clique");
171  model.addCutGenerator(&flowGen,-1,"FlowCover");
172  model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
173  // Say we want timings
174  int numberGenerators = model.numberCutGenerators();
175  int iGenerator;
176  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
177    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
178    generator->setTiming(true);
179  }
180  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (model.solver());
181  // go faster stripes
182  if (osiclp) {
183    // Turn this off if you get problems
184    // Used to be automatically set
185    osiclp->setSpecialOptions(128);
186    if(osiclp->getNumRows()<300&&osiclp->getNumCols()<500) {
187      //osiclp->setupForRepeatedUse(2,0);
188      osiclp->setupForRepeatedUse(0,0);
189    }
190  } 
191  model.messagesPointer()->setDetailMessage(0,61);
192  // Allow rounding heuristic
193
194  CbcRounding heuristic1(model);
195  model.addHeuristic(&heuristic1);
196
197  // And local search when new solution found
198
199  CbcHeuristicLocal heuristic2(model);
200  model.addHeuristic(&heuristic2);
201
202  // Redundant definition of default branching (as Default == User)
203  CbcBranchUserDecision branch;
204  model.setBranchingMethod(&branch);
205
206  // Definition of node choice
207  CbcCompareUser compare;
208  model.setNodeComparison(compare);
209
210  // Do initial solve to continuous
211  model.initialSolve();
212
213  // Could tune more
214  double objValue = model.solver()->getObjSense()*model.solver()->getObjValue();
215  double minimumDropA=CoinMin(1.0,fabs(objValue)*1.0e-3+1.0e-4);
216  double minimumDrop= fabs(objValue)*1.0e-4+1.0e-4;
217  printf("min drop %g (A %g)\n",minimumDrop,minimumDropA);
218  model.setMinimumDrop(minimumDrop);
219
220  if (model.getNumCols()<500)
221    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
222  else if (model.getNumCols()<5000)
223    model.setMaximumCutPassesAtRoot(100); // use minimum drop
224  else
225    model.setMaximumCutPassesAtRoot(20);
226  model.setMaximumCutPasses(10);
227  //model.setMaximumCutPasses(2);
228
229  // Switch off strong branching if wanted
230  // model.setNumberStrong(0);
231  // Do more strong branching if small
232  if (model.getNumCols()<5000)
233    model.setNumberStrong(10);
234  model.setNumberStrong(20);
235  //model.setNumberStrong(5);
236  model.setNumberBeforeTrust(5);
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  //#define DEBUG_CUTS
257#ifdef DEBUG_CUTS
258  // Set up debugger by name (only if no preprocesing)
259  if (!preProcess) {
260    std::string problemName ;
261    model.solver()->getStrParam(OsiProbName,problemName) ;
262    model.solver()->activateRowCutDebugger(problemName.c_str()) ;
263  }
264#endif
265
266  // Do complete search
267 
268  model.branchAndBound();
269
270  std::cout<<mpsFileName<<" took "<<CoinCpuTime()-time1<<" seconds, "
271           <<model.getNodeCount()<<" nodes with objective "
272           <<model.getObjValue()
273           <<(!model.status() ? " Finished" : " Not finished")
274           <<std::endl;
275
276  // Print more statistics
277  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
278           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
279
280  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
281    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
282    std::cout<<generator->cutGeneratorName()<<" was tried "
283             <<generator->numberTimesEntered()<<" times and created "
284             <<generator->numberCutsInTotal()<<" cuts of which "
285             <<generator->numberCutsActive()<<" were active after adding rounds of cuts";
286    if (generator->timing())
287      std::cout<<" ( "<<generator->timeInCutGenerator()<<" seconds)"<<std::endl;
288    else
289      std::cout<<std::endl;
290  }
291  // Print solution if finished - we can't get names from Osi! - so get from OsiClp
292
293  if (model.getMinimizationObjValue()<1.0e50) {
294    // post process
295    OsiSolverInterface * solver;
296    if (preProcess) {
297      process.postProcess(*model.solver());
298      // Solution now back in solver1
299      solver = & solver1;
300    } else {
301      solver = model.solver();
302    }
303    int numberColumns = solver->getNumCols();
304   
305    const double * solution = solver->getColSolution();
306
307    // Get names from solver1 (as OsiSolverInterface may lose)
308    std::vector<std::string> columnNames = *solver1.getModelPtr()->columnNames();
309   
310    int iColumn;
311    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
312   
313    std::cout<<"--------------------------------------"<<std::endl;
314    for (iColumn=0;iColumn<numberColumns;iColumn++) {
315      double value=solution[iColumn];
316      if (fabs(value)>1.0e-7&&solver->isInteger(iColumn)) 
317        std::cout<<std::setw(6)<<iColumn<<" "
318                 <<columnNames[iColumn]<<" "
319                 <<value<<std::endl;
320    }
321    std::cout<<"--------------------------------------"<<std::endl;
322 
323    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
324  }
325  return 0;
326}   
Note: See TracBrowser for help on using the repository browser.