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

Last change on this file since 2419 was 2419, checked in by forrest, 2 years ago

more string parameters and some sos priorities

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.5 KB
Line 
1// $Id: CbcSOS.hpp 2419 2018-11-15 16:15:28Z 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#ifdef CBC_INVESTIGATE_SOS
109    /// Set which Set
110    inline void setSet(int number) {
111      setNumber_=number;
112    }
113    /// Which set
114    inline int whichSet() const {
115      return setNumber_;
116    }
117#endif
118    /// Down number times
119    inline int numberTimesDown() const {
120        return numberTimesDown_;
121    }
122    /// Up number times
123    inline int numberTimesUp() const {
124        return numberTimesUp_;
125    }
126
127    /** Array of weights */
128    inline const double * weights() const {
129        return weights_;
130    }
131
132    /// Set number of members
133    inline void setNumberMembers(int n) {
134        numberMembers_ = n;
135    }
136
137    /// Members (indices in range 0 ... numberColumns-1)
138    inline int * mutableMembers() const {
139        return members_;
140    }
141
142    /** Array of weights */
143    inline double * mutableWeights() const {
144        return weights_;
145    }
146
147    /** \brief Return true if object can take part in normal heuristics
148    */
149    virtual bool canDoHeuristics() const {
150        return (sosType_ == 1 && integerValued_);
151    }
152    /// Set whether set is integer valued or not
153    inline void setIntegerValued(bool yesNo) {
154        integerValued_ = yesNo;
155    }
156private:
157    /// data
158
159    /// Members (indices in range 0 ... numberColumns-1)
160    int * members_;
161  /** \brief Weights for individual members
162
163    Arbitrary weights for members. Can be used to attach meaning to variable
164    values independent of objective coefficients. For example, if the SOS set
165    comprises binary variables used to choose a facility of a given size, the
166    weight could be the corresponding facilty size. Fractional values of the
167    SOS variables can then be used to estimate ideal facility size.
168
169    Weights cannot be completely arbitrary. From the code, they must be
170    differ by at least 1.0e-7
171  */
172
173    double * weights_;
174    /// Current pseudo-shadow price estimate down
175    mutable double shadowEstimateDown_;
176    /// Current pseudo-shadow price estimate up
177    mutable double shadowEstimateUp_;
178    /// Down pseudo ratio
179    double downDynamicPseudoRatio_;
180    /// Up pseudo ratio
181    double upDynamicPseudoRatio_;
182    /// Number of times we have gone down
183    int numberTimesDown_;
184    /// Number of times we have gone up
185    int numberTimesUp_;
186    /// Number of members
187    int numberMembers_;
188    /// SOS type
189    int sosType_;
190#ifdef CBC_INVESTIGATE_SOS
191    /// Which set
192    int setNumber_;
193#endif
194    /// Whether integer valued
195    bool integerValued_;
196    /// Whether odd values e.g. negative
197    bool oddValues_;
198};
199
200/** Branching object for Special ordered sets
201
202    Variable_ is the set id number (redundant, as the object also holds a
203    pointer to the set.
204 */
205class CbcSOSBranchingObject : public CbcBranchingObject {
206
207public:
208
209    // Default Constructor
210    CbcSOSBranchingObject ();
211
212    // Useful constructor
213    CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
214                           int way,
215                           double separator);
216
217    // Copy constructor
218    CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
219
220    // Assignment operator
221    CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
222
223    /// Clone
224    virtual CbcBranchingObject * clone() const;
225
226    // Destructor
227    virtual ~CbcSOSBranchingObject ();
228
229    using CbcBranchingObject::branch ;
230    /// Does next branch and updates state
231    virtual double branch();
232    /** Update bounds in solver as in 'branch' and update given bounds.
233        branchState is -1 for 'down' +1 for 'up' */
234    virtual void fix(OsiSolverInterface * solver,
235                     double * lower, double * upper,
236                     int branchState) const ;
237
238    /** Reset every information so that the branching object appears to point to
239        the previous child. This method does not need to modify anything in any
240        solver. */
241    virtual void previousBranch() {
242        CbcBranchingObject::previousBranch();
243        computeNonzeroRange();
244    }
245
246    using CbcBranchingObject::print ;
247    /** \brief Print something about branch - only if log level high
248    */
249    virtual void print();
250
251    /** Return the type (an integer identifier) of \c this */
252    virtual CbcBranchObjType type() const {
253        return SoSBranchObj;
254    }
255
256    /** Compare the original object of \c this with the original object of \c
257        brObj. Assumes that there is an ordering of the original objects.
258        This method should be invoked only if \c this and brObj are of the same
259        type.
260        Return negative/0/positive depending on whether \c this is
261        smaller/same/larger than the argument.
262    */
263    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
264
265    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
266        same type and must have the same original object, but they may have
267        different feasible regions.
268        Return the appropriate CbcRangeCompare value (first argument being the
269        sub/superset if that's the case). In case of overlap (and if \c
270        replaceIfOverlap is true) replace the current branching object with one
271        whose feasible region is the overlap.
272     */
273    virtual CbcRangeCompare compareBranchingObject
274    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
275
276    /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
277    void computeNonzeroRange();
278
279private:
280    /// data
281    const CbcSOS * set_;
282    /// separator
283    double separator_;
284    /** The following two members describe the range in the members_ of the
285        original object that whose upper bound is not fixed to 0. This is not
286        necessary for Cbc to function correctly, this is there for heuristics so
287        that separate branching decisions on the same object can be pooled into
288        one branching object. */
289    int firstNonzero_;
290    int lastNonzero_;
291};
292#endif
293
Note: See TracBrowser for help on using the repository browser.