source: trunk/Cbc/src/CbcClique.hpp

Last change on this file was 2465, checked in by unxusr, 5 months ago

script to format sources

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