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

Last change on this file since 1574 was 1574, checked in by lou, 8 years ago

Change to EPL license notice.

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