source: trunk/Cbc/src/CbcClique.hpp @ 1573

Last change on this file since 1573 was 1573, checked in by lou, 8 years ago

Change to EPL license notice.

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