source: trunk/Couenne/src/heuristics/CouenneFeasPump.hpp @ 577

Last change on this file since 577 was 577, checked in by pbelotti, 9 years ago

restoring FP for tests. Changing branching point on integer variables with integer value. Fixing large branching points for variables with large (upper/lower) bounds and large LP values. Added debug code to twoImplBounds for check against optimal solutions. Added fictitious objective function of 0 when none is defined. Redeclared size_t in invmap.cpp for compatibility with MSVS.

  • Property svn:keywords set to Author Date Id Revision
File size: 5.2 KB
Line 
1/* $Id: CouenneFeasPump.hpp 577 2011-05-21 20:38:48Z pbelotti $
2 *
3 * Name:    CouenneFeasPump.hpp
4 * Authors: Pietro Belotti, Lehigh University
5 *          Timo Berthold, ZIB Berlin
6 * Purpose: Define the Feasibility Pump heuristic class
7 * Created: August 5, 2009
8 *
9 * This file is licensed under the Eclipse Public License (EPL)
10 */
11
12#ifndef CouenneFeasPump_HPP
13#define CouenneFeasPump_HPP
14
15#include <queue>
16
17#include "CouenneTypes.hpp"
18#include "CbcHeuristic.hpp"
19#include "IpOptionsList.hpp"
20
21namespace Osi {
22  class OsiSolverInterface;
23}
24
25namespace Ipopt {
26  class IpoptApplication;
27}
28
29namespace Bonmin {
30  class RegisteredOptions;
31}
32
33namespace Couenne {
34
35  class expression;
36  class CouenneProblem;
37  class CouenneCutGenerator;
38  class CouenneTNLP;
39
40  /// An implementation of the Feasibility pump that uses
41  /// linearization and Ipopt to find the two sequences of points.
42 
43  class CouenneFeasPump: public CbcHeuristic {
44
45  public:
46
47    // Default constructor
48    CouenneFeasPump ();
49
50    /// Constructor with model and Ipopt problems
51    CouenneFeasPump (CouenneProblem *couenne,
52                     CouenneCutGenerator *cg,
53                     Ipopt::SmartPtr<Ipopt::OptionsList> options);
54
55    /// Copy constructor
56    CouenneFeasPump (const CouenneFeasPump &other);
57   
58    /// Destructor
59    virtual ~CouenneFeasPump();
60
61    /// Clone
62    virtual CbcHeuristic *clone () const;
63   
64    /// Assignment operator
65    CouenneFeasPump &operator= (const CouenneFeasPump &rhs);
66
67    /// Does nothing, but necessary as CbcHeuristic declares it pure virtual
68    virtual void resetModel (CbcModel *model) {}
69
70    /// Run heuristic, return 1 if a better solution than the one
71    /// passed is found and 0 otherwise.
72    ///
73    /// \argument objectiveValue Best known solution in input and
74    /// value of solution found in output
75    ///
76    /// \argument newSolution Solution found by heuristic.
77    virtual int solution (double &objectiveValue, double *newSolution);
78
79    /// set number of nlp's solved for each given level of the tree
80    void setNumberSolvePerLevel (int value)
81    {numberSolvePerLevel_ = value;}
82
83    /// find integer (possibly NLP-infeasible) point isol closest
84    /// (according to the l-1 norm of the hessian) to the current
85    /// NLP-feasible (but fractional) solution nsol
86    CouNumber solveMILP (CouNumber *nSol, CouNumber *&iSol); 
87
88    /// obtain solution to NLP
89    CouNumber solveNLP  (CouNumber *nSol, CouNumber *&iSol);
90
91    /// set new expression as the NLP objective function using
92    /// argument as point to minimize distance from. Return new
93    /// objective function
94    expression *updateNLPObj (const double *);
95
96    /// admits a (possibly fractional) solution and fixes the integer
97    /// components in the nonlinear problem for later re-solve
98    void fixIntVariables (double *sol);
99
100    /// initialize options to be read later
101    static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions>);
102
103    /// find feasible solution (called by solveMILP ())
104    void findSolution ();
105
106    /// initialize all solvers at the first call, where the initial
107    /// MILP is built
108    void init_MILP ();
109
110  private:
111
112    //
113    // Essential tools for the FP: a problem pointer and one for the
114    // linearization cut generator
115    //
116
117    /// Couenne representation of the problem.
118    CouenneProblem *problem_;
119
120    /// CouenneCutGenerator for linearization cuts
121    CouenneCutGenerator *couenneCG_;
122
123    //
124    // PERSISTENT OBJECTS -- not necessary to identify FP, but it's
125    // useful to keep them between calls
126    //
127
128    /// Continuous relaxation of the problem, with an interface for
129    /// Ipopt only
130    CouenneTNLP *nlp_;
131
132    /// MILP relaxation of the MINLP (used to find integer
133    /// non-NLP-feasible solution)
134    OsiSolverInterface *milp_;
135
136    /// Ipopt solver
137    Ipopt::IpoptApplication *nlpSolver_;
138
139    /// Pool of solutions
140    std::priority_queue <std::pair <CouNumber *, CouNumber> > pool_;
141
142    /// These methods can be used to solve the MILP, from the most
143    /// expensive, exact method to a cheap, inexact one:
144    ///
145    /// 1. Solve a MILP relaxation with Manhattan distance as objective
146    /// 2. Apply RENS on 1
147    /// 3. Use Objective FP 2.0 for MILPs
148    /// 4. round-and-propagate
149    /// 5. choose from pool, see 4
150    /// 6. random pertubation
151
152    enum Methods {SOLVE_MILP,       APPLY_RENS,  USE_FP_2, ROUND_N_PROPAGATE, 
153                  CHOOSE_FROM_POOL, RND_PERTURB, NUM_METHODS};
154
155    /// array of NUM_METHODS elements containing a number indicating
156    /// the recent successes of the corresponding algorithm (see enum
157    /// right above). The larger method_success_ [i], the more often
158    /// the i-th method should be used.
159
160    int *method_success_;
161
162    //
163    // PARAMETERS
164    //
165
166    /// Number of nlp's solved for each given level of the tree
167    int numberSolvePerLevel_;
168
169    /// weight of the Hessian in computing the objective functions of NLP
170    double betaNLP_;
171
172    /// weight of the Hessian in computing the objective functions of MILP
173    double betaMILP_; // decrease it over time
174
175    /// compute distance from integer variables only, not all variables;
176    bool compDistInt_;
177
178    /// Skip NLP solver if found integer but MINLP-infeasible solution
179    bool milpCuttingPlane_;
180
181    /// maximum iterations per call
182    int maxIter_;
183
184  };
185}
186
187#endif
Note: See TracBrowser for help on using the repository browser.