source: trunk/Samples/qmip.cpp @ 176

Last change on this file since 176 was 176, checked in by forrest, 16 years ago

as heuristics have moved

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.5 KB
Line 
1// Copyright (C) 2004, 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 <cassert>
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 "CbcCutGenerator.hpp"
18#include "CbcHeuristicLocal.hpp"
19#include "ClpQuadInterface.hpp"
20
21// Cuts - some may work but be very very careful
22
23#include "CglProbing.hpp"
24
25// Heuristics would need adapting
26
27#include "CbcHeuristic.hpp"
28
29
30// Time
31#include "CoinTime.hpp"
32
33
34/************************************************************************
35
36This main program reads in a quadratic integer model from an mps file.
37
38It then sets up some Cgl cut generators and calls branch and cut.
39
40Branching is simple binary branching on integer variables.
41
42Node selection is depth first until first solution is found and then
43based on objective and number of unsatisfied integer variables.
44In this example the functionality is the same as default but it is
45a user comparison function.
46
47Variable branching selection is on maximum minimum-of-up-down change
48after strong branching on 5 variables closest to 0.5.
49
50A simple rounding heuristic could be used.but is switched off as needs work for quadratic
51
52This is NOT meant to be a serious MIQP code;  it is to show how you can use
53ClpQuadInterface.hpp to solve a QP at each node.  You could pick up data in that interface
54and use any QP solver (e.g. one that works)
55
56************************************************************************/
57
58int main (int argc, const char *argv[])
59{
60
61  // Define a Solver which inherits from OsiClpsolverInterface -> OsiSolverInterface
62 
63  ClpQuadInterface solver1;
64
65  // Read in model using argv[1]
66  // must use clp to get a quadratic model
67  ClpSimplex * clp = solver1.getModelPtr();
68  int numMpsReadErrors = clp->readMps(argv[1]);
69  // and assert that it is a clean model
70  assert(numMpsReadErrors==0);
71
72  // This clones solver
73  CbcModel model(solver1);
74  // But now model doesn't know about integers!
75  const char * integerInfo = clp->integerInformation();
76  int numberColumns = clp->numberColumns();
77  // and point to solver
78  OsiSolverInterface * solver2 = model.solver();
79  for (int iColumn=0;iColumn<numberColumns;iColumn++) {
80    if (integerInfo[iColumn]) 
81      solver2->setInteger(iColumn);
82  }
83  // Okay - now we have a good MIQP solver
84  // Within branch and cut it is better (at present) to switch off all objectives
85
86  ClpQuadInterface * osiclp = dynamic_cast< ClpQuadInterface*> (solver2);
87  assert (osiclp);
88  // Set fake objective so Cbc not confused
89  osiclp->initialize();
90  solver2->setHintParam(OsiDoReducePrint,true,OsiHintTry);
91
92  // Set up some cut generators and defaults
93  // Probing first as gets tight bounds on continuous
94
95  CglProbing generator1;
96  // can not use objective
97  generator1.setUsingObjective(false);
98  generator1.setMaxPass(3);
99  generator1.setMaxProbe(100);
100  generator1.setMaxLook(50);
101  generator1.setRowCuts(3);
102
103  // Add in generators
104  // Only some generators work (and even then try without first)
105  model.addCutGenerator(&generator1,1,"Probing");
106  // Allow rounding heuristic
107
108  CbcRounding heuristic1(model);
109  // do not add yet as don't know how to deal with quadratic objective
110  //model.addHeuristic(&heuristic1);
111
112
113  // Redundant definition of default branching (as Default == User)
114  CbcBranchUserDecision branch;
115  model.setBranchingMethod(&branch);
116
117  // Definition of node choice
118  CbcCompareUser compare;
119  // breadth first
120  //compare.setWeight(0.0);
121  model.setNodeComparison(compare);
122
123
124  // Do initial solve to continuous
125  model.initialSolve();
126
127  // Could tune more
128  model.setMinimumDrop(min(1.0,
129                             fabs(model.getMinimizationObjValue())*1.0e-3+1.0e-4));
130
131  if (model.getNumCols()<500)
132    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
133  else if (model.getNumCols()<5000)
134    model.setMaximumCutPassesAtRoot(100); // use minimum drop
135  else
136    model.setMaximumCutPassesAtRoot(20);
137
138  // Switch off strong branching if wanted
139  //model.setNumberStrong(5);
140 
141  model.solver()->setIntParam(OsiMaxNumIterationHotStart,10000);
142
143  // If time is given then stop after that number of minutes
144  if (argc>2) {
145    int minutes = atoi(argv[2]);
146    std::cout<<"Stopping after "<<minutes<<" minutes"<<std::endl;
147    assert (minutes>=0);
148    model.setDblParam(CbcModel::CbcMaximumSeconds,60.0*minutes);
149  }
150  // Switch off most output
151  if (model.getNumCols()<3000) {
152    model.messageHandler()->setLogLevel(1);
153    //model.solver()->messageHandler()->setLogLevel(0);
154  } else {
155    model.messageHandler()->setLogLevel(2);
156    model.solver()->messageHandler()->setLogLevel(1);
157  }
158  model.setPrintFrequency(50);
159 
160  double time1 = CoinCpuTime();
161
162  // Do complete search
163 
164  model.branchAndBound();
165
166  std::cout<<argv[1]<<" took "<<CoinCpuTime()-time1<<" seconds, "
167           <<model.getNodeCount()<<" nodes with objective "
168           <<model.getObjValue()
169           <<(!model.status() ? " Finished" : " Not finished")
170           <<std::endl;
171
172  // Print more statistics
173  std::cout<<"Cuts at root node changed objective from "<<model.getContinuousObjective()
174           <<" to "<<model.rootObjectiveAfterCuts()<<std::endl;
175
176  int numberGenerators = model.numberCutGenerators();
177  for (int iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
178    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
179    std::cout<<generator->cutGeneratorName()<<" was tried "
180             <<generator->numberTimesEntered()<<" times and created "
181             <<generator->numberCutsInTotal()<<" cuts of which "
182             <<generator->numberCutsActive()<<" were active after adding rounds of cuts"
183             <<std::endl;
184  }
185  // Print solution if finished - we can't get names from Osi!
186
187  if (!model.status()&&model.getMinimizationObjValue()<1.0e50) {
188    int numberColumns = model.solver()->getNumCols();
189   
190    const double * solution = model.solver()->getColSolution();
191   
192    int iColumn;
193    std::cout<<std::setiosflags(std::ios::fixed|std::ios::showpoint)<<std::setw(14);
194   
195    std::cout<<"--------------------------------------"<<std::endl;
196    for (iColumn=0;iColumn<numberColumns;iColumn++) {
197      double value=solution[iColumn];
198      if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) 
199        std::cout<<std::setw(6)<<iColumn<<" "<<value<<std::endl;
200    }
201    std::cout<<"--------------------------------------"<<std::endl;
202 
203    std::cout<<std::resetiosflags(std::ios::fixed|std::ios::showpoint|std::ios::scientific);
204  }
205  return 0;
206}   
Note: See TracBrowser for help on using the repository browser.