# source:trunk/Cbc/src/CbcClique.hpp@1422

Last change on this file since 1422 was 1389, checked in by caphillSNL, 11 years ago

Start at adding documentation, removing magic numbers, removing dead code, etc.
Added an enum for type in classes derived from CbCBranchingObject. It's safer,
handier for debugging (inspection in a debugger), and clearly shows the relationship
between the dozen or so special numbers. Numbers are the same as they were before to
ensure no changes in correctness.

File size: 10.0 KB
Line
1// Edwin 11/9/2009-- carved out of CbcBranchActual
2#ifndef CbcClique_H
3#define CbcClique_H
4
5/** \brief Branching object for cliques
6
7  A clique is defined to be a set of binary variables where fixing any one
8  variable to its `strong' value fixes all other variables. An example is the
9  most common SOS1 construction: a set of binary variables x<j> s.t.  SUM{j}
10  x<j> = 1.  Setting any one variable to 1 forces all other variables to 0.
11  (See comments for CbcSOS below.)
12
13  Other configurations are possible, however: Consider x1-x2+x3 <= 0.
14  Setting x1 (x3) to 1 forces x2 to 1 and x3 (x1) to 0. Setting x2 to 0
15  forces x1 and x3 to 0.
16
17  The proper point of view to take when interpreting CbcClique is
18  `generalisation of SOS1 on binary variables.' To get into the proper frame
19  of mind, here's an example.
20
21  Consider the following sequence, where x<i> = (1-y<i>):
22     x1 + x2 + x3 <=  1         all strong at 1
23     x1 - y2 + x3 <=  0         y2 strong at 0; x1, x3 strong at 1
24    -y1 - y2 + x3 <= -1         y1, y2 strong at 0, x3 strong at 1
25    -y1 - y2 - y3 <= -2         all strong at 0
26  The first line is a standard SOS1 on binary variables.
27
28  Variables with +1 coefficients are `SOS-style' and variables with -1
29  coefficients are `non-SOS-style'. So numberNonSOSMembers_ simply tells you
30  how many variables have -1 coefficients. The implicit rhs for a clique is
31  1-numberNonSOSMembers_.
32*/
33
34/// Define a clique class
35
36class CbcClique : public CbcObject {
37
38public:
39
40    // Default Constructor
41    CbcClique ();
42
43  /** Useful constructor (which are integer indices) slack can denote a slack
44  // Useful constructor (which are integer indices)
45      in set.  If type == NULL then as if 1
46  */
47    CbcClique (CbcModel * model, int cliqueType, int numberMembers,
48               const int * which, const char * type,
49               int identifier, int slack = -1);
50
51    // Copy constructor
52    CbcClique ( const CbcClique &);
53
54    /// Clone
55    virtual CbcObject * clone() const;
56
57    // Assignment operator
58    CbcClique & operator=( const CbcClique& rhs);
59
60    // Destructor
61    virtual ~CbcClique ();
62
63    /// Infeasibility - large is 0.5
64    virtual double infeasibility(const OsiBranchingInformation * info,
65                                 int &preferredWay) const;
66
67    using CbcObject::feasibleRegion ;
68    /// This looks at solution and sets bounds to contain solution
69    virtual void feasibleRegion();
70
71    /// Creates a branching object
72    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
73    /// Number of members
74    inline int numberMembers() const {
75        return numberMembers_;
76    }
77        /** \brief Number of variables with -1 coefficient
78
79          Original comment: Number of Non SOS members i.e. fixing to zero is strong.
80          See comments at head of class, and comments for type_.
81        */
82
83    inline int numberNonSOSMembers() const {
84        return numberNonSOSMembers_;
85    }
86
87    /// Members (indices in range 0 ... numberIntegers_-1)
88    inline const int * members() const {
89        return members_;
90    }
91
92    /** \brief Type of each member, i.e. which way is strong
93
94    This also specifies whether a variable has a +1 or -1 coefficient.
95      0 => -1 coefficient, 0 is strong value
96      1 -> +1 coefficient, 1 is strong value
97    If unspecified, all coefficients are assumed to be positive.
98
99    Indexed as 0 .. numberMembers_-1
100    */
101        inline char type(int index) const {
102        if (type_) return type_[index];
103        else return 1;
104    }
105
106    /// Clique type - 0 <=, 1 ==
107    inline int cliqueType() const {
108        return cliqueType_;
109    }
110    /// Redoes data when sequence numbers change
111    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
112
113protected:
114    /// data
115    /// Number of members
116    int numberMembers_;
117
118    /// Number of Non SOS members i.e. fixing to zero is strong
119    int numberNonSOSMembers_;
120
121    /// Members (indices in range 0 ... numberIntegers_-1)
122    int * members_;
123
124    /** \brief Strong value for each member.
125
126      This also specifies whether a variable has a +1 or -1 coefficient.
127        0 => -1 coefficient, 0 is strong value
128        1 -> +1 coefficient, 1 is strong value
129      If unspecified, all coefficients are assumed to be positive.
130
131      Indexed as 0 .. numberMembers_-1
132    */
133    char * type_;
134
135    /** \brief Clique type
136
137      0 defines a <= relation, 1 an equality. The assumed value of the rhs is
138      numberNonSOSMembers_+1. (See comments for the class.)
139    */
140    int cliqueType_;
141
142    /** \brief Slack variable for the clique
143
144      Identifies the slack variable for the clique (typically added to convert
145      a <= relation to an equality). Value is sequence number within clique
146      menbers.
147    */
148    int slack_;
149};
150
151/** Branching object for unordered cliques
152
153    Intended for cliques which are long enough to make it worthwhile
154    but <= 64 members.  There will also be ones for long cliques.
155
156    Variable_ is the clique id number (redundant, as the object also holds a
157    pointer to the clique.
158 */
159class CbcCliqueBranchingObject : public CbcBranchingObject {
160
161public:
162
163    // Default Constructor
164    CbcCliqueBranchingObject ();
165
166    // Useful constructor
167    CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
168                              int way,
169                              int numberOnDownSide, const int * down,
170                              int numberOnUpSide, const int * up);
171
172    // Copy constructor
173    CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
174
175    // Assignment operator
176    CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
177
178    /// Clone
179    virtual CbcBranchingObject * clone() const;
180
181    // Destructor
182    virtual ~CbcCliqueBranchingObject ();
183
184    using CbcBranchingObject::branch ;
185    /// Does next branch and updates state
186    virtual double branch();
187
188    using CbcBranchingObject::print ;
189    /** \brief Print something about branch - only if log level high
190    */
191    virtual void print();
192
193    /** Return the type (an integer identifier) of \c this */
194    virtual CbcBranchObjType type() const {
195        return CliqueBranchObj;
196    }
197
198    /** Compare the original object of \c this with the original object of \c
199        brObj. Assumes that there is an ordering of the original objects.
200        This method should be invoked only if \c this and brObj are of the same
201        type.
202        Return negative/0/positive depending on whether \c this is
203        smaller/same/larger than the argument.
204    */
205    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
206
207    /** Compare the \c this with \c brObj. \c this and \c brObj must be of the
208        same type and must have the same original object, but they may have
209        different feasible regions.
210        Return the appropriate CbcRangeCompare value (first argument being the
211        sub/superset if that's the case). In case of overlap (and if \c
212        replaceIfOverlap is true) replace the current branching object with one
213        whose feasible region is the overlap.
214     */
215    virtual CbcRangeCompare compareBranchingObject
216    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
217
218private:
219    /// data
220    const CbcClique * clique_;
221    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
222    unsigned int downMask_[2];
223    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
224    unsigned int upMask_[2];
225};
226
227/** Unordered Clique Branching Object class.
228    These are for cliques which are > 64 members
229    Variable is number of clique.
230 */
231class CbcLongCliqueBranchingObject : public CbcBranchingObject {
232
233public:
234
235    // Default Constructor
236    CbcLongCliqueBranchingObject ();
237
238    // Useful constructor
239    CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
240                                  int way,
241                                  int numberOnDownSide, const int * down,
242                                  int numberOnUpSide, const int * up);
243
244    // Copy constructor
245    CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
246
247    // Assignment operator
248    CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
249
250    /// Clone
251    virtual CbcBranchingObject * clone() const;
252
253    // Destructor
254    virtual ~CbcLongCliqueBranchingObject ();
255
256    using CbcBranchingObject::branch ;
257    /// Does next branch and updates state
258    virtual double branch();
259
260    using CbcBranchingObject::print ;
261    /** \brief Print something about branch - only if log level high
262    */
263    virtual void print();
264
265    /** Return the type (an integer identifier) of \c this */
266    virtual CbcBranchObjType type() const {
267        return LongCliqueBranchObj;
268    }
269
270    /** Compare the original object of \c this with the original object of \c
271        brObj. Assumes that there is an ordering of the original objects.
272        This method should be invoked only if \c this and brObj are of the same
273        type.
274        Return negative/0/positive depending on whether \c this is
275        smaller/same/larger than the argument.
276    */
277    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
278
279    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
280        same type and must have the same original object, but they may have
281        different feasible regions.
282        Return the appropriate CbcRangeCompare value (first argument being the
283        sub/superset if that's the case). In case of overlap (and if \c
284        replaceIfOverlap is true) replace the current branching object with one
285        whose feasible region is the overlap.
286     */
287    virtual CbcRangeCompare compareBranchingObject
288    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
289
290private:
291    /// data
292    const CbcClique * clique_;
293    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
294    unsigned int * downMask_;
295    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
296    unsigned int * upMask_;
297};
298
299#endif
Note: See TracBrowser for help on using the repository browser.