source: trunk/Samples/sample5.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: 9.9 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 "CbcCompareUser.hpp"
17#include "CbcCutGenerator.hpp"
18#include "CbcHeuristicLocal.hpp"
19#ifdef COIN_USE_CLP
20#include "OsiClpSolverInterface.hpp"
21#endif
22#ifdef COIN_USE_OSL
23#include "OsiOslSolverInterface.hpp"
24#endif
25
26// Cuts
27
28#include "CglGomory.hpp"
29#include "CglProbing.hpp"
30#include "CglKnapsackCover.hpp"
31#include "CglOddHole.hpp"
32#include "CglClique.hpp"
33#include "CglFlowCover.hpp"
34#include "CglMixedIntegerRounding.hpp"
35
36// Heuristics
37
38#include "CbcHeuristic.hpp"
39
40// Methods of building
41
42#include "CoinBuild.hpp"
43#include "CoinModel.hpp"
44
45#include  "CoinTime.hpp"
46
47
48/************************************************************************
49
50This main program creates an integer model and then solves it
51
52It then sets up some Cgl cut generators and calls branch and cut.
53
54Branching is simple binary branching on integer variables.
55
56Node selection is depth first until first solution is found and then
57based on objective and number of unsatisfied integer variables.
58In this example the functionality is the same as default but it is
59a user comparison function.
60
61Variable branching selection is on maximum minimum-of-up-down change
62after strong branching on 5 variables closest to 0.5.
63
64A simple rounding heuristic is used.
65
66
67************************************************************************/
68
69
70int main (int argc, const char *argv[])
71{
72
73  /* Define your favorite OsiSolver.
74
75     CbcModel clones the solver so use solver1 up to the time you pass it
76     to CbcModel then use a pointer to cloned solver (model.solver())
77  */
78 
79#ifdef COIN_USE_CLP
80  OsiClpSolverInterface solver1;
81#elif COIN_USE_OSL
82  OsiOslSolverInterface solver1;
83#endif
84  /* From now on we can build model in a solver independent way.
85     You can add rows one at a time but for large problems this is slow so
86     this example uses CoinBuild or CoinModel
87  */
88  OsiSolverInterface * solver = &solver1;
89  // Data (is exmip1.mps in Mps/Sample
90  // Objective
91  double objValue[]={1.0,2.0,0.0,0.0,0.0,0.0,0.0,-1.0};
92  // Lower bounds for columns
93  double columnLower[]={2.5,0.0,0.0,0.0,0.5,0.0,0.0,0.0};
94  // Upper bounds for columns
95  double columnUpper[]={COIN_DBL_MAX,4.1,1.0,1.0,4.0,
96                  COIN_DBL_MAX,COIN_DBL_MAX,4.3};
97  // Lower bounds for row activities
98  double rowLower[]={2.5,-COIN_DBL_MAX,-COIN_DBL_MAX,1.8,3.0};
99  // Upper bounds for row activities
100  double rowUpper[]={COIN_DBL_MAX,2.1,4.0,5.0,15.0};
101  // Matrix stored packed
102  int column[] = {0,1,3,4,7,
103                  1,2,
104                  2,5,
105                  3,6,
106                  4,7};
107  double element[] = {3.0,1.0,-2.0,-1.0,-1.0,
108                      2.0,1.1,
109                      1.0,1.0,
110                      2.8,-1.2,
111                      1.0,1.9};
112  int starts[]={0,5,7,9,11,13};
113  // Integer variables (note upper bound already 1.0)
114  int whichInt[]={2,3};
115  int numberRows=(int) (sizeof(rowLower)/sizeof(double));
116  int numberColumns=(int) (sizeof(columnLower)/sizeof(double));
117#define BUILD 2
118#if BUILD==1
119  // Using CoinBuild
120  // First do columns (objective and bounds)
121  int i;
122  // We are not adding elements
123  for (i=0;i<numberColumns;i++) {
124    solver->addCol(0,NULL,NULL,columnLower[i],columnUpper[i],
125                    objValue[i]);
126  }
127  // mark as integer
128  for (i=0;i<(int) (sizeof(whichInt)/sizeof(int));i++)
129    solver->setInteger(whichInt[i]);
130  // Now build rows
131  CoinBuild build;
132  for (i=0;i<numberRows;i++) {
133    int startRow = starts[i];
134    int numberInRow = starts[i+1]-starts[i];
135    build.addRow(numberInRow,column+startRow,element+startRow,
136                 rowLower[i],rowUpper[i]);
137  } 
138  // add rows into solver
139  solver->addRows(build);
140#else
141  /* using CoinModel - more flexible but still beta.
142     Can do exactly same way but can mix and match much more.
143     Also all operations are on building object
144  */
145  CoinModel build;
146  // First do columns (objective and bounds)
147  int i;
148  for (i=0;i<numberColumns;i++) {
149    build.setColumnBounds(i,columnLower[i],columnUpper[i]);
150    build.setObjective(i,objValue[i]);
151  }
152  // mark as integer
153  for (i=0;i<(int) (sizeof(whichInt)/sizeof(int));i++)
154    build.setInteger(whichInt[i]);
155  // Now build rows
156  for (i=0;i<numberRows;i++) {
157    int startRow = starts[i];
158    int numberInRow = starts[i+1]-starts[i];
159    build.addRow(numberInRow,column+startRow,element+startRow,
160                 rowLower[i],rowUpper[i]);
161  } 
162  // add rows into solver
163  solver->loadFromCoinModel(build);
164#endif
165
166  // Pass to solver
167  CbcModel model(*solver);
168  model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
169
170
171  // Set up some cut generators and defaults
172  // Probing first as gets tight bounds on continuous
173
174  CglProbing generator1;
175  generator1.setUsingObjective(true);
176  generator1.setMaxPass(3);
177  generator1.setMaxProbe(100);
178  generator1.setMaxLook(50);
179  generator1.setRowCuts(3);
180  //  generator1.snapshot(*model.solver());
181  //generator1.createCliques(*model.solver(),2,1000,true);
182  //generator1.setMode(0);
183
184  CglGomory generator2;
185  // try larger limit
186  generator2.setLimit(300);
187
188  CglKnapsackCover generator3;
189
190  CglOddHole generator4;
191  generator4.setMinimumViolation(0.005);
192  generator4.setMinimumViolationPer(0.00002);
193  // try larger limit
194  generator4.setMaximumEntries(200);
195
196  CglClique generator5;
197  generator5.setStarCliqueReport(false);
198  generator5.setRowCliqueReport(false);
199
200  CglMixedIntegerRounding mixedGen;
201  CglFlowCover flowGen;
202 
203  // Add in generators
204  model.addCutGenerator(&generator1,-1,"Probing");
205  model.addCutGenerator(&generator2,-1,"Gomory");
206  model.addCutGenerator(&generator3,-1,"Knapsack");
207  model.addCutGenerator(&generator4,-1,"OddHole");
208  model.addCutGenerator(&generator5,-1,"Clique");
209  model.addCutGenerator(&flowGen,-1,"FlowCover");
210  model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
211
212#ifdef COIN_USE_CLP
213  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (model.solver());
214  // go faster stripes
215  if (osiclp->getNumRows()<300&&osiclp->getNumCols()<500) {
216    osiclp->setupForRepeatedUse(2,0);
217    printf("trying slightly less reliable but faster version (? Gomory cuts okay?)\n");
218    printf("may not be safe if doing cuts in tree which need accuracy (level 2 anyway)\n");
219  }
220#endif
221
222  // Allow rounding heuristic
223
224  CbcRounding heuristic1(model);
225  model.addHeuristic(&heuristic1);
226
227  // And local search when new solution found
228
229  CbcHeuristicLocal heuristic2(model);
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(5);
254
255  // Switch off strong branching if wanted
256  // model.setNumberStrong(0);
257  // Do more strong branching if small
258  if (model.getNumCols()<5000)
259    model.setNumberStrong(10);
260
261  model.solver()->setIntParam(OsiMaxNumIterationHotStart,100);
262
263  // If time is given then stop after that number of minutes
264  if (argc>2) {
265    int minutes = atoi(argv[2]);
266    std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
267    assert (minutes>=0);
268    model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
269  }
270  // Switch off most output
271  if (model.getNumCols()<3000) {
272    model.messageHandler()->setLogLevel(1);
273    //model.solver()->messageHandler()->setLogLevel(0);
274  } else {
275    model.messageHandler()->setLogLevel(2);
276    model.solver()->messageHandler()->setLogLevel(1);
277  }
278  double time1 = CoinCpuTime();
279
280  // Do complete search
281 
282  model.branchAndBound();
283
284  std::cout<<" Branch and cut took "<<CoinCpuTime()-time1<<" seconds, "
285           <<model.getNodeCount()<<" nodes with objective "
286           <<model.getObjValue()
287           <<(!model.status() ? " Finished" : " Not finished")
288           <<std::endl;
289
290  // Print more statistics
291  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
292           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
293
294  int numberGenerators = model.numberCutGenerators();
295  for (int iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
296    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
297    std::cout<<generator->cutGeneratorName()<<" was tried "
298             <<generator->numberTimesEntered()<<" times and created "
299             <<generator->numberCutsInTotal()<<" cuts of which "
300             <<generator->numberCutsActive()<<" were active after adding rounds of cuts"
301             <<std::endl;
302  }
303  // Print solution if any - we can't get names from Osi!
304
305  if (model.getMinimizationObjValue()<1.0e50) {
306    int numberColumns = model.solver()->getNumCols();
307   
308    const double * solution = model.solver()->getColSolution();
309   
310    int iColumn;
311    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
312   
313    std::cout<<"--------------------------------------"<<std::endl;
314    for (iColumn=0;iColumn<numberColumns;iColumn++) {
315      double value=solution[iColumn];
316      if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) 
317        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
318    }
319    std::cout<<"--------------------------------------"<<std::endl;
320 
321    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
322  }
323  return 0;
324}   
Note: See TracBrowser for help on using the repository browser.