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

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

Remove some unused option in OA add Claudi d'Ambrosio code

File size: 10.2 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().maxLocalSearch_ = INT_MAX;
72    parameter().maxLocalSearchTime_ =
73      Ipopt::Min(b.getDoubleParameter(BabSetupBase::MaxTime), oaTime);
74  }
75  OACutGenerator2::~OACutGenerator2()
76  {}
77
78  /// virutal method to decide if local search is performed
79  bool
80  OACutGenerator2::doLocalSearch() const
81  {
82    return (nLocalSearch_<parameters_.maxLocalSearch_ &&
83        CoinCpuTime() - timeBegin_ < parameters_.maxLocalSearchTime_);
84  }
85  /// virtual method which performs the OA algorithm by modifying lp and nlp.
86  double
87  OACutGenerator2::performOa(OsiCuts &cs,
88      solverManip &nlpManip,
89      solverManip &lpManip,
90      SubMipSolver * &subMip,
91      OsiBabSolver * babInfo,
92      double & cutoff) const
93  {
94    double lastPeriodicLog= CoinCpuTime();
95
96    //const int numcols = nlp_->getNumCols();
97
98
99    bool isInteger = false;
100
101    OsiSolverInterface * lp = lpManip.si();
102    OsiBranchingInformation info(lp, false);
103    bool milpOptimal = 1;
104
105
106    double milpBound = -COIN_DBL_MAX;
107    bool milpFeasible = 1;
108    bool feasible = 1;
109    if (subMip)//Perform a local search
110    {
111      subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
112          (parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime()) /* time limit */);
113      milpBound = subMip->lowBound();
114      milpOptimal = subMip->optimal();
115
116      feasible = milpBound < cutoff;
117      milpFeasible = feasible;
118      isInteger = subMip->getLastSolution() != NULL;
119      nLocalSearch_++;
120
121      if (milpOptimal)
122        handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
123      else
124      {
125        handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
126      }
127    }
128    int numberPasses = 0;
129
130#ifdef OA_DEBUG
131    bool foundSolution = 0;
132#endif
133    double * nlpSol = NULL;
134
135    while (isInteger && feasible ) {
136      numberPasses++;
137
138      //after a prescribed elapsed time give some information to user
139      double time = CoinCpuTime();
140      if (time - lastPeriodicLog > parameters_.logFrequency_) {
141        double lb = (subMip == NULL) ?lp->getObjValue() : subMip->getLowerBound();
142        handler_->message(PERIODIC_MSG,messages_)
143        <<time - timeBegin_<<cutoff
144        <<lb
145        <<CoinMessageEol;
146        lastPeriodicLog = CoinCpuTime();
147      }
148
149
150      //setup the nlp
151      int numberCutsBefore = cs.sizeRowCuts();
152
153      //Fix the variable which have to be fixed, after having saved the bounds
154      const double * colsol = subMip == NULL ? lp->getColSolution():
155          subMip->getLastSolution();
156      info.solution_ = colsol;
157      nlpManip.fixIntegers(info);
158
159
160      if (solveNlp(babInfo, cutoff)) {
161        //nlp solved and feasible
162        // Update the cutoff
163        cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
164        // Update the lp solver cutoff
165        lp->setDblParam(OsiDualObjectiveLimit, cutoff);
166      }
167
168      nlpSol = const_cast<double *>(nlp_->getColSolution());
169
170      // Get the cuts outer approximation at the current point
171      const double * toCut = (parameter().addOnlyViolated_)?
172          colsol:NULL;
173      nlp_->getOuterApproximation(cs, nlpSol, 1, toCut,
174                                  parameter().global_);
175
176      int numberCuts = cs.sizeRowCuts() - numberCutsBefore;
177      if (numberCuts > 0)
178        lpManip.installCuts(cs, numberCuts);
179
180      lp->resolve();
181      double objvalue = lp->getObjValue();
182      //milpBound = max(milpBound, lp->getObjValue());
183      feasible = (lp->isProvenOptimal() &&
184          !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
185      //if value of integers are unchanged then we have to get out
186      bool changed = !feasible;//if lp is infeasible we don't have to check anything
187      info.solution_ = lp->getColSolution();
188      if (!changed)
189        changed = nlpManip.isDifferentOnIntegers(lp->getColSolution());
190      if (changed) {
191
192        isInteger = lpManip.integerFeasible(info);
193      }
194      else {
195        isInteger = 0;
196        //        if(!fixed)//fathom on bounds
197        milpBound = 1e200;
198      }
199#ifdef OA_DEBUG
200      printf("Obj value after cuts %g %d rows\n",lp->getObjValue(),
201          numberCuts) ;
202#endif
203      //check time
204      if (CoinCpuTime() - timeBegin_ > parameters_.maxLocalSearchTime_)
205        break;
206      //do we perform a new local search ?
207      if (milpOptimal && feasible && !isInteger &&
208          nLocalSearch_ < parameters_.maxLocalSearch_) {
209
210        /** do we have a subMip? if not create a new one. */
211        if (subMip == NULL) subMip = new SubMipSolver(lp, parameters_.strategy());
212
213        nLocalSearch_++;
214
215        subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
216            parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime());
217
218        milpBound = subMip->lowBound();
219
220        if (subMip->optimal())
221          handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
222        else
223          handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
224
225
226        colsol = const_cast<double *> (subMip->getLastSolution());
227        isInteger = colsol != 0;
228
229        feasible =  (milpBound < cutoff);
230
231        if (feasible && isInteger) {
232          bool changed = false;
233          changed = nlpManip.isDifferentOnIntegers(colsol);//If integer solution is the same as nlp
234          //solution problem is solved
235          if (!changed) {
236            feasible = 0;
237            milpBound = 1e50;
238          }
239          milpFeasible = feasible;
240        }
241        if (subMip->optimal())
242          milpOptimal = 1;
243        else {
244          milpOptimal = 0;
245        }
246
247        if (milpBound < cutoff)
248          handler_->message(UPDATE_LB, messages_)<<milpBound<<CoinCpuTime() - timeBegin_<<CoinMessageEol;
249        else {
250          milpBound = 1e50;
251          feasible = 0;
252          handler_->message(OASUCCESS, messages_)<<CoinCpuTime() - timeBegin_ <<CoinMessageEol;
253        }
254      }/** endif localSearch*/
255      else if (subMip!=NULL) {
256        delete subMip;
257        subMip = NULL;
258      }
259    }
260
261#ifdef OA_DEBUG
262    debug_.printEndOfProcedureDebugMessage(cs, foundSolution, cutoff, milpBound, isInteger, feasible, std::cout);
263#endif
264    return milpBound;
265  }
266
267  /** Register OA options.*/
268  void
269  OACutGenerator2::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
270  {
271    roptions->SetRegisteringCategory("Options for OA decomposition", RegisteredOptions::BonminCategory);
272    roptions->AddLowerBoundedNumberOption("oa_dec_time_limit",
273        "Specify the maximum number of seconds spent overall in OA decomposition iterations.",
274        0.,0,30.,
275        "");
276
277    roptions->AddBoundedIntegerOption("oa_log_level",
278        "specify OA iterations log level.",
279        0,2,1,
280        "Set the level of output of OA decomposition solver : "
281        "0 - none, 1 - normal, 2 - verbose"
282                                     );
283
284    roptions->AddLowerBoundedNumberOption("oa_log_frequency",
285        "display an update on lower and upper bounds in OA every n seconds",
286        0.,1.,100.,
287        "");
288
289    roptions->SetRegisteringCategory("Options for MILP subsolver in OA decomposition", RegisteredOptions::BonminCategory);
290    roptions->AddStringOption3("milp_subsolver",
291        "Choose the subsolver to solve MILP sub-problems in OA decompositions.",
292        "Cbc_D",
293        "Cbc_D","Coin Branch and Cut with its default",
294        "Cbc_Par", "Coin Branch and Cut with passed parameters",
295        "Cplex","Ilog Cplex",
296        " To use Cplex, a valid license is required and you should have compiled OsiCpx in COIN-OR  (see Osi documentation).");
297    roptions->setOptionExtraInfo("milp_subsolver",5);
298
299    roptions->AddBoundedIntegerOption("milp_log_level",
300        "specify MILP subsolver log level.",
301        0,3,0,
302        "Set the level of output of the MILP subsolver in OA : "
303        "0 - none, 1 - minimal, 2 - normal low, 3 - normal high"
304                                     );
305    roptions->setOptionExtraInfo("milp_log_level",5);
306
307
308  }
309
310
311}/* End namespace Bonmin. */
Note: See TracBrowser for help on using the repository browser.