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

Last change on this file since 1898 was 1898, checked in by stefan, 6 years ago

fixup examples
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.0 KB
Line 
1// $Id: sample3.cpp 1898 2013-04-09 18:06:04Z 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  if (argc <= 1) {
94     printf("using %s <modelfile>\n", argv[0]);
95     return 1;
96  }
97
98  // Read in model using argv[1]
99  // and assert that it is a clean model
100  int numMpsReadErrors = solver1.readMps(argv[1],"");
101  if( numMpsReadErrors != 0 )
102  {
103     printf("%d errors reading MPS file\n", numMpsReadErrors);
104     return numMpsReadErrors;
105  }
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(CoinMin(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.