// $Id$
// Copyright (C) 2002, International Business Machines
// Corporation and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
// Edwin 11/9/2009-- carved out of CbcBranchActual
#ifndef CbcSOS_H
#define CbcSOS_H
/** \brief Branching object for Special Ordered Sets of type 1 and 2.
SOS1 are an ordered set of variables where at most one variable can be
non-zero. SOS1 are commonly defined with binary variables (interpreted as
selection between alternatives) but this is not necessary. An SOS1 with
all binary variables is a special case of a clique (setting any one
variable to 1 forces all others to 0).
In theory, the implementation makes no assumptions about integrality in
Type 1 sets. In practice, there are places where the code seems to have been
written with a binary SOS mindset. Current development of SOS branching
objects is proceeding in OsiSOS.
SOS2 are an ordered set of variables in which at most two consecutive
variables can be non-zero and must sum to 1 (interpreted as interpolation
between two discrete values). By definition the variables are non-integer.
*/
class CbcSOS : public CbcObject {
public:
// Default Constructor
CbcSOS ();
/** \brief Constructor with SOS type and member information
Type specifies SOS 1 or 2. Identifier is an arbitrary value.
Which should be an array of variable indices with numberMembers entries.
Weights can be used to assign arbitrary weights to variables, in the order
they are specified in which. If no weights are provided, a default array of
0, 1, 2, ... is generated.
*/
CbcSOS (CbcModel * model, int numberMembers,
const int * which, const double * weights, int identifier,
int type = 1);
// Copy constructor
CbcSOS ( const CbcSOS &);
/// Clone
virtual CbcObject * clone() const;
// Assignment operator
CbcSOS & operator=( const CbcSOS& rhs);
// Destructor
virtual ~CbcSOS ();
/// Infeasibility - large is 0.5
virtual double infeasibility(const OsiBranchingInformation * info,
int &preferredWay) const;
using CbcObject::feasibleRegion ;
/// This looks at solution and sets bounds to contain solution
virtual void feasibleRegion();
/// Creates a branching object
virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
/** Pass in information on branch just done and create CbcObjectUpdateData instance.
If object does not need data then backward pointer will be NULL.
Assumes can get information from solver */
virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
const CbcNode * node,
const CbcBranchingObject * branchingObject);
/// Update object by CbcObjectUpdateData
virtual void updateInformation(const CbcObjectUpdateData & data) ;
using CbcObject::solverBranch ;
/** Create an OsiSolverBranch object
This returns NULL if branch not represented by bound changes
*/
virtual OsiSolverBranch * solverBranch() const;
/// Redoes data when sequence numbers change
virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
/// Construct an OsiSOS object
OsiSOS * osiObject(const OsiSolverInterface * solver) const;
/// Number of members
inline int numberMembers() const {
return numberMembers_;
}
/// Members (indices in range 0 ... numberColumns-1)
inline const int * members() const {
return members_;
}
/// SOS type
inline int sosType() const {
return sosType_;
}
/// Down number times
inline int numberTimesDown() const {
return numberTimesDown_;
}
/// Up number times
inline int numberTimesUp() const {
return numberTimesUp_;
}
/** Array of weights */
inline const double * weights() const {
return weights_;
}
/// Set number of members
inline void setNumberMembers(int n) {
numberMembers_ = n;
}
/// Members (indices in range 0 ... numberColumns-1)
inline int * mutableMembers() const {
return members_;
}
/** Array of weights */
inline double * mutableWeights() const {
return weights_;
}
/** \brief Return true if object can take part in normal heuristics
*/
virtual bool canDoHeuristics() const {
return (sosType_ == 1 && integerValued_);
}
/// Set whether set is integer valued or not
inline void setIntegerValued(bool yesNo) {
integerValued_ = yesNo;
}
private:
/// data
/// Members (indices in range 0 ... numberColumns-1)
int * members_;
/** \brief Weights for individual members
Arbitrary weights for members. Can be used to attach meaning to variable
values independent of objective coefficients. For example, if the SOS set
comprises binary variables used to choose a facility of a given size, the
weight could be the corresponding facilty size. Fractional values of the
SOS variables can then be used to estimate ideal facility size.
Weights cannot be completely arbitrary. From the code, they must be
differ by at least 1.0e-7
*/
double * weights_;
/// Current pseudo-shadow price estimate down
mutable double shadowEstimateDown_;
/// Current pseudo-shadow price estimate up
mutable double shadowEstimateUp_;
/// Down pseudo ratio
double downDynamicPseudoRatio_;
/// Up pseudo ratio
double upDynamicPseudoRatio_;
/// Number of times we have gone down
int numberTimesDown_;
/// Number of times we have gone up
int numberTimesUp_;
/// Number of members
int numberMembers_;
/// SOS type
int sosType_;
/// Whether integer valued
bool integerValued_;
};
/** Branching object for Special ordered sets
Variable_ is the set id number (redundant, as the object also holds a
pointer to the set.
*/
class CbcSOSBranchingObject : public CbcBranchingObject {
public:
// Default Constructor
CbcSOSBranchingObject ();
// Useful constructor
CbcSOSBranchingObject (CbcModel * model, const CbcSOS * clique,
int way,
double separator);
// Copy constructor
CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
// Assignment operator
CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
/// Clone
virtual CbcBranchingObject * clone() const;
// Destructor
virtual ~CbcSOSBranchingObject ();
using CbcBranchingObject::branch ;
/// Does next branch and updates state
virtual double branch();
/** Update bounds in solver as in 'branch' and update given bounds.
branchState is -1 for 'down' +1 for 'up' */
virtual void fix(OsiSolverInterface * solver,
double * lower, double * upper,
int branchState) const ;
/** Reset every information so that the branching object appears to point to
the previous child. This method does not need to modify anything in any
solver. */
virtual void previousBranch() {
CbcBranchingObject::previousBranch();
computeNonzeroRange();
}
using CbcBranchingObject::print ;
/** \brief Print something about branch - only if log level high
*/
virtual void print();
/** Return the type (an integer identifier) of \c this */
virtual CbcBranchObjType type() const {
return SoSBranchObj;
}
/** Compare the original object of \c this with the original object of \c
brObj. Assumes that there is an ordering of the original objects.
This method should be invoked only if \c this and brObj are of the same
type.
Return negative/0/positive depending on whether \c this is
smaller/same/larger than the argument.
*/
virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
same type and must have the same original object, but they may have
different feasible regions.
Return the appropriate CbcRangeCompare value (first argument being the
sub/superset if that's the case). In case of overlap (and if \c
replaceIfOverlap is true) replace the current branching object with one
whose feasible region is the overlap.
*/
virtual CbcRangeCompare compareBranchingObject
(const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
/** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
void computeNonzeroRange();
private:
/// data
const CbcSOS * set_;
/// separator
double separator_;
/** The following two members describe the range in the members_ of the
original object that whose upper bound is not fixed to 0. This is not
necessary for Cbc to function correctly, this is there for heuristics so
that separate branching decisions on the same object can be pooled into
one branching object. */
int firstNonzero_;
int lastNonzero_;
};
#endif