source: trunk/Cbc/examples/fast0507.cpp @ 1422

Last change on this file since 1422 was 1067, checked in by ladanyi, 11 years ago

changed max/min to CoinMax/CoinMin?

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.2 KB
Line 
1// Copyright (C) 2005, 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 "CbcBranchActual.hpp"
16#include "CbcBranchUser.hpp"
17#include "CbcBranchCut.hpp"
18#include "CbcCompareUser.hpp"
19#include "CbcCutGenerator.hpp"
20#include "CbcHeuristicGreedy.hpp"
21#include "OsiClpSolverInterface.hpp"
22#include "CbcSolver3.hpp"
23
24// Cuts
25
26#include "CglGomory.hpp"
27#include "CglProbing.hpp"
28#include "CglKnapsackCover.hpp"
29#include "CglOddHole.hpp"
30#include "CglClique.hpp"
31#include "CglFlowCover.hpp"
32#include "CglMixedIntegerRounding.hpp"
33#include "CglMixedIntegerRounding2.hpp"
34// Preprocessing
35#include "CglPreProcess.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  CbcSolver3 solver1;
69
70  // Read in model using argv[1]
71  // and assert that it is a clean model
72  std::string mpsFileName = "../../Data/Sample/p0033.mps";
73  if (argc>=2) mpsFileName = argv[1];
74  int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(),"");
75  assert(numMpsReadErrors==0);
76  double time1 = CoinCpuTime();
77
78  /* Options are:
79     preprocess to do preprocessing
80     time in minutes
81     if 2 parameters and numeric taken as time
82  */
83  bool preProcess=false;
84  double minutes=-1.0;
85  int nGoodParam=0;
86  for (int iParam=2; iParam<argc;iParam++) {
87    if (!strcmp(argv[iParam],"preprocess")) {
88      preProcess=true;
89      nGoodParam++;
90    } else if (!strcmp(argv[iParam],"time")) {
91      if (iParam+1<argc&&isdigit(argv[iParam+1][0])) {
92        minutes=atof(argv[iParam+1]);
93        if (minutes>=0.0) {
94          nGoodParam+=2;
95          iParam++; // skip time
96        }
97      }
98    }
99  }
100  if (nGoodParam==0&&argc==3&&isdigit(argv[2][0])) {
101    // If time is given then stop after that number of minutes
102    minutes = atof(argv[2]);
103    if (minutes>=0.0) 
104      nGoodParam=1;
105  }
106  if (nGoodParam!=argc-2) {
107    printf("Usage <file> [preprocess] [time <minutes>] or <file> <minutes>\n");
108    exit(1);
109  }
110  solver1.initialSolve();
111  // Reduce printout
112  solver1.setHintParam(OsiDoReducePrint,true,OsiHintTry);
113  // Say we want scaling
114  //solver1.setHintParam(OsiDoScale,true,OsiHintTry);
115  //solver1.setCleanupScaling(1);
116  // See if we want preprocessing
117  OsiSolverInterface * solver2=&solver1;
118  CglPreProcess process;
119  if (preProcess) {
120    /* Do not try and produce equality cliques and
121       do up to 5 passes */
122    solver2 = process.preProcess(solver1,false,5);
123    if (!solver2) {
124      printf("Pre-processing says infeasible\n");
125      exit(2);
126    }
127    solver2->resolve();
128  }
129  CbcModel model(*solver2);
130  // Point to solver
131  OsiSolverInterface * solver3 = model.solver();
132  CbcSolver3 * osiclp = dynamic_cast< CbcSolver3*> (solver3);
133  assert (osiclp);
134  const double fractionFix=0.985;
135  osiclp->initialize(&model,NULL);
136  osiclp->setAlgorithm(2);
137  osiclp->setMemory(1000);
138  osiclp->setNested(fractionFix);
139  //osiclp->setNested(1.0); //off
140  // Set up some cut generators and defaults
141  // Probing first as gets tight bounds on continuous
142
143  CglProbing generator1;
144  generator1.setUsingObjective(true);
145  generator1.setMaxPass(3);
146  // Number of unsatisfied variables to look at
147  generator1.setMaxProbe(10);
148  // How far to follow the consequences
149  generator1.setMaxLook(50);
150  // Only look at rows with fewer than this number of elements
151  generator1.setMaxElements(200);
152  generator1.setRowCuts(3);
153
154  CglGomory generator2;
155  // try larger limit
156  generator2.setLimit(300);
157
158  CglKnapsackCover generator3;
159
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  /* This is same as default constructor -
172     (1,true,1)
173      I presume if maxAggregate larger then slower but maybe better
174      criterion can be  1 through 3
175      Reference:
176      Hugues Marchand and Laurence A. Wolsey
177      Aggregation and Mixed Integer Rounding to Solve MIPs
178      Operations Research, 49(3), May-June 2001.
179   */
180  int maxAggregate=1;
181  bool multiply=true;
182  int criterion=1;
183  CglMixedIntegerRounding2 mixedGen2(maxAggregate,multiply,criterion);
184  CglFlowCover flowGen;
185 
186  // Add in generators
187  // Experiment with -1 and -99 etc
188  model.addCutGenerator(&generator1,-99,"Probing");
189  //model.addCutGenerator(&generator2,-1,"Gomory");
190  //model.addCutGenerator(&generator3,-1,"Knapsack");
191  //model.addCutGenerator(&generator4,-1,"OddHole");
192  //model.addCutGenerator(&generator5,-1,"Clique");
193  //model.addCutGenerator(&flowGen,-1,"FlowCover");
194  //model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
195  //model.addCutGenerator(&mixedGen2,-1,"MixedIntegerRounding2");
196  // Say we want timings
197  int numberGenerators = model.numberCutGenerators();
198  int iGenerator;
199  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
200    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
201    generator->setTiming(true);
202  }
203
204  // Allow rounding heuristic
205
206  CbcRounding heuristic1(model);
207  model.addHeuristic(&heuristic1);
208
209  // And Greedy heuristic
210
211  CbcHeuristicGreedyCover heuristic2(model);
212  // Use original upper and perturb more
213  heuristic2.setAlgorithm(11);
214  model.addHeuristic(&heuristic2);
215
216  // Redundant definition of default branching (as Default == User)
217  CbcBranchUserDecision branch;
218  model.setBranchingMethod(&branch);
219
220  // Definition of node choice
221  CbcCompareUser compare;
222  model.setNodeComparison(compare);
223
224  int iColumn;
225  int numberColumns = solver3->getNumCols();
226  // do pseudo costs
227  CbcObject ** objects = new CbcObject * [numberColumns+1];
228  const CoinPackedMatrix * matrix = solver3->getMatrixByCol();
229  // Column copy
230  const int * columnLength = matrix->getVectorLengths();
231  const double * objective = model.getObjCoefficients();
232  int n=0;
233  for (iColumn=0;iColumn<numberColumns;iColumn++) {
234    if (solver3->isInteger(iColumn)) {
235      double costPer = objective[iColumn]/ ((double) columnLength[iColumn]);
236      CbcSimpleIntegerPseudoCost * newObject =
237        new CbcSimpleIntegerPseudoCost(&model,n,iColumn,
238                                       costPer,costPer);
239      newObject->setMethod(3);
240      objects[n++]= newObject;
241    }
242  }
243  // and special fix lots branch
244  objects[n++]=new CbcBranchToFixLots(&model,-1.0e-6,fractionFix+0.01,1,0,NULL);
245  model.addObjects(n,objects);
246  for (iColumn=0;iColumn<n;iColumn++)
247    delete objects[iColumn];
248  delete [] objects;
249  // High priority for odd object
250  int followPriority=1;
251  model.passInPriorities(&followPriority,true);
252
253  // Do initial solve to continuous
254  model.initialSolve();
255
256  // Could tune more
257  model.setMinimumDrop(CoinMin(1.0,
258                             fabs(model.getMinimizationObjValue())*1.0e-3+1.0e-4));
259
260  if (model.getNumCols()<500)
261    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
262  else if (model.getNumCols()<5000)
263    model.setMaximumCutPassesAtRoot(100); // use minimum drop
264  else
265    model.setMaximumCutPassesAtRoot(20);
266  //model.setMaximumCutPasses(1);
267
268  // Do more strong branching if small
269  //if (model.getNumCols()<5000)
270  //model.setNumberStrong(10);
271  // Switch off strong branching if wanted
272  model.setNumberStrong(0);
273
274  model.solver()->setIntParam(OsiMaxNumIterationHotStart,100);
275
276  // If time is given then stop after that number of minutes
277  if (minutes>=0.0) {
278    std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
279    model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
280  }
281  // Switch off most output
282  if (model.getNumCols()<300000) {
283    model.messageHandler()->setLogLevel(1);
284    //model.solver()->messageHandler()->setLogLevel(0);
285  } else {
286    model.messageHandler()->setLogLevel(2);
287    model.solver()->messageHandler()->setLogLevel(1);
288  }
289  //model.messageHandler()->setLogLevel(2);
290  //model.solver()->messageHandler()->setLogLevel(2);
291  //model.setPrintFrequency(50);
292#define DEBUG_CUTS
293#ifdef DEBUG_CUTS
294  // Set up debugger by name (only if no preprocesing)
295  if (!preProcess) {
296    std::string problemName ;
297    //model.solver()->getStrParam(OsiProbName,problemName) ;
298    //model.solver()->activateRowCutDebugger(problemName.c_str()) ;
299    model.solver()->activateRowCutDebugger("cap6000a") ;
300  }
301#endif
302
303  // Do complete search
304  try {
305    model.branchAndBound();
306  }
307  catch (CoinError e) {
308    e.print();
309    if (e.lineNumber()>=0)
310      std::cout<<"This was from a CoinAssert"<<std::endl;
311    exit(0);
312  }
313  //void printHowMany();
314  //printHowMany();
315  std::cout<<mpsFileName<<" took "<<CoinCpuTime()-time1<<" seconds, "
316           <<model.getNodeCount()<<" nodes with objective "
317           <<model.getObjValue()
318           <<(!model.status() ? " Finished" : " Not finished")
319           <<std::endl;
320
321  // Print more statistics
322  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
323           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
324
325  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
326    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
327    std::cout<<generator->cutGeneratorName()<<" was tried "
328             <<generator->numberTimesEntered()<<" times and created "
329             <<generator->numberCutsInTotal()<<" cuts of which "
330             <<generator->numberCutsActive()<<" were active after adding rounds of cuts";
331    if (generator->timing())
332      std::cout<<" ( "<<generator->timeInCutGenerator()<<" seconds)"<<std::endl;
333    else
334      std::cout<<std::endl;
335  }
336  // Print solution if finished - we can't get names from Osi!
337
338  if (model.getMinimizationObjValue()<1.0e50) {
339    // post process
340    if (preProcess)
341      process.postProcess(*model.solver());
342    int numberColumns = model.solver()->getNumCols();
343   
344    const double * solution = model.solver()->getColSolution();
345   
346    int iColumn;
347    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
348   
349    std::cout<<"--------------------------------------"<<std::endl;
350    for (iColumn=0;iColumn<numberColumns;iColumn++) {
351      double value=solution[iColumn];
352      if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) 
353        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
354    }
355    std::cout<<"--------------------------------------"<<std::endl;
356 
357    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
358  }
359  return 0;
360}   
Note: See TracBrowser for help on using the repository browser.