source: trunk/Cbc/src/CbcSOS.hpp @ 2070

Last change on this file since 2070 was 2070, checked in by forrest, 4 years ago

allow sos in lp files and fix odd SOS branching

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