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

Last change on this file since 1464 was 1464, checked in by stefan, 9 years ago

merge split branch into trunk; fix some examples

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