source: stable/2.6/Cbc/src/CbcSOS.hpp @ 2122

Last change on this file since 2122 was 1432, checked in by bjarni, 9 years ago

Added extra return at end of each source file where needed, to remove possible linefeed conflicts (NightlyBuild? errors)

File size: 9.0 KB
Line 
1// Edwin 11/9/2009-- carved out of CbcBranchActual
2#ifndef CbcSOS_H
3#define CbcSOS_H
4
5/** \brief Branching object for Special Ordered Sets of type 1 and 2.
6
7  SOS1 are an ordered set of variables where at most one variable can be
8  non-zero. SOS1 are commonly defined with binary variables (interpreted as
9  selection between alternatives) but this is not necessary.  An SOS1 with
10  all binary variables is a special case of a clique (setting any one
11  variable to 1 forces all others to 0).
12
13  In theory, the implementation makes no assumptions about integrality in
14  Type 1 sets. In practice, there are places where the code seems to have been
15  written with a binary SOS mindset. Current development of SOS branching
16  objects is proceeding in OsiSOS.
17
18  SOS2 are an ordered set of variables in which at most two consecutive
19  variables can be non-zero and must sum to 1 (interpreted as interpolation
20  between two discrete values). By definition the variables are non-integer.
21*/
22
23class CbcSOS : public CbcObject {
24
25public:
26
27    // Default Constructor
28    CbcSOS ();
29
30        /** \brief Constructor with SOS type and member information
31
32    Type specifies SOS 1 or 2. Identifier is an arbitrary value.
33
34    Which should be an array of variable indices with numberMembers entries.
35    Weights can be used to assign arbitrary weights to variables, in the order
36    they are specified in which. If no weights are provided, a default array of
37    0, 1, 2, ... is generated.
38        */
39
40    CbcSOS (CbcModel * model, int numberMembers,
41            const int * which, const double * weights, int identifier,
42            int type = 1);
43
44    // Copy constructor
45    CbcSOS ( const CbcSOS &);
46
47    /// Clone
48    virtual CbcObject * clone() const;
49
50    // Assignment operator
51    CbcSOS & operator=( const CbcSOS& rhs);
52
53    // Destructor
54    virtual ~CbcSOS ();
55
56    /// Infeasibility - large is 0.5
57    virtual double infeasibility(const OsiBranchingInformation * info,
58                                 int &preferredWay) const;
59
60    using CbcObject::feasibleRegion ;
61    /// This looks at solution and sets bounds to contain solution
62    virtual void feasibleRegion();
63
64    /// Creates a branching object
65    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
66
67
68
69    /** Pass in information on branch just done and create CbcObjectUpdateData instance.
70        If object does not need data then backward pointer will be NULL.
71        Assumes can get information from solver */
72    virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
73            const CbcNode * node,
74            const CbcBranchingObject * branchingObject);
75    /// Update object by CbcObjectUpdateData
76    virtual void updateInformation(const CbcObjectUpdateData & data) ;
77    using CbcObject::solverBranch ;
78    /** Create an OsiSolverBranch object
79
80        This returns NULL if branch not represented by bound changes
81    */
82    virtual OsiSolverBranch * solverBranch() const;
83    /// Redoes data when sequence numbers change
84    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
85
86    /// Construct an OsiSOS object
87    OsiSOS * osiObject(const OsiSolverInterface * solver) const;
88    /// Number of members
89    inline int numberMembers() const {
90        return numberMembers_;
91    }
92
93    /// Members (indices in range 0 ... numberColumns-1)
94    inline const int * members() const {
95        return members_;
96    }
97
98    /// SOS type
99    inline int sosType() const {
100        return sosType_;
101    }
102    /// Down number times
103    inline int numberTimesDown() const {
104        return numberTimesDown_;
105    }
106    /// Up number times
107    inline int numberTimesUp() const {
108        return numberTimesUp_;
109    }
110
111    /** Array of weights */
112    inline const double * weights() const {
113        return weights_;
114    }
115
116    /// Set number of members
117    inline void setNumberMembers(int n) {
118        numberMembers_ = n;
119    }
120
121    /// Members (indices in range 0 ... numberColumns-1)
122    inline int * mutableMembers() const {
123        return members_;
124    }
125
126    /** Array of weights */
127    inline double * mutableWeights() const {
128        return weights_;
129    }
130
131    /** \brief Return true if object can take part in normal heuristics
132    */
133    virtual bool canDoHeuristics() const {
134        return (sosType_ == 1 && integerValued_);
135    }
136    /// Set whether set is integer valued or not
137    inline void setIntegerValued(bool yesNo) {
138        integerValued_ = yesNo;
139    }
140private:
141    /// data
142
143    /// Members (indices in range 0 ... numberColumns-1)
144    int * members_;
145  /** \brief Weights for individual members
146
147    Arbitrary weights for members. Can be used to attach meaning to variable
148    values independent of objective coefficients. For example, if the SOS set
149    comprises binary variables used to choose a facility of a given size, the
150    weight could be the corresponding facilty size. Fractional values of the
151    SOS variables can then be used to estimate ideal facility size.
152
153    Weights cannot be completely arbitrary. From the code, they must be
154    differ by at least 1.0e-7
155  */
156
157    double * weights_;
158    /// Current pseudo-shadow price estimate down
159    mutable double shadowEstimateDown_;
160    /// Current pseudo-shadow price estimate up
161    mutable double shadowEstimateUp_;
162    /// Down pseudo ratio
163    double downDynamicPseudoRatio_;
164    /// Up pseudo ratio
165    double upDynamicPseudoRatio_;
166    /// Number of times we have gone down
167    int numberTimesDown_;
168    /// Number of times we have gone up
169    int numberTimesUp_;
170    /// Number of members
171    int numberMembers_;
172    /// SOS type
173    int sosType_;
174    /// Whether integer valued
175    bool integerValued_;
176};
177
178/** Branching object for Special ordered sets
179
180    Variable_ is the set id number (redundant, as the object also holds a
181    pointer to the set.
182 */
183class CbcSOSBranchingObject : public CbcBranchingObject {
184
185public:
186
187    // Default Constructor
188    CbcSOSBranchingObject ();
189
190    // Useful constructor
191    CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
192                           int way,
193                           double separator);
194
195    // Copy constructor
196    CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
197
198    // Assignment operator
199    CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
200
201    /// Clone
202    virtual CbcBranchingObject * clone() const;
203
204    // Destructor
205    virtual ~CbcSOSBranchingObject ();
206
207    using CbcBranchingObject::branch ;
208    /// Does next branch and updates state
209    virtual double branch();
210    /** Update bounds in solver as in 'branch' and update given bounds.
211        branchState is -1 for 'down' +1 for 'up' */
212    virtual void fix(OsiSolverInterface * solver,
213                     double * lower, double * upper,
214                     int branchState) const ;
215
216    /** Reset every information so that the branching object appears to point to
217        the previous child. This method does not need to modify anything in any
218        solver. */
219    virtual void previousBranch() {
220        CbcBranchingObject::previousBranch();
221        computeNonzeroRange();
222    }
223
224    using CbcBranchingObject::print ;
225    /** \brief Print something about branch - only if log level high
226    */
227    virtual void print();
228
229    /** Return the type (an integer identifier) of \c this */
230    virtual CbcBranchObjType type() const {
231        return SoSBranchObj;
232    }
233
234    /** Compare the original object of \c this with the original object of \c
235        brObj. Assumes that there is an ordering of the original objects.
236        This method should be invoked only if \c this and brObj are of the same
237        type.
238        Return negative/0/positive depending on whether \c this is
239        smaller/same/larger than the argument.
240    */
241    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
242
243    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
244        same type and must have the same original object, but they may have
245        different feasible regions.
246        Return the appropriate CbcRangeCompare value (first argument being the
247        sub/superset if that's the case). In case of overlap (and if \c
248        replaceIfOverlap is true) replace the current branching object with one
249        whose feasible region is the overlap.
250     */
251    virtual CbcRangeCompare compareBranchingObject
252    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
253
254    /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
255    void computeNonzeroRange();
256
257private:
258    /// data
259    const CbcSOS * set_;
260    /// separator
261    double separator_;
262    /** The following two members describe the range in the members_ of the
263        original object that whose upper bound is not fixed to 0. This is not
264        necessary for Cbc to function correctly, this is there for heuristics so
265        that separate branching decisions on the same object can be pooled into
266        one branching object. */
267    int firstNonzero_;
268    int lastNonzero_;
269};
270#endif
271
Note: See TracBrowser for help on using the repository browser.