source: branches/devel/Cbc/examples/fast0507b.cpp @ 467

Last change on this file since 467 was 333, checked in by andreasw, 13 years ago

finished examples subdir

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