source: trunk/Couenne/src/cut/sdpcuts/CouenneSdpCuts.hpp @ 945

Last change on this file since 945 was 945, checked in by stefan, 8 years ago

generateCuts in Cgl >= 0.58 will not be const anymore

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 5.5 KB
Line 
1/* $Id: CouenneSdpCuts.hpp 945 2013-04-06 20:25:21Z stefan $
2 *
3 * Name:    CouenneSdpCuts.hpp
4 * Authors: Pietro Belotti
5 *          Andrea Qualizza
6 * Purpose: wrapper for Couenne to insert sdpcuts
7 *
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11#ifndef CouenneSdpCuts_hpp
12#define CouenneSdpCuts_hpp
13
14#include "CglConfig.h"
15#include "CglCutGenerator.hpp"
16#include "BonRegisteredOptions.hpp"
17#include "IpOptionsList.hpp"
18#include "CouenneJournalist.hpp"
19
20namespace Couenne {
21
22  class CouenneProblem;
23  class CouenneExprMatrix;
24
25  ///
26  /// These are cuts of the form
27  ///
28  /// a' X a >= 0
29  ///
30  /// where X is a matrix constrained to be PSD.
31  ///
32  /// Typical application is in problems with products forming a
33  /// matrix of auxiliary variables X0 = (x_ij)_{i,j in N}, and x_ij
34  /// is the auxiliary variable for x_i * x_j. After reformulation,
35  /// matrices like X0 arise naturally and can be used to separate
36  /// cuts that help strengthen the lower bound. See Sherali and
37  /// Fraticelli for the base idea, and Qualizza, Belotti and Margot
38  /// for an efficient rework and its implementation. Andrea
39  /// Qualizza's code has been made open source and is used here
40  /// (thanks Andrea!).
41  ///
42
43  class CouenneSdpCuts: public CglCutGenerator {
44
45  protected:
46
47    CouenneProblem *problem_; ///< pointer to problem info
48
49    bool doNotUse_; ///< after construction, true if there are enough
50                    ///< product terms to justify application. If not,
51                    ///< do not add this cut generator
52
53    std::vector <CouenneExprMatrix *> minors_; ///< minors on which to apply cuts
54
55    int numEigVec_; ///< number of eigenvectors to be used (default: n)
56
57    bool onlyNegEV_; ///< only use negative eigenvalues (default: yes)
58
59    bool useSparsity_; ///< Sparsify eigenvalues before writing inequality (default: no)
60
61    bool fillMissingTerms_; ///< If minor not fully dense, create
62                            ///< fictitious auxiliary variables that
63                            ///< will be used in sdp cuts only (tighter
64                            ///< than sdp cuts without)
65
66  public:
67
68    CouenneSdpCuts  (CouenneProblem *, JnlstPtr,
69                     const Ipopt::SmartPtr <Ipopt::OptionsList>); ///< Constructor
70
71    ~CouenneSdpCuts ();                                           ///< Destructor
72    CouenneSdpCuts  &operator= (const CouenneSdpCuts &);          ///< Assignment
73    CouenneSdpCuts             (const CouenneSdpCuts &);          ///< Copy constructor
74    virtual CglCutGenerator *clone () const;                      ///< Cloning constructor
75
76    const bool doNotUse () const {return doNotUse_;}
77
78    /// The main CglCutGenerator
79    virtual void generateCuts (const OsiSolverInterface &, 
80                               OsiCuts &, 
81                               const CglTreeInfo = CglTreeInfo ())
82#if CGL_VERSION_MAJOR == 0 && CGL_VERSION_MINOR <= 57
83    const
84#endif
85    ;
86
87    /// Add list of options to be read from file
88    static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
89
90    // -----------------------------------------------------------------------------------------------------
91
92    void updateSol();
93
94  private:
95
96    void genCutSingle (CouenneExprMatrix * const &,
97                       const OsiSolverInterface &, OsiCuts &, 
98                       const CglTreeInfo = CglTreeInfo ()) const;
99
100    void compareSparsify (const OsiSolverInterface &si,
101                          int n, int m, const double *sol, 
102                          double *z, double *w,FILE *out) const;
103
104
105    void sparsify2 (const int n,
106                    const double *A, double **sparse_v_mat,
107                    int *card_v_mat, int min_nz, int *evdec_num) const;
108
109    void genSDPcut (const OsiSolverInterface &si,
110                    OsiCuts &cs, 
111                    CouenneExprMatrix *XX,
112                    double *v1, double *v2, 
113                    int **) const; // contains indices
114
115    void additionalSDPcuts (const OsiSolverInterface &si,
116                            OsiCuts &cs, 
117                            CouenneExprMatrix *minor, 
118                            int np, const double *A, 
119                            const double *vector, int **) const; // indices of matrix X'
120
121    enum zero_type {POS_DELTA, SELECTED, VALID_DELTA};
122
123    void zero_comp (const int ind_i, const double delta,
124                    const int np, const int *selected,
125                    int *loc_selected, 
126                    int *ploc_card_selected, int *ploc_card_new_selected, 
127                    double *ploc_lhs, 
128                    double *locmargin, double *locmat, 
129                    double *locv, 
130                    const int evidx, bool wise, 
131                    int *evdec_num, 
132                    double *recomp_gap, 
133                    double *threshold) const;
134
135    void zero_unified (enum zero_type type,
136                       const int np, const int *order,
137                       const int * selected,
138                       const int min_card_new_selected,
139                       const double min_delta, const int start_point, 
140                       const int curr_i, 
141                       int *loc_selected, 
142                       int *ploc_card_selected, 
143                       int *ploc_card_new_selected, 
144                       double *ploc_lhs, 
145                       double *locmargin, double *locmat, 
146                       int *pnchanged,
147                       double *locv, 
148                       const int evidx, bool wise,double *recomp_gap, double *threshold,
149                       int *evdec_num) const;
150
151    void add_v_cut(const int np,
152                   const int *loc_selected, 
153                   const int loc_card_selected,
154                   const double *locv,
155                   const int init_card_selected, int *has_init_vect,
156                   int *selected, int *pcard_selected,
157                   int *pnew_selected,
158                   double **sparse_v_mat,
159                   int *pcard_v_mat) const;
160
161    void update_sparsify_structures(const int np, 
162                                    double *v, double* margin, 
163                                    double *A, double *lhs, const int *zeroed, 
164                                    int evidx, bool decompose, int *evdec_num) const;
165
166    void sparsify (bool sparsify_new,
167                   const int evidx, const double eigen_val, 
168                   const double *v, const int n, 
169                   const double *sol, double **sparse_v_mat,
170                   int *card_v_mat,
171                   int *evdec_num) const;
172  };
173}
174
175#endif
Note: See TracBrowser for help on using the repository browser.