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

Last change on this file since 936 was 936, checked in by pbelotti, 8 years ago

added option to fill matrices for SDP cuts. removed delete_ field from CouenneScalar?

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