Scippy

SCIP

Solving Constraint Integer Programs

weight_space_vertex.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program PolySCIP */
4 /* */
5 /* Copyright (C) 2012-2018 Konrad-Zuse-Zentrum */
6 /* fuer Informationstechnik Berlin */
7 /* */
8 /* PolySCIP is distributed under the terms of the ZIB Academic License. */
9 /* */
10 /* You should have received a copy of the ZIB Academic License */
11 /* along with PolySCIP; see the file LICENCE. */
12 /* */
13 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
14 
15 /**
16  * @file weight_space_vertex.h
17  * @brief Class representing a vertex of the (partial) weight space polyhedron
18  * @author Sebastian Schenker
19  * @author Timo Strunk
20  *
21  */
22 
23 #ifndef POLYSCIP_SRC_WEIGHT_SPACE_VERTEX_H_INCLUDED
24 #define POLYSCIP_SRC_WEIGHT_SPACE_VERTEX_H_INCLUDED
25 
26 #include <cstddef>
27 #include <functional>
28 #include <iosfwd>
29 #include <memory> // std::shared_ptr
30 #include <vector>
31 
32 #include "objscip/objscip.h"
33 #include "polyscip_types.h"
35 
36 namespace polyscip {
37 
38  /**
39  * @class WeightSpaceVertex
40  * @brief Class representing a vertex of the (partial) weight space polyhedron
41  * @details A vertex of the (partial) weight space polyhedron is given
42  * by a weight vector 'weight_' and an weighted objective value 'weighted_obj_val' and
43  * is active for a certain number of inequalities of the form
44  * 'weight_ \\cdot y >= weighted_obj_val' where y are non-dominated extreme points
45  * of the considered problem
46  */
48 
49  public:
50  /**
51  * Different statuses a weight space vertex can take
52  */
54 
55  /**
56  * Default constructor
57  * @param incident_facets Incident facets of the constructed vertex
58  * @param weight Lhs coefficients of the constructed vertex
59  * @param weighted_obj_val Rhs coefficient of the constructed vertex
60  * @param sort_facets if true, incident facets are sorted
61  */
63  WeightType weight,
64  ValueType weighted_obj_val,
65  bool sort_facets = true);
66 
67  /**
68  * Constructor creating a new vertex from an obsolete and non-obsolete vertex via
69  * the equality new_vertex = obs_coeff * obs + non_obs_coeff * non_obs
70  * @param obs_coeff Coefficient of obsolete vertex
71  * @param non_obs_coeff Coefficient of non-obsolete vertex
72  * @param obs Obsolete vertex
73  * @param non_obs Non-obsolete vertex
74  * @param incident_facet Incident facet of new vertex
75  * @param wsp_dimension Dimension of the corresponding weight space polyhedron
76  */
77  explicit WeightSpaceVertex(double obs_coeff,
78  double non_obs_coeff,
79  const WeightSpaceVertex* obs,
80  const WeightSpaceVertex* non_obs,
81  const std::shared_ptr<const WeightSpaceFacet>& incident_facet,
82  std::size_t wsp_dimension);
83 
84  /**
85  * Returns associated weight vector of weight space vertex
86  * @return Weight vector of vertex
87  */
88  WeightType getWeight() const;
89 
90  /**
91  * Returns weighted objective value of vertex
92  * @return weighted objective value
93  */
94  ValueType getCurrentWOV() const;
95 
96  /**
97  * Outcome vector \\cdot weight vector
98  * @param outcome Outcome vector
99  * @return Scalarproduct of outcome and weight vector of vertex
100  */
101  double getWeightedOutcome(const OutcomeType& outcome) const;
102 
103  /**
104  * Computes slack
105  * @param outcome Outcome vector
106  * @param outcome_is_ray Indicates whether given outcome corresponds to ray
107  * @return outcome \\cdot weight - weighted_obj_val if outcome corresponds to point;
108  * else outcome \\cdot weight
109  */
110  double computeSlack(const OutcomeType& outcome, bool outcome_is_ray) const;
111 
112 
113  /**
114  * Indicates whether weight vector of vertex corresponds to some unit vector
115  * @return true if weight vector of vertex corresponds to some unit vector; otherwise false
116  */
117  bool hasUnitWeight() const;
118 
119  /**
120  * Indicates whether weight vector of vertex corresponds to zero vector
121  * @return true if weight vector of vertex is zero vector; otherwise false
122  */
123  bool hasZeroWeight() const;
124 
125  /**
126  * Get vertex status
127  * @return Status of vertex
128  */
129  VertexStatus getStatus() const {return vertex_status_;};
130 
131  /**
132  * Set vertex status
133  * @param status New status of vertex
134  */
135  void setStatus(VertexStatus status) {vertex_status_ = status;};
136 
137  /**
138  * Compare weight vectors
139  * @param weight Weight to check against
140  * @return true if given weight vector coincides with weight vector of vertex; otherwise false
141  */
142  bool hasSameWeight(const WeightType& weight) const;
143 
144  /**
145  * Print function
146  * @param os Output stream to write to
147  * @param printFacets Indicate whehter incident facets should be printed
148  */
149  void print(std::ostream& os, bool printFacets = false) const;
150 
151  private:
152 
153  /**
154  * @relates WeightSpacePolyhedron
155  * @param v
156  * @param w
157  * @return
158  */
160  const WeightSpaceVertex* w);
161 
162  /**
163  * Compute convex combination of weights
164  * @param weight1 First weight vector
165  * @param weight2 Second weight vector
166  * @param h Coefficient for convex combination
167  * @return h * weight1 + (1-h) * weight2
168  */
169  static const WeightType calculateWeightCombination(double h,
170  const WeightType& weight1,
171  const WeightType& weight2);
172 
173 
174  VertexStatus vertex_status_; ///< Corresponding status of vertex
175  WeightSpacePolyhedron::FacetContainer incident_facets_; ///< Incident facets of vertex
176  WeightType weight_; ///< Corresponding weight vector of vertex
177  ValueType weighted_obj_val_; ///< Corresponding weighted objective value of vertex
178  };
179 
180 }
181 
182 #endif //POLYSCIP_SRC_WEIGHT_SPACE_VERTEX_H_INCLUDED
bool areAdjacent(const WeightSpaceVertex *v, const WeightSpaceVertex *w)
std::vector< ValueType > WeightType
Type for weight vectors.
SCIP_Real ValueType
Type for computed values.
WeightSpaceVertex(WeightSpacePolyhedron::FacetContainer incident_facets, WeightType weight, ValueType weighted_obj_val, bool sort_facets=true)
General types used for PolySCIP.
std::vector< ValueType > OutcomeType
Type for points, rays in objective space.
void print(std::ostream &os, bool printFacets=false) const
SCIP_VAR * w
Definition: circlepacking.c:58
C++ wrapper classes for SCIP.
Class representing the 1-skeleton of the weight space polyhedron.
SCIP_VAR * h
Definition: circlepacking.c:59
VertexStatus getStatus() const
double computeSlack(const OutcomeType &outcome, bool outcome_is_ray) const
std::vector< std::shared_ptr< const WeightSpaceFacet > > FacetContainer
Container for facets.
void setStatus(VertexStatus status)
bool hasSameWeight(const WeightType &weight) const
double getWeightedOutcome(const OutcomeType &outcome) const
Class representing a vertex of the (partial) weight space polyhedron.