source: trunk/Bonmin/src/Algorithms/OaGenerators/BonOACutGenerator2.cpp @ 1511

Last change on this file since 1511 was 1511, checked in by pbonami, 11 years ago

Add some output

File size: 9.9 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
10#include "BonOACutGenerator2.hpp"
11#include "BonminConfig.h"
12
13#include "OsiClpSolverInterface.hpp"
14
15#include "CbcModel.hpp"
16#include "BonCbcLpStrategy.hpp"
17#ifdef COIN_HAS_CPX
18#include "OsiCpxSolverInterface.hpp"
19#endif
20#include "OsiAuxInfo.hpp"
21#include "BonSolverHelp.hpp"
22
23
24namespace Bonmin
25{
26   static const char * txt_id = "OA decomposition";
27
28
29/// Constructor with basic setup
30  OACutGenerator2::OACutGenerator2(BabSetupBase & b):
31      OaDecompositionBase(b, true, false)
32  {
33    int ivalue;
34    std::string bonmin="bonmin.";
35    std::string prefix = (b.prefix() == bonmin) ? "" : b.prefix();
36    prefix += "oa_decomposition.";
37    b.options()->GetEnumValue("milp_solver",ivalue,prefix);
38    if (ivalue <= 0) {//uses cbc
39      CbcStrategyDefault strategy;
40      setStrategy(strategy);
41    }
42    else if (ivalue == 1) {
43      CbcStrategyChooseCuts strategy(b, prefix);
44      setStrategy(strategy);
45    }
46    else if (ivalue == 2) {
47#ifdef COIN_HAS_CPX
48      OsiCpxSolverInterface * cpxSolver = new OsiCpxSolverInterface;
49      b.nonlinearSolver()->extractLinearRelaxation(*cpxSolver);
50      assignLpInterface(cpxSolver);
51#else
52      std::cerr << "You have set an option to use CPLEX as the milp\n"
53      << "subsolver in oa decomposition. However, apparently\n"
54      << "CPLEX is not configured to be used in bonmin.\n"
55      << "See the manual for configuring CPLEX\n";
56      throw -1;
57#endif
58    }
59
60    double oaTime;
61    b.options()->GetNumericValue("time_limit",oaTime,prefix);
62    parameter().maxLocalSearchTime_ =
63    std::min(b.getDoubleParameter(BabSetupBase::MaxTime), oaTime);
64    b.options()->GetIntegerValue("solution_limit", parameter().maxSols_,prefix);
65    parameter().localSearchNodeLimit_ = 1000000;
66    parameter().maxLocalSearch_ = 100000;
67    parameter().maxLocalSearchPerNode_ = 10000;
68  }
69  OACutGenerator2::~OACutGenerator2()
70  {}
71
72  /// virutal method to decide if local search is performed
73  bool
74  OACutGenerator2::doLocalSearch(BabInfo * babInfo) const
75  {
76    return (nLocalSearch_<parameters_.maxLocalSearch_ &&
77        parameters_.localSearchNodeLimit_ > 0 &&
78        CoinCpuTime() - timeBegin_ < parameters_.maxLocalSearchTime_ &&
79        numSols_ < parameters_.maxSols_);
80  }
81  /// virtual method which performs the OA algorithm by modifying lp and nlp.
82  double
83  OACutGenerator2::performOa(OsiCuts &cs,
84      solverManip &lpManip,
85      SubMipSolver * &subMip,
86      BabInfo * babInfo,
87      double & cutoff, const CglTreeInfo & info) const
88  {
89
90    bool interuptOnLimit = false;
91    double lastPeriodicLog = CoinCpuTime();
92
93    //const int numcols = nlp_->getNumCols();
94
95
96    bool isInteger = false;
97
98    OsiSolverInterface * lp = lpManip.si();
99    OsiBranchingInformation branch_info(lp, false);
100    bool milpOptimal = 1;
101
102
103    double milpBound = -COIN_DBL_MAX;
104    bool milpFeasible = 1;
105    bool feasible = 1;
106
107    if (subMip)//Perform a local search
108    {
109      subMip->find_good_sol(cutoff, parameters_.subMilpLogLevel_,
110          (parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime()) /* time limit */,
111          parameters_.localSearchNodeLimit_);
112      milpBound = subMip->lowBound();
113      milpOptimal = subMip->optimal();
114
115      feasible = milpBound < cutoff;
116      milpFeasible = feasible;
117      isInteger = (subMip->getLastSolution() != NULL);
118      nLocalSearch_++;
119
120      if (milpOptimal)
121        handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
122      else
123      {
124        handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
125      }
126    }
127    int numberPasses = 0;
128
129#ifdef OA_DEBUG
130    bool foundSolution = 0;
131#endif
132    double * nlpSol = NULL;
133
134    while (isInteger && feasible ) {
135      numberPasses++;
136      //after a prescribed elapsed time give some information to user
137      double time = CoinCpuTime();
138      if (time - lastPeriodicLog > parameters_.logFrequency_) {
139        double lb = (subMip == NULL) ?lp->getObjValue() : subMip->getLowerBound();
140        handler_->message(PERIODIC_MSG,messages_)
141        <<time - timeBegin_<<cutoff
142        <<lb
143        <<CoinMessageEol;
144        lastPeriodicLog = CoinCpuTime();
145      }
146
147
148      //setup the nlp
149      int numberCutsBefore = cs.sizeRowCuts();
150
151      //Fix the variable which have to be fixed, after having saved the bounds
152      const double * colsol = subMip == NULL ? lp->getColSolution():
153          subMip->getLastSolution();
154      branch_info.solution_ = colsol;
155
156      fixIntegers(*nlp_,branch_info, parameters_.cbcIntegerTolerance_,objects_, nObjects_);
157
158      nlp_->resolve(txt_id);
159      if (post_nlp_solve(babInfo, cutoff)) {
160        //nlp solved and feasible
161        // Update the cutoff
162        cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
163        // Update the lp solver cutoff
164        lp->setDblParam(OsiDualObjectiveLimit, cutoff);
165        numSols_++;
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      assert(numberCuts);
178      installCuts(*lp, cs, numberCuts);
179
180      lp->resolve();
181
182      double objvalue = lp->getObjValue();
183      //milpBound = max(milpBound, lp->getObjValue());
184      feasible = (lp->isProvenOptimal() &&
185          !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
186      //if value of integers are unchanged then we have to get out
187      bool changed = !feasible;//if lp is infeasible we don't have to check anything
188      branch_info.solution_ = lp->getColSolution();
189      if (!changed)
190        changed = isDifferentOnIntegers(*nlp_, objects_, nObjects_,
191                                        0.1,
192                                        nlp_->getColSolution(), lp->getColSolution());
193      if (changed) {
194
195        isInteger = integerFeasible(*lp, branch_info, parameters_.cbcIntegerTolerance_,
196                                     objects_, nObjects_);
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 (feasible && !isInteger &&
212          nLocalSearch_ < parameters_.maxLocalSearch_ &&
213          numberPasses < parameters_.maxLocalSearchPerNode_ &&
214          parameters_.localSearchNodeLimit_ > 0 && numSols_ < parameters_.maxSols_) {
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->find_good_sol(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 = isDifferentOnIntegers(*nlp_, objects_, nObjects_,
241                                          0.1,
242                                          nlp_->getColSolution(), colsol);
243          //solution problem is solved
244          if (!changed) {
245            feasible = 0;
246            milpBound = 1e50;
247          }
248          milpFeasible = feasible;
249        }
250        if (subMip->optimal())
251          milpOptimal = 1;
252        else {
253          milpOptimal = 0;
254        }
255
256        if (milpBound < cutoff)
257          handler_->message(UPDATE_LB, messages_)<<milpBound<<CoinCpuTime() - timeBegin_<<CoinMessageEol;
258        else {
259          milpBound = 1e50;
260          feasible = 0;
261          handler_->message(OASUCCESS, messages_)<<CoinCpuTime() - timeBegin_ <<CoinMessageEol;
262        }
263      }/** endif localSearch*/
264      else if (subMip!=NULL) {
265        delete subMip;
266        subMip = NULL;
267      }
268    }
269
270#ifdef OA_DEBUG
271    debug_.printEndOfProcedureDebugMessage(cs, foundSolution, cutoff, milpBound, isInteger, feasible, std::cout);
272#endif
273    return milpBound;
274  }
275
276  /** Register OA options.*/
277  void
278  OACutGenerator2::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
279  {
280    roptions->SetRegisteringCategory("Options for OA decomposition", RegisteredOptions::BonminCategory);
281    roptions->AddStringOption2("oa_decomposition", "If yes do initial OA decomposition",
282                               "no",
283                               "no","",
284                               "yes","",
285                               "");
286    roptions->AddBoundedIntegerOption("oa_log_level",
287        "specify OA iterations log level.",
288        0,2,1,
289        "Set the level of output of OA decomposition solver : "
290        "0 - none, 1 - normal, 2 - verbose"
291                                     );
292    roptions->setOptionExtraInfo("oa_decomposition", 7);
293
294    roptions->AddLowerBoundedNumberOption("oa_log_frequency",
295        "display an update on lower and upper bounds in OA every n seconds",
296        0.,1.,100.,
297        "");
298    roptions->setOptionExtraInfo("oa_log_frequency", 15);
299  }
300}/* End namespace Bonmin. */
301
Note: See TracBrowser for help on using the repository browser.