source: trunk/Samples/fast0507b.cpp @ 176

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