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

Last change on this file since 1565 was 1464, checked in by stefan, 9 years ago

merge split branch into trunk; fix some examples

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