← Back to branch summary

~ubuntu-branches/ubuntu/natty/coinor-cbc/natty

« back to all changes in this revision

Viewing changes to Cbc/examples/sample5.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2009-08-26 16:57:29 UTC
  • Revision ID: james.westby@ubuntu.com-20090826165729-ybrezxdybg0hd1u6
Tags: upstream-2.3.0
Import upstream version 2.3.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
Cbc/examples/sample5.cpp
 
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
 
 
52
This main program creates an integer model and then solves it
 
53
 
 
54
It then sets up some Cgl cut generators and calls branch and cut.
 
55
 
 
56
Branching is simple binary branching on integer variables.
 
57
 
 
58
Node selection is depth first until first solution is found and then
 
59
based on objective and number of unsatisfied integer variables.
 
60
In this example the functionality is the same as default but it is
 
61
a user comparison function.
 
62
 
 
63
Variable branching selection is on maximum minimum-of-up-down change
 
64
after strong branching on 5 variables closest to 0.5.
 
65
 
 
66
A simple rounding heuristic is used.
 
67
 
 
68
 
 
69
************************************************************************/
 
70
 
 
71
 
 
72
int 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
}