source: stable/1.1/Bonmin/src/Algorithms/OaGenerators/BonOACutGenerator2.cpp @ 1522

Last change on this file since 1522 was 1522, checked in by pbonami, 10 years ago

Increase OA node limit

File size: 10.6 KB
Line 
1// (C) Copyright Carnegie Mellon University 2005, 2006
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// Authors :
6// P. Bonami, Carnegie Mellon University
7//
8// Date : 05/26/2005
9//#define OA_DEBUG
10
11#include "BonOACutGenerator2.hpp"
12#include "BonminConfig.h"
13
14#include "OsiClpSolverInterface.hpp"
15
16#include "CbcModel.hpp"
17#include "BonCbcLpStrategy.hpp"
18#ifdef COIN_HAS_CPX
19#include "OsiCpxSolverInterface.hpp"
20#endif
21#include "OsiAuxInfo.hpp"
22
23#include <climits>
24
25namespace Bonmin
26{
27
28/// Constructor with basic setup
29  OACutGenerator2::OACutGenerator2(BabSetupBase & b):
30      OaDecompositionBase(b, true, false)
31  {
32    int ivalue;
33    b.options()->GetEnumValue("milp_subsolver",ivalue,"bonmin.");
34    if (ivalue <= 0) {//uses cbc
35      //nothing to do?
36    }
37    else if (ivalue == 1) {
38      int nodeS, nStrong, nTrust, mig, mir, probe, cover;
39      b.options()->GetEnumValue("node_comparison",nodeS,"milp_sub.");
40      b.options()->GetIntegerValue("number_strong_branch",nStrong,"milp_sub.");
41      b.options()->GetIntegerValue("number_before_trust", nTrust,"milp_sub.");
42      b.options()->GetIntegerValue("Gomory_cuts", mig,"milp_sub.");
43      //b.options()->GetIntegerValue("probing_cuts",probe,"milp_sub.");
44      probe = 0;
45      b.options()->GetIntegerValue("mir_cuts",mir,"milp_sub.");
46      b.options()->GetIntegerValue("cover_cuts",cover,"milp_sub.");
47     
48      CbcStrategy * strategy =
49        new CbcOaStrategy(mig, probe, mir, cover, nTrust,
50            nStrong, nodeS, parameters_.cbcIntegerTolerance_, parameters_.subMilpLogLevel_);
51      setStrategy(*strategy);
52      delete strategy;
53
54    }
55    else if (ivalue == 2) {
56#ifdef COIN_HAS_CPX
57      OsiCpxSolverInterface * cpxSolver = new OsiCpxSolverInterface;
58      b.nonlinearSolver()->extractLinearRelaxation(*cpxSolver);
59      assignLpInterface(cpxSolver);
60#else
61      std::cerr << "You have set an option to use CPLEX as the milp\n"
62      << "subsolver in oa decomposition. However, apparently\n"
63      << "CPLEX is not configured to be used in bonmin.\n"
64      << "See the manual for configuring CPLEX\n";
65      throw -1;
66#endif
67    }
68
69    double oaTime;
70    b.options()->GetNumericValue("oa_dec_time_limit",oaTime,"bonmin.");
71    parameter().localSearchNodeLimit_ = INT_MAX;
72    parameter().maxLocalSearch_ = INT_MAX;
73    parameter().maxLocalSearchPerNode_ = INT_MAX;
74    parameter().maxLocalSearchTime_ =
75      Ipopt::Min(b.getDoubleParameter(BabSetupBase::MaxTime), oaTime);
76  }
77  OACutGenerator2::~OACutGenerator2()
78  {}
79
80  /// virutal method to decide if local search is performed
81  bool
82  OACutGenerator2::doLocalSearch() const
83  {
84    return (nLocalSearch_<parameters_.maxLocalSearch_ &&
85        parameters_.localSearchNodeLimit_ > 0 &&
86        CoinCpuTime() - timeBegin_ < parameters_.maxLocalSearchTime_);
87  }
88  /// virtual method which performs the OA algorithm by modifying lp and nlp.
89  double
90  OACutGenerator2::performOa(OsiCuts &cs,
91      solverManip &nlpManip,
92      solverManip &lpManip,
93      SubMipSolver * &subMip,
94      OsiBabSolver * babInfo,
95      double & cutoff) const
96  {
97    double lastPeriodicLog= CoinCpuTime();
98
99    //const int numcols = nlp_->getNumCols();
100
101
102    bool isInteger = false;
103
104    OsiSolverInterface * lp = lpManip.si();
105    OsiBranchingInformation info(lp, false);
106    bool milpOptimal = 1;
107
108
109    double milpBound = -COIN_DBL_MAX;
110    bool milpFeasible = 1;
111    bool feasible = 1;
112    if (subMip)//Perform a local search
113    {
114      subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
115          (parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime()) /* time limit */,
116          parameters_.localSearchNodeLimit_);
117      milpBound = subMip->lowBound();
118      milpOptimal = subMip->optimal();
119
120      feasible = milpBound < cutoff;
121      milpFeasible = feasible;
122      isInteger = subMip->getLastSolution() != NULL;
123      nLocalSearch_++;
124
125      if (milpOptimal)
126        handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
127      else
128      {
129        handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
130      }
131    }
132    int numberPasses = 0;
133
134#ifdef OA_DEBUG
135    bool foundSolution = 0;
136#endif
137    double * nlpSol = NULL;
138
139    while (isInteger && feasible ) {
140      numberPasses++;
141
142      //after a prescribed elapsed time give some information to user
143      double time = CoinCpuTime();
144      if (time - lastPeriodicLog > parameters_.logFrequency_) {
145        double lb = (subMip == NULL) ?lp->getObjValue() : subMip->getLowerBound();
146        handler_->message(PERIODIC_MSG,messages_)
147        <<time - timeBegin_<<cutoff
148        <<lb
149        <<CoinMessageEol;
150        lastPeriodicLog = CoinCpuTime();
151      }
152
153
154      //setup the nlp
155      int numberCutsBefore = cs.sizeRowCuts();
156
157      //Fix the variable which have to be fixed, after having saved the bounds
158      const double * colsol = subMip == NULL ? lp->getColSolution():
159          subMip->getLastSolution();
160      info.solution_ = colsol;
161      nlpManip.fixIntegers(info);
162
163
164      if (solveNlp(babInfo, cutoff)) {
165        //nlp solved and feasible
166        // Update the cutoff
167        cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
168        // Update the lp solver cutoff
169        lp->setDblParam(OsiDualObjectiveLimit, cutoff);
170      }
171
172      nlpSol = const_cast<double *>(nlp_->getColSolution());
173
174      // Get the cuts outer approximation at the current point
175      const double * toCut = (parameter().addOnlyViolated_)?
176          colsol:NULL;
177      nlp_->getOuterApproximation(cs, nlpSol, 1, toCut,
178                                  parameter().global_);
179
180      int numberCuts = cs.sizeRowCuts() - numberCutsBefore;
181      if (numberCuts > 0)
182        lpManip.installCuts(cs, numberCuts);
183
184      lp->resolve();
185      double objvalue = lp->getObjValue();
186      //milpBound = max(milpBound, lp->getObjValue());
187      feasible = (lp->isProvenOptimal() &&
188          !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
189      //if value of integers are unchanged then we have to get out
190      bool changed = !feasible;//if lp is infeasible we don't have to check anything
191      info.solution_ = lp->getColSolution();
192      if (!changed)
193        changed = nlpManip.isDifferentOnIntegers(lp->getColSolution());
194      if (changed) {
195
196        isInteger = lpManip.integerFeasible(info);
197      }
198      else {
199        isInteger = 0;
200        //        if(!fixed)//fathom on bounds
201        milpBound = 1e200;
202      }
203#ifdef OA_DEBUG
204      printf("Obj value after cuts %g %d rows\n",lp->getObjValue(),
205          numberCuts) ;
206#endif
207      //check time
208      if (CoinCpuTime() - timeBegin_ > parameters_.maxLocalSearchTime_)
209        break;
210      //do we perform a new local search ?
211      if (milpOptimal && feasible && !isInteger &&
212          nLocalSearch_ < parameters_.maxLocalSearch_ &&
213          numberPasses < parameters_.maxLocalSearchPerNode_ &&
214          parameters_.localSearchNodeLimit_ > 0) {
215
216        /** do we have a subMip? if not create a new one. */
217        if (subMip == NULL) subMip = new SubMipSolver(lp, parameters_.strategy());
218
219        nLocalSearch_++;
220
221        subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
222            parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime(),
223            parameters_.localSearchNodeLimit_);
224
225        milpBound = subMip->lowBound();
226
227        if (subMip->optimal())
228          handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
229        else
230          handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
231
232
233        colsol = const_cast<double *> (subMip->getLastSolution());
234        isInteger = colsol != 0;
235
236        feasible =  (milpBound < cutoff);
237
238        if (feasible && isInteger) {
239          bool changed = false;
240          changed = nlpManip.isDifferentOnIntegers(colsol);//If integer solution is the same as nlp
241          //solution problem is solved
242          if (!changed) {
243            feasible = 0;
244            milpBound = 1e50;
245          }
246          milpFeasible = feasible;
247        }
248        if (subMip->optimal())
249          milpOptimal = 1;
250        else {
251          milpOptimal = 0;
252        }
253
254        if (milpBound < cutoff)
255          handler_->message(UPDATE_LB, messages_)<<milpBound<<CoinCpuTime() - timeBegin_<<CoinMessageEol;
256        else {
257          milpBound = 1e50;
258          feasible = 0;
259          handler_->message(OASUCCESS, messages_)<<CoinCpuTime() - timeBegin_ <<CoinMessageEol;
260        }
261      }/** endif localSearch*/
262      else if (subMip!=NULL) {
263        delete subMip;
264        subMip = NULL;
265      }
266    }
267
268#ifdef OA_DEBUG
269    debug_.printEndOfProcedureDebugMessage(cs, foundSolution, cutoff, milpBound, isInteger, feasible, std::cout);
270#endif
271    return milpBound;
272  }
273
274  /** Register OA options.*/
275  void
276  OACutGenerator2::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
277  {
278    roptions->SetRegisteringCategory("Options for OA decomposition", RegisteredOptions::BonminCategory);
279    roptions->AddLowerBoundedNumberOption("oa_dec_time_limit",
280        "Specify the maximum number of seconds spent overall in OA decomposition iterations.",
281        0.,0,30.,
282        "");
283
284    roptions->AddBoundedIntegerOption("oa_log_level",
285        "specify OA iterations log level.",
286        0,2,1,
287        "Set the level of output of OA decomposition solver : "
288        "0 - none, 1 - normal, 2 - verbose"
289                                     );
290
291    roptions->AddLowerBoundedNumberOption("oa_log_frequency",
292        "display an update on lower and upper bounds in OA every n seconds",
293        0.,1.,100.,
294        "");
295
296    roptions->SetRegisteringCategory("Options for MILP subsolver in OA decomposition", RegisteredOptions::BonminCategory);
297    roptions->AddStringOption3("milp_subsolver",
298        "Choose the subsolver to solve MILP sub-problems in OA decompositions.",
299        "Cbc_D",
300        "Cbc_D","Coin Branch and Cut with its default",
301        "Cbc_Par", "Coin Branch and Cut with passed parameters",
302        "Cplex","Ilog Cplex",
303        " To use Cplex, a valid license is required and you should have compiled OsiCpx in COIN-OR  (see Osi documentation).");
304    roptions->setOptionExtraInfo("milp_subsolver",5);
305
306    roptions->AddBoundedIntegerOption("milp_log_level",
307        "specify MILP subsolver log level.",
308        0,3,0,
309        "Set the level of output of the MILP subsolver in OA : "
310        "0 - none, 1 - minimal, 2 - normal low, 3 - normal high"
311                                     );
312    roptions->setOptionExtraInfo("milp_log_level",5);
313
314
315  }
316
317
318}/* End namespace Bonmin. */
Note: See TracBrowser for help on using the repository browser.