# source:stable/2.7/Cbc/src/CbcClique.hpp@1675

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

sync with trunk rev1674

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