source: trunk/Cbc/examples/fast0507.cpp

Last change on this file was 1898, checked in by stefan, 6 years ago

fixup examples

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.4 KB
Line 
1// $Id: fast0507.cpp 1898 2013-04-09 18:06:04Z unxusr $
2// Copyright (C) 2005, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include <cassert>
7#include <iomanip>
8
9#include "CoinPragma.hpp"
10
11// For Branch and bound
12#include "OsiSolverInterface.hpp"
13#include "CbcModel.hpp"
14#include "CbcBranchActual.hpp"
15#include "CbcBranchUser.hpp"
16#include "CbcBranchCut.hpp"
17#include "CbcBranchToFixLots.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;
73  if (argc>=2) mpsFileName = argv[1];
74  int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(),"");
75  if( numMpsReadErrors != 0 )
76  {
77     printf("%d errors reading MPS file\n", numMpsReadErrors);
78     return numMpsReadErrors;
79  }
80  double time1 = CoinCpuTime();
81
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  CbcSolver3 * osiclp = dynamic_cast< CbcSolver3*> (solver3);
137  assert (osiclp);
138  const double fractionFix=0.985;
139  osiclp->initialize(&model,NULL);
140  osiclp->setAlgorithm(2);
141  osiclp->setMemory(1000);
142  osiclp->setNested(fractionFix);
143  //osiclp->setNested(1.0); //off
144  // Set up some cut generators and defaults
145  // Probing first as gets tight bounds on continuous
146
147  CglProbing generator1;
148  generator1.setUsingObjective(true);
149  generator1.setMaxPass(3);
150  // Number of unsatisfied variables to look at
151  generator1.setMaxProbe(10);
152  // How far to follow the consequences
153  generator1.setMaxLook(50);
154  // Only look at rows with fewer than this number of elements
155  generator1.setMaxElements(200);
156  generator1.setRowCuts(3);
157
158  CglGomory generator2;
159  // try larger limit
160  generator2.setLimit(300);
161
162  CglKnapsackCover generator3;
163
164  CglOddHole generator4;
165  generator4.setMinimumViolation(0.005);
166  generator4.setMinimumViolationPer(0.00002);
167  // try larger limit
168  generator4.setMaximumEntries(200);
169
170  CglClique generator5;
171  generator5.setStarCliqueReport(false);
172  generator5.setRowCliqueReport(false);
173
174  CglMixedIntegerRounding mixedGen;
175  /* This is same as default constructor -
176     (1,true,1)
177      I presume if maxAggregate larger then slower but maybe better
178      criterion can be  1 through 3
179      Reference:
180      Hugues Marchand and Laurence A. Wolsey
181      Aggregation and Mixed Integer Rounding to Solve MIPs
182      Operations Research, 49(3), May-June 2001.
183   */
184  int maxAggregate=1;
185  bool multiply=true;
186  int criterion=1;
187  CglMixedIntegerRounding2 mixedGen2(maxAggregate,multiply,criterion);
188  CglFlowCover flowGen;
189 
190  // Add in generators
191  // Experiment with -1 and -99 etc
192  model.addCutGenerator(&generator1,-99,"Probing");
193  //model.addCutGenerator(&generator2,-1,"Gomory");
194  //model.addCutGenerator(&generator3,-1,"Knapsack");
195  //model.addCutGenerator(&generator4,-1,"OddHole");
196  //model.addCutGenerator(&generator5,-1,"Clique");
197  //model.addCutGenerator(&flowGen,-1,"FlowCover");
198  //model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
199  //model.addCutGenerator(&mixedGen2,-1,"MixedIntegerRounding2");
200  // Say we want timings
201  int numberGenerators = model.numberCutGenerators();
202  int iGenerator;
203  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
204    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
205    generator->setTiming(true);
206  }
207
208  // Allow rounding heuristic
209
210  CbcRounding heuristic1(model);
211  model.addHeuristic(&heuristic1);
212
213  // And Greedy heuristic
214
215  CbcHeuristicGreedyCover heuristic2(model);
216  // Use original upper and perturb more
217  heuristic2.setAlgorithm(11);
218  model.addHeuristic(&heuristic2);
219
220  // Redundant definition of default branching (as Default == User)
221  CbcBranchUserDecision branch;
222  model.setBranchingMethod(&branch);
223
224  // Definition of node choice
225  CbcCompareUser compare;
226  model.setNodeComparison(compare);
227
228  int iColumn;
229  int numberColumns = solver3->getNumCols();
230  // do pseudo costs
231  CbcObject ** objects = new CbcObject * [numberColumns+1];
232  const CoinPackedMatrix * matrix = solver3->getMatrixByCol();
233  // Column copy
234  const int * columnLength = matrix->getVectorLengths();
235  const double * objective = model.getObjCoefficients();
236  int n=0;
237  for (iColumn=0;iColumn<numberColumns;iColumn++) {
238    if (solver3->isInteger(iColumn)) {
239      double costPer = objective[iColumn]/ ((double) columnLength[iColumn]);
240      CbcSimpleIntegerPseudoCost * newObject =
241        new CbcSimpleIntegerPseudoCost(&model,n,iColumn,
242                                       costPer,costPer);
243      newObject->setMethod(3);
244      objects[n++]= newObject;
245    }
246  }
247  // and special fix lots branch
248  objects[n++]=new CbcBranchToFixLots(&model,-1.0e-6,fractionFix+0.01,1,0,NULL);
249  model.addObjects(n,objects);
250  for (iColumn=0;iColumn<n;iColumn++)
251    delete objects[iColumn];
252  delete [] objects;
253  // High priority for odd object
254  int followPriority=1;
255  model.passInPriorities(&followPriority,true);
256
257  // Do initial solve to continuous
258  model.initialSolve();
259
260  // Could tune more
261  model.setMinimumDrop(CoinMin(1.0,
262                             fabs(model.getMinimizationObjValue())*1.0e-3+1.0e-4));
263
264  if (model.getNumCols()<500)
265    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
266  else if (model.getNumCols()<5000)
267    model.setMaximumCutPassesAtRoot(100); // use minimum drop
268  else
269    model.setMaximumCutPassesAtRoot(20);
270  //model.setMaximumCutPasses(1);
271
272  // Do more strong branching if small
273  //if (model.getNumCols()<5000)
274  //model.setNumberStrong(10);
275  // Switch off strong branching if wanted
276  model.setNumberStrong(0);
277
278  model.solver()->setIntParam(OsiMaxNumIterationHotStart,100);
279
280  // If time is given then stop after that number of minutes
281  if (minutes>=0.0) {
282    std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
283    model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
284  }
285  // Switch off most output
286  if (model.getNumCols()<300000) {
287    model.messageHandler()->setLogLevel(1);
288    //model.solver()->messageHandler()->setLogLevel(0);
289  } else {
290    model.messageHandler()->setLogLevel(2);
291    model.solver()->messageHandler()->setLogLevel(1);
292  }
293  //model.messageHandler()->setLogLevel(2);
294  //model.solver()->messageHandler()->setLogLevel(2);
295  //model.setPrintFrequency(50);
296#define DEBUG_CUTS
297#ifdef DEBUG_CUTS
298  // Set up debugger by name (only if no preprocesing)
299  if (!preProcess) {
300    std::string problemName ;
301    //model.solver()->getStrParam(OsiProbName,problemName) ;
302    //model.solver()->activateRowCutDebugger(problemName.c_str()) ;
303    model.solver()->activateRowCutDebugger("cap6000a") ;
304  }
305#endif
306
307  // Do complete search
308  try {
309    model.branchAndBound();
310  }
311  catch (CoinError e) {
312    e.print();
313    if (e.lineNumber()>=0)
314      std::cout<<"This was from a CoinAssert"<<std::endl;
315    exit(0);
316  }
317  //void printHowMany();
318  //printHowMany();
319  std::cout<<mpsFileName<<" took "<<CoinCpuTime()-time1<<" seconds, "
320           <<model.getNodeCount()<<" nodes with objective "
321           <<model.getObjValue()
322           <<(!model.status() ? " Finished" : " Not finished")
323           <<std::endl;
324
325  // Print more statistics
326  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
327           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
328
329  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
330    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
331    std::cout<<generator->cutGeneratorName()<<" was tried "
332             <<generator->numberTimesEntered()<<" times and created "
333             <<generator->numberCutsInTotal()<<" cuts of which "
334             <<generator->numberCutsActive()<<" were active after adding rounds of cuts";
335    if (generator->timing())
336      std::cout<<" ( "<<generator->timeInCutGenerator()<<" seconds)"<<std::endl;
337    else
338      std::cout<<std::endl;
339  }
340  // Print solution if finished - we can't get names from Osi!
341
342  if (model.getMinimizationObjValue()<1.0e50) {
343    // post process
344    if (preProcess)
345      process.postProcess(*model.solver());
346    int numberColumns = model.solver()->getNumCols();
347   
348    const double * solution = model.solver()->getColSolution();
349   
350    int iColumn;
351    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
352   
353    std::cout<<"--------------------------------------"<<std::endl;
354    for (iColumn=0;iColumn<numberColumns;iColumn++) {
355      double value=solution[iColumn];
356      if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) 
357        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
358    }
359    std::cout<<"--------------------------------------"<<std::endl;
360 
361    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
362  }
363  return 0;
364}   
Note: See TracBrowser for help on using the repository browser.