# source:branches/sandbox/Cbc/src/CbcClique.hpp@1362

Last change on this file since 1362 was 1362, checked in by EdwinStraver, 4 years ago

File size: 10.5 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.
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#if 0
189    // No need to override. Default works fine.
190    /** Reset every information so that the branching object appears to point to
191        the previous child. This method does not need to modify anything in any
192        solver. */
193    virtual void previousBranch();
194#endif
195
196    using CbcBranchingObject::print ;
197    /** \brief Print something about branch - only if log level high
198    */
199    virtual void print();
200
201    /** Return the type (an integer identifier) of \c this */
202    virtual int type() const {
203        return 102;
204    }
205
206    /** Compare the original object of \c this with the original object of \c
207        brObj. Assumes that there is an ordering of the original objects.
208        This method should be invoked only if \c this and brObj are of the same
209        type.
210        Return negative/0/positive depending on whether \c this is
211        smaller/same/larger than the argument.
212    */
213    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
214
215    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
216        same type and must have the same original object, but they may have
217        different feasible regions.
218        Return the appropriate CbcRangeCompare value (first argument being the
219        sub/superset if that's the case). In case of overlap (and if \c
220        replaceIfOverlap is true) replace the current branching object with one
221        whose feasible region is the overlap.
222     */
223    virtual CbcRangeCompare compareBranchingObject
224    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
225
226private:
227    /// data
228    const CbcClique * clique_;
229    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
231    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
233};
234
235/** Unordered Clique Branching Object class.
236    These are for cliques which are > 64 members
237    Variable is number of clique.
238 */
239class CbcLongCliqueBranchingObject : public CbcBranchingObject {
240
241public:
242
243    // Default Constructor
244    CbcLongCliqueBranchingObject ();
245
246    // Useful constructor
247    CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
248                                  int way,
249                                  int numberOnDownSide, const int * down,
250                                  int numberOnUpSide, const int * up);
251
252    // Copy constructor
253    CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
254
255    // Assignment operator
256    CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
257
258    /// Clone
259    virtual CbcBranchingObject * clone() const;
260
261    // Destructor
262    virtual ~CbcLongCliqueBranchingObject ();
263
264    using CbcBranchingObject::branch ;
265    /// Does next branch and updates state
266    virtual double branch();
267
268#if 0
269    // No need to override. Default works fine.
270    /** Reset every information so that the branching object appears to point to
271        the previous child. This method does not need to modify anything in any
272        solver. */
273    virtual void previousBranch();
274#endif
275
276    using CbcBranchingObject::print ;
277    /** \brief Print something about branch - only if log level high
278    */
279    virtual void print();
280
281    /** Return the type (an integer identifier) of \c this */
282    virtual int type() const {
283        return 103;
284    }
285
286    /** Compare the original object of \c this with the original object of \c
287        brObj. Assumes that there is an ordering of the original objects.
288        This method should be invoked only if \c this and brObj are of the same
289        type.
290        Return negative/0/positive depending on whether \c this is
291        smaller/same/larger than the argument.
292    */
293    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
294
295    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
296        same type and must have the same original object, but they may have
297        different feasible regions.
298        Return the appropriate CbcRangeCompare value (first argument being the
299        sub/superset if that's the case). In case of overlap (and if \c
300        replaceIfOverlap is true) replace the current branching object with one
301        whose feasible region is the overlap.
302     */
303    virtual CbcRangeCompare compareBranchingObject
304    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
305
306private:
307    /// data
308    const CbcClique * clique_;
309    /// downMask - bit set to fix to weak bounds, not set to leave unfixed