source: trunk/Cbc/examples/sample3.cpp @ 1660

Last change on this file since 1660 was 1660, checked in by stefan, 8 years ago

change to new way of using and installing configuration header files

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