source: stable/0.100/Bonmin/src/Algorithms/OaGenerators/BonOaDecBase.hpp @ 1355

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

Switch default strategy to probed-diving with best-bound

File size: 10.8 KB
Line 
1// (C) Copyright International Business Machines (IBM) 2006
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// Authors :
6// P. Bonami, International Business Machines
7//
8// Date :  12/07/2006
9
10#ifndef BonOaDecBase_HPP
11#define BonOaDecBase_HPP
12#include "CglCutGenerator.hpp"
13#include "BonBabSetupBase.hpp"
14#include "BonOAMessages.hpp"
15#include "CbcModel.hpp"
16
17#include "CbcStrategy.hpp"
18
19#include "CoinTime.hpp"
20#include "OsiAuxInfo.hpp"
21#include "OsiBranchingObject.hpp"
22
23
24/* forward declarations.*/
25class OsiClpSolverInterface;
26class OsiCpxSolverInterface;
27
28namespace Bonmin
29{
30  /** Base class for OA algorithms.*/
31  class OaDecompositionBase : public CglCutGenerator
32  {
33  public:
34    /** Small class to perform the solution of sub-mips.*/
35    class SubMipSolver
36    {
37    public:
38      /** Constructor */
39      SubMipSolver(OsiSolverInterface * lp = NULL,
40          const CbcStrategy * strategy = NULL);
41
42      ~SubMipSolver();
43
44      /** Assign lp solver. */
45      void setLpSolver(OsiSolverInterface * lp);
46
47      /** Assign a strategy. */
48      void setStrategy(CbcStrategy * strategy)
49      {
50        if (strategy_) delete strategy_;
51        strategy_ = strategy->clone();
52      }
53      /** get the solution found in last local search (return NULL if no solution). */
54      const double * getLastSolution()
55      {
56        return integerSolution_;
57      }
58
59      double getLowerBound()
60      {
61        return lowBound_;
62      }
63      /** update cutoff and perform a new local search. */
64      void performLocalSearch(double cutoff,
65          int loglevel,
66          double maxTime,
67          int maxNodes);
68
69      /** Returns lower bound. */
70      inline double lowBound()
71      {
72        return lowBound_;
73      }
74
75      /** returns optimality status. */
76      inline bool optimal()
77      {
78        return optimal_;
79      }
80
81      /** Returns number of nodes in last solve.*/
82      inline int nodeCount()
83      {
84        return nodeCount_;
85      }
86
87      /** Returns number of simplex iterations in last solve.*/
88      inline int iterationCount()
89      {
90        return iterationCount_;
91      }
92
93
94      /** Register options for that Oa based cut generation method. */
95      void registerOptions(Ipopt::SmartPtr<Ipopt::RegisteredOptions> roptions)
96      {}
97    private:
98      /** lp (potentially mip solver). */
99      OsiSolverInterface * lp_;
100      /** If lp solver is clp (then have to use Cbc).*/
101      OsiClpSolverInterface *clp_;
102      /** If lp solver is cpx this points to it. */
103      OsiCpxSolverInterface * cpx_;
104      /** If cbc is used pointer to CbcModel. */
105      CbcModel * cbc_;
106      /** lower bound obtained */
107      double lowBound_;
108      /** Is optimality proven? */
109      bool optimal_;
110      /** Has an integer solution? then it is here*/
111      double * integerSolution_;
112      /** Strategy for solving sub mips with cbc. */
113      CbcStrategy * strategy_;
114      /** number of nodes in last mip solved.*/
115      int nodeCount_;
116      /** number of simplex iteration in last mip solved.*/
117      int iterationCount_;
118    };
119
120    /** Small class to manipulatee various things in an OsiSolverInterface and restore them.
121        The OsiSolverInterface manipulated may already exist or may be cloned from another one.*/
122    class solverManip
123    {
124    public:
125      /** Constructor. */
126      solverManip(OsiSolverInterface *si , bool saveNumRows=true,
127          bool saveBasis=true, bool saveBounds=false,
128          bool saveCutoff = false, bool resolve=true);
129
130      /** Constructor which clone an other interface. */
131      solverManip(const OsiSolverInterface & si);
132      /** Destructor. */
133      ~solverManip();
134      /** Restore solver. */
135      void restore();
136
137      /** Clone the state of another solver (bounds, cutoff, basis).*/
138      void cloneOther(const OsiSolverInterface &si);
139      /** Check for integer feasibility of a solution return true if it is feasible.
140      \todo Handle SOS Type 2 constraints. */
141      bool integerFeasible(const OsiBranchingInformation & info) const;
142
143      /** Fix integer variables in si to their values in colsol.
144          \remark colsol is assumed to be integer on the integer constrained variables.
145          \todo Handle SOS type 2.*/
146      void fixIntegers(const OsiBranchingInformation & info);
147
148      /** Check if solution in solver is the same as colsol on integer variables. */
149      bool isDifferentOnIntegers(const double * colsol);
150
151      /** Check if two solutions are the same on integer variables. */
152      bool isDifferentOnIntegers(const double * colsol, const double * other);
153
154      /** Install cuts in solver. */
155      void installCuts(const OsiCuts& cs, int numberCuts);
156
157      /** Get pointer to solver interface. */
158      OsiSolverInterface * si()
159      {
160        return si_;
161      }
162
163      /** Set objects.*/
164      void setObjects(OsiObject ** objects, int nObjects)
165      {
166        objects_ = objects;
167        nObjects_ = nObjects;
168      }
169
170      void setIntegerTolerance(double v)
171      {
172        integerTolerance_ = v;
173      }
174    private:
175      /** Interface saved. */
176      OsiSolverInterface * si_;
177      /** Initial number of rows (-1 if don't save). */
178      int initialNumberRows_;
179
180      /** Initial lower bounds. */
181      double * colLower_;
182
183      /** Initial Upper bounds.*/
184      double * colUpper_;
185
186      /** Inital basis. */
187      CoinWarmStart * warm_;
188
189      /** Initial cutoff. */
190      double cutoff_;
191
192      /** delete si_ ? */
193      bool deleteSolver_;
194
195      /// Some objects the feasiblitiy of which to verify.
196      OsiObject * * objects_;
197      /// Number of objects.*/
198      int nObjects_;
199      /** \name Cached info from solver interface.*/
200      /** @{ */
201      /** Number of columns. */
202      int numcols_;
203      /** Number of rows. */
204      int numrows_;
205      /** Lower bounds on variables.*/
206      const double * siColLower_;
207      /** Upper bounds on variables. */
208      const double * siColUpper_;
209
210      void getCached();
211      /** @} */
212      double integerTolerance_;
213    };
214    /// Old usefull constructor
215    OaDecompositionBase(OsiTMINLPInterface * nlp = NULL,
216        OsiSolverInterface * si = NULL,
217        CbcStrategy * strategy = NULL,
218        double cbcCutoffIncrement_=1e-07,
219        double cbcIntegerTolerance = 1e-05,
220        bool leaveSiUnchanged = 0
221                       );
222    /// New usefull constructor
223    OaDecompositionBase(BabSetupBase &b, bool leaveSiUnchanged,
224        bool reassignLpsolver);
225
226    /// Copy constructor
227    OaDecompositionBase(const OaDecompositionBase & copy);
228
229
230    /// Destructor
231    virtual ~OaDecompositionBase();
232
233    /** Standard cut generation methods. */
234    virtual void generateCuts(const OsiSolverInterface &si,  OsiCuts & cs,
235        const CglTreeInfo info = CglTreeInfo()) const;
236
237    /// Assign an OsiTMINLPInterface
238    void assignNlpInterface(OsiTMINLPInterface * nlp)
239    {
240      nlp_ = nlp;
241    }
242
243    /// Assign an OsiTMINLPInterface
244    void assignLpInterface(OsiSolverInterface * si)
245    {
246      lp_ = si;
247    }
248
249    bool reassignLpsolver()
250    {
251      return reassignLpsolver_;
252    }
253    /** Set objects.*/
254    void setObjects(OsiObject ** objects, int nObjects)
255    {
256      objects_ = objects;
257      nObjects_ = nObjects;
258    }
259    /// Set whether to leave the solverinterface unchanged
260    inline void setLeaveSiUnchanged(bool yesno)
261    {
262      leaveSiUnchanged_ = yesno;
263    }
264
265    /** Parameters for algorithm. */
266    struct Parameters
267    {
268      /// Add cuts as global
269      bool global_;
270      /// Add only violated OA inequalities
271      bool addOnlyViolated_;
272      /// cutoff min increase (has to be intialized trhough Cbc)
273      double cbcCutoffIncrement_;
274      /// integer tolerance (has to be the same as Cbc's)
275      double cbcIntegerTolerance_;
276      ///Max number of nodes for local search
277      int localSearchNodeLimit_;
278      ///Max number of local searches per node
279      int maxLocalSearchPerNode_;
280      ///Total max number of local searches
281      int maxLocalSearch_;
282      /// maximum time for local searches
283      double maxLocalSearchTime_;
284      /** sub milp log level.*/
285      int subMilpLogLevel_;
286      /** Frequency of log. */
287      double logFrequency_;
288
289      /** Constructor with default values */
290      Parameters();
291
292      /** Copy constructor */
293      Parameters(const Parameters & other);
294
295      /** Destructor */
296      ~Parameters()
297      {
298        if (!strategy_) delete strategy_;
299      }
300
301      /** Strategy to apply when using Cbc as MILP sub-solver.*/
302      void setStrategy(const CbcStrategy & strategy)
303      {
304        if (strategy_) delete strategy_;
305        strategy_ = strategy.clone();
306      }
307
308      const CbcStrategy * strategy() const
309      {
310        return strategy_;
311      }
312private:
313      /** Strategy to apply when using Cbc as MILP sub-solver.*/
314      CbcStrategy * strategy_;
315
316    };
317
318    Parameters& parameter()
319    {
320      return parameters_;
321    }
322
323    const Parameters& parameter()const
324    {
325      return parameters_;
326    }
327
328    void setLogLevel(int level)
329    {
330      handler_->setLogLevel(level);
331    }
332
333    void passInMessageHandler(CoinMessageHandler * handler);
334  protected:
335    /// \name Protected helper functions
336    /**@{ */
337
338    /** Solve the nlp and do output.
339        \return true if feasible*/
340    bool solveNlp(OsiBabSolver * babInfo, double cutoff) const;
341    /** @} */
342
343    /// virtual method which performs the OA algorithm by modifying lp and nlp.
344    virtual double performOa(OsiCuts &cs, solverManip &nlpManip, solverManip &lpManip,
345        SubMipSolver * &subMip, OsiBabSolver * babInfo, double &) const = 0;
346    /// virutal method to decide if local search is performed
347    virtual bool doLocalSearch() const = 0;
348
349    /// \name Protected members
350    /** @{ */
351    /// Pointer to nlp interface
352    mutable OsiTMINLPInterface * nlp_;
353    ///Number of nlp solved done
354    mutable int nSolve_;
355    /// A linear solver
356    mutable OsiSolverInterface * lp_;
357    /// Some objects the feasiblitiy of which to verify.
358    OsiObject * * objects_;
359    /// Number of objects.*/
360    int nObjects_;
361    ///number of local searches performed
362    mutable int nLocalSearch_;
363    /** messages handler. */
364    CoinMessageHandler * handler_;
365    /** Messages for OA */
366    CoinMessages messages_;
367    /** Wether or not we should remove cuts at the end of the procedure */
368    bool leaveSiUnchanged_;
369    /** Do we need to reassign the lp solver with Cbc.*/
370    bool reassignLpsolver_;
371    /** time of construction*/
372    double timeBegin_;
373
374    /** Parameters.*/
375    Parameters parameters_;
376
377    /** @} */
378
379#ifdef OA_DEBUG
380    class OaDebug
381    {
382      public:
383      bool checkInteger(const OsiSolverInterface&nlp, std::ostream & os) const;
384
385      void printEndOfProcedureDebugMessage(const OsiCuts &cs,
386          bool foundSolution,
387          double solValue,
388          double milpBound,
389          bool isInteger,
390          bool feasible,
391          std::ostream & os) const;
392    };
393
394    /** debug object. */
395    OaDebug debug_;
396
397#endif
398  };
399}
400#endif
401
Note: See TracBrowser for help on using the repository browser.