source: trunk/Samples/sample3.cpp @ 2

Last change on this file since 2 was 2, checked in by ladanyi, 17 years ago

Import of Coin Branch-and-Cut (formerly known as Sbb)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.0 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 <assert.h>
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 "CbcTreeLocal.hpp"
18#include "CbcCutGenerator.hpp"
19#include "CbcHeuristicUser.hpp"
20#ifdef COIN_USE_CLP
21#include "OsiClpSolverInterface.hpp"
22#endif
23#ifdef COIN_USE_OSL
24#include "OsiOslSolverInterface.hpp"
25#endif
26
27// Cuts
28
29#include "CglGomory.hpp"
30#include "CglProbing.hpp"
31#include "CglKnapsackCover.hpp"
32#include "CglOddHole.hpp"
33#include "CglClique.hpp"
34
35// Heuristics
36
37#include "CbcHeuristic.hpp"
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// See if option there and return integer value - or -123456
64bool option(int argc, const char *argv[],const char * check, int & value)
65{
66  value=-123456;
67  for (int i=1;i<argc;i++) {
68    if (char * x = strstr(argv[i],check)) {
69      // see if at beginning
70      if (x==argv[i]||(x==argv[i]+1&&argv[i][0]=='-')) {
71        // see if =
72        x = strchr(argv[i],'=');
73        if (x) {
74          value = atoi(x+1);
75        } else if (i<argc-1) {
76          value = atoi(argv[i+1]);
77        }
78        return true;
79      }
80    }
81  }
82  return false;
83}
84
85// ****** define comparison to choose best next node
86
87int main (int argc, const char *argv[])
88{
89
90  // Define your favorite OsiSolver
91 
92#ifdef COIN_USE_CLP
93  OsiClpSolverInterface solver1;
94  //solver1.messageHandler()->setLogLevel(0);
95  solver1.getModelPtr()->setDualBound(1.0e10);
96#endif
97#ifdef COIN_USE_OSL
98  OsiOslSolverInterface solver1;
99  //solver1.messageHandler()->setLogLevel(0);
100#endif
101
102  // Read in model using argv[1]
103  // and assert that it is a clean model
104  int numMpsReadErrors = solver1.readMps(argv[1],"");
105  assert(numMpsReadErrors==0);
106  // do here so integers correct
107  CbcModel model(solver1);
108  model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
109
110  // Set up some cut generators and defaults
111  // Probing first as gets tight bounds on continuous
112
113  CglProbing generator1;
114  generator1.setUsingObjective(true);
115  generator1.setMaxPass(3);
116  generator1.setMaxProbe(100);
117  generator1.setMaxLook(50);
118  generator1.setRowCuts(3);
119
120  CglGomory generator2;
121  // try larger limit
122  generator2.setLimit(300);
123
124  CglKnapsackCover generator3;
125
126  CglOddHole generator4;
127  generator4.setMinimumViolation(0.005);
128  generator4.setMinimumViolationPer(0.00002);
129  // try larger limit
130  generator4.setMaximumEntries(200);
131
132  CglClique generator5;
133
134  // Add in generators
135  model.addCutGenerator(&generator1,-1,"Probing");
136  // You may want to switch these off for local search on some problems
137  //model.addCutGenerator(&generator2,-1,"Gomory");
138  model.addCutGenerator(&generator2,-99,"Gomory");
139  //model.addCutGenerator(&generator3,-1,"Knapsack");
140  model.addCutGenerator(&generator4,-99,"OddHole");
141  model.addCutGenerator(&generator5,-99,"Clique");
142
143  // Allow rounding heuristic
144
145  CbcRounding heuristic1(model);
146  model.addHeuristic(&heuristic1);
147
148  // Redundant definition of default branching (as Default == User)
149  CbcBranchUserDecision branch;
150  model.setBranchingMethod(&branch);
151
152  // Definition of node choice
153  CbcCompareUser compare;
154  model.setNodeComparison(compare);
155
156  // Do initial solve to continuous
157  model.initialSolve();
158  //model.solver()->setHintParam(OsiDoScale,false,OsiHintTry);
159
160  // Could tune more
161  model.setMinimumDrop(min(1.0,
162                             fabs(model.getMinimizationObjValue())*1.0e-3+1.0e-4));
163
164  if (model.getNumCols()<500)
165    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
166  else if (model.getNumCols()<5000)
167    model.setMaximumCutPassesAtRoot(100); // use minimum drop
168  else
169    model.setMaximumCutPassesAtRoot(20);
170  //model.setMaximumCutPasses(5);
171
172  // Do more strong branching if small
173  if (model.getNumCols()<5000)
174    model.setNumberStrong(10);
175  // Switch off strong branching if wanted
176  //model.setNumberStrong(0);
177
178  model.solver()->setIntParam(OsiMaxNumIterationHotStart,100);
179
180  // If time is given then stop after that number of minutes
181  if (argc==3) {
182    int minutes = atoi(argv[2]);
183    if (minutes>0 && minutes<1000000) {
184      std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
185      model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
186      argc=0; // stop other options
187    }
188  }
189  int optionValue;
190  if(option( argc, argv ,"minute" , optionValue)) {
191    int minutes = optionValue;
192    if (minutes>0 && minutes<1000000) {
193      std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
194      model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
195    }
196  }
197 
198  // Switch off most output
199  if (model.getNumCols()<3000) {
200    model.messageHandler()->setLogLevel(1);
201    //model.solver()->messageHandler()->setLogLevel(0);
202  } else {
203    model.messageHandler()->setLogLevel(2);
204    model.solver()->messageHandler()->setLogLevel(1);
205  }
206  if(option( argc, argv ,"print" , optionValue)) {
207    if (optionValue==3) {
208      model.messageHandler()->setLogLevel(3);
209      model.solver()->messageHandler()->setLogLevel(3);
210    } else {
211      model.messageHandler()->setLogLevel(2);
212      model.solver()->messageHandler()->setLogLevel(1);
213    }
214  }
215  //model.setPrintFrequency(50);
216 
217  double time1 = CoinCpuTime();
218 
219  if(option( argc, argv ,"clique" , optionValue)) {
220    printf("Finding cliques\n");
221    // Find cliques
222    int numberColumns = model.getNumCols();
223    int numberIntegers = 0;
224    int * integerVariable = new int[numberColumns];
225    int i;
226    for ( i=0;i<numberColumns;i++) {
227      if (model.isInteger(i)) {
228        integerVariable[numberIntegers++]=i;
229        //model.solver()->setContinuous(i);
230      }
231    }
232    model.findCliques(false,2,1000);
233    // give cliques high priority but leave integers to improve time
234    int numberCliques = model.numberObjects()-numberIntegers;
235    int * priority = new int [numberIntegers+numberCliques];
236    for (i=0;i<numberIntegers;i++)
237      priority[i]=10000+i;
238    for (;i<numberIntegers+numberCliques;i++)
239      priority[i]=i;
240    model.passInPriorities(priority,false);
241    delete [] priority;
242    delete [] integerVariable;
243    model.messageHandler()->setLogLevel(2);
244  }
245  if(option( argc, argv ,"presolvelocal" , optionValue)) {
246    // integer presolve
247    CbcModel * model2 = model.integerPresolve();
248    if (model2) {
249      // Do complete search
250      model2->branchAndBound();
251      // get back solution
252      model.originalModel(model2,false);
253    } else {
254      // infeasible
255      exit(1);
256    }
257  } else if(option( argc, argv ,"presolve" , optionValue)) {
258    // integer presolve
259    CbcModel * model2 = model.integerPresolve();
260    if (model2) {
261      int maxNodes=2000;
262      int k=10;
263      CbcTreeLocal localTree(model2,NULL,k,0,1,10000,maxNodes);
264      model2->passInTreeHandler(localTree);
265      // Do complete search
266      model2->branchAndBound();
267      // get back solution
268      model.originalModel(model2,false);
269    } else {
270      // infeasible
271      exit(1);
272    }
273  } else if (option(argc,argv,"localprove",optionValue)) {
274    int maxNodes=2000;
275    int k=10;
276    CbcTreeLocal localTree(&model,NULL,k,0,1,10000,maxNodes);
277    model.passInTreeHandler(localTree);
278    model.branchAndBound();
279  } else if (option(argc,argv,"local",optionValue)) {
280    int maxNodes=2000;
281    int k=10;
282    double * solution=NULL;
283    // trying to get best solution to fast0507
284    // (so we can debug why localTree (prove) cut off solution!
285    int numberColumns = model.getNumCols();
286    if (numberColumns==63009) {
287      solution = new double [numberColumns];
288      memset(solution,0,numberColumns*sizeof(double));
289      int seq[] ={
290        245 ,246 ,395 ,582 ,813 ,1432 ,2009 ,2063 ,2455 ,2879 ,
291        3027 ,3116 ,3154 ,3258 ,3675 ,5548 ,5890 ,6229 ,6318 ,6595 ,
292        6852 ,6859 ,7279 ,7565 ,7604 ,7855 ,9160 ,9259 ,9261 ,9296 ,
293        9318 ,10080 ,10339 ,10349 ,10652 ,10874 ,11046 ,11396 ,11812 ,11968 ,
294        12129 ,12321 ,12495 ,12650 ,13182 ,13350 ,14451 ,15198 ,15586 ,17876 ,
295        18537 ,19742 ,19939 ,19969 ,20646 ,20667 ,20668 ,23810 ,25973 ,27238 ,
296        27510 ,27847 ,30708 ,31164 ,33189 ,36506 ,36881 ,38025 ,38070 ,38216 ,
297        38381 ,39076 ,39397 ,39708 ,40770 ,40831 ,41017 ,41164 ,41195 ,41227 ,
298        41384 ,41743 ,42451 ,42776 ,42833 ,43991 ,44904 ,45045 ,45718 ,47860 ,
299        47896 ,48180 ,48257 ,48461 ,48961 ,49227 ,51278 ,52534 ,53275 ,54856 ,
300        55672 ,55674 ,55760 ,55822 ,56641 ,56703 ,56892 ,56964 ,57117 ,57556 ,
301        57905 ,59936 ,61649 ,62319 ,62387 };
302      double intSolnV[]={
303        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
304        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
305        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
306        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
307        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
308        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
309        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
310        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
311        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
312        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
313        1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,1. ,
314        1. ,1. ,1. ,1. ,1. };
315      int n=sizeof(seq)/sizeof(int);
316      for (int i=0;i<n;i++) 
317        solution[seq[i]]=intSolnV[i];
318      k=50;
319    }
320    CbcTreeLocal localTree(&model,solution,k,0,50,10000,maxNodes);
321    delete [] solution;
322    model.passInTreeHandler(localTree);
323    model.branchAndBound();
324  } else if (option(argc,argv,"1local",optionValue)) {
325    // test giving cbc a solution
326    CbcModel model2 = model;
327    model2.setMaximumSolutions(1);
328    model2.branchAndBound();
329    if (model2.status()&&model2.getMinimizationObjValue()<1.0e50) {
330      // Definition of local search
331      const double * solution = model2.solver()->getColSolution();
332      CbcTreeLocal localTree(&model,solution,2);
333      model.passInTreeHandler(localTree);
334      model.branchAndBound();
335    } else {
336      model=model2;
337    }
338  } else {
339    // Do complete search
340 
341    model.branchAndBound();
342  }
343
344  std::cout<<argv[1]<<" took "<<CoinCpuTime()-time1<<" seconds, "
345           <<model.getNodeCount()<<" nodes with objective "
346           <<model.getObjValue()
347           <<(!model.status() ? " Finished" : " Not finished")
348           <<std::endl;
349
350  // Print more statistics
351  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
352           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
353
354  int numberGenerators = model.numberCutGenerators();
355  for (int iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
356    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
357    std::cout<<generator->cutGeneratorName()<<" was tried "
358             <<generator->numberTimesEntered()<<" times and created "
359             <<generator->numberCutsInTotal()<<" cuts of which "
360             <<generator->numberCutsActive()<<" were active after adding rounds of cuts"
361             <<std::endl;
362  }
363  if (model.numberGlobalViolations())
364    std::cout<<"Global cuts were active "<<model.numberGlobalViolations()<<" times"<<std::endl;
365  // Print solution if finished - we can't get names from Osi!
366
367  if (model.getMinimizationObjValue()<1.0e50) {
368    int numberColumns = model.solver()->getNumCols();
369   
370    const double * solution = model.solver()->getColSolution();
371   
372    int iColumn;
373    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
374   
375    std::cout<<"--------------------------------------"<<std::endl;
376    for (iColumn=0;iColumn<numberColumns;iColumn++) {
377      double value=solution[iColumn];
378      if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) 
379        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
380    }
381    std::cout<<"--------------------------------------"<<std::endl;
382 
383    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
384    int n=0;
385    int i;
386    bool comma=false;
387    bool newLine=false;
388    for ( i=0;i<numberColumns;i++) {
389      if(solution[i]>0.5&&model.solver()->isInteger(i)) {
390        if (comma)
391          printf(",");
392        if (newLine)
393          printf("\n");
394        printf("%d ",i);
395        comma=true;
396        newLine=false;
397        n++;
398        if (n==10) {
399          n=0;
400          newLine=true;
401        }
402      }
403    }
404    printf("};\n");
405    n=0;
406    comma=false;
407    newLine=false;
408    printf("\tdouble intSolnV[]={\n");
409    for ( i=0;i<numberColumns;i++) {
410      if(solution[i]>0.5&&model.solver()->isInteger(i)) {
411        if (comma)
412          printf(",");
413        if (newLine)
414          printf("\n");
415        int value = (int) (solution[i]+0.5);
416        printf("%d. ",value);
417        comma=true;
418        newLine=false;
419        n++;
420        if (n==10) {
421          n=0;
422          newLine=true;
423        }
424      }
425    }
426    printf("};\n");
427  }
428  return 0;
429}   
Note: See TracBrowser for help on using the repository browser.