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

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