Scippy

SCIP

Solving Constraint Integer Programs

weight_space_vertex.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program PolySCIP */
4 /* */
5 /* Copyright (C) 2012-2019 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.cpp
17  * @brief Implements class representing vertex of (partial) weight space polyhedron
18  * @author Sebastian Schenker
19  * @author Timo Strunk
20  *
21  */
22 
23 #include "weight_space_vertex.h"
24 
25 #include <algorithm> // std::copy, std::set_intersection, std::sort
26 #include <cstddef>
27 #include <iterator> // std::back_inserter
28 #include <limits>
29 #include <memory> //std::shared
30 #include <numeric> // std::inner_product;
31 #include <ostream>
32 
33 #include "global_functions.h" //global::print
34 #include "polyscip_types.h"
35 #include "weight_space_facet.h"
37 
38 using std::ostream;
39 using std::shared_ptr;
40 using std::sort;
41 using std::vector;
42 
43 namespace polyscip {
44 
45  /**
46  * Default constructor
47  * @param incident_facets Incident facets of the constructed vertex
48  * @param weight Lhs coefficients of the constructed vertex
49  * @param weighted_obj_val Rhs coefficient of the constructed vertex
50  * @param sort_facets if true, incident facets are sorted
51  */
53  WeightType weight,
54  ValueType weighted_obj_val,
55  bool sort_facets)
56  : vertex_status_(VertexStatus::unmarked),
57  incident_facets_(std::move(incident_facets)),
58  weight_(std::move(weight)),
59  weighted_obj_val_{weighted_obj_val} {
60  if (sort_facets) // sort facets in order to be able to use std::set_intersection in other constructor
61  sort(begin(incident_facets_), end(incident_facets_), WeightSpaceFacet::Compare());
62  }
63 
64  /**
65  * Returns weighted objective value of vertex
66  * @return weighted objective value
67  */
69  return weighted_obj_val_;
70  }
71 
72 
73  /**
74  * Constructor creating a new vertex from an obsolete and non-obsolete vertex via
75  * the equality new_vertex = obs_coeff * obs + non_obs_coeff * non_obs
76  * @param obs_coeff Coefficient of obsolete vertex
77  * @param non_obs_coeff Coefficient of non-obsolete vertex
78  * @param obs Obsolete vertex
79  * @param non_obs Non-obsolete vertex
80  * @param incident_facet Incident facet of new vertex
81  * @param wsp_dimension Dimension of the corresponding weight space polyhedron
82  */
84  double non_obs_coeff,
85  const WeightSpaceVertex* obs,
86  const WeightSpaceVertex* non_obs,
87  const std::shared_ptr<const WeightSpaceFacet>& incident_facet,
88  std::size_t wsp_dimension)
89  : vertex_status_(VertexStatus::unmarked)
90  {
91  assert (obs != non_obs);
92  // get intersection of facets of obs and non_obs
93  std::set_intersection(obs->incident_facets_.cbegin(),
94  obs->incident_facets_.cend(),
95  non_obs->incident_facets_.cbegin(),
96  non_obs->incident_facets_.cend(),
97  std::back_inserter(incident_facets_),
99  auto upper_it = std::upper_bound(begin(incident_facets_),
100  end(incident_facets_),
101  incident_facet, WeightSpaceFacet::Compare());
102  incident_facets_.insert(upper_it, incident_facet);
103  assert(incident_facets_.size() >= wsp_dimension);
104 
105  std::transform(begin(obs->weight_), end(obs->weight_),
106  begin(non_obs->weight_), std::back_inserter(weight_),
107  [obs_coeff, non_obs_coeff](ValueType obs_val, ValueType non_obs_val) {
108  return obs_coeff * obs_val - non_obs_coeff * non_obs_val;
109  });
110  auto normalize_val = *(std::max_element(begin(weight_), end(weight_)));
111  assert (normalize_val > 0);
112  std::transform(begin(weight_), end(weight_), begin(weight_),
113  [normalize_val](const ValueType &val) { return val / normalize_val; });
114  weighted_obj_val_ = obs_coeff*obs->weighted_obj_val_ - non_obs_coeff*non_obs->weighted_obj_val_; // return m_coeff * ray_minus - p_coeff * ray_plus
115  weighted_obj_val_ /= normalize_val;
116  }
117 
118  /**
119  * Returns associated weight vector of weight space vertex
120  * @return Weight vector of vertex
121  */
123  return weight_;
124  }
125 
126  /**
127  * Outcome vector \\cdot weight vector
128  * @param outcome Outcome vector
129  * @return Scalarproduct of outcome and weight vector of vertex
130  */
131  double WeightSpaceVertex::getWeightedOutcome(const OutcomeType& outcome) const {
132  assert (outcome.size() == weight_.size());
133  return std::inner_product(begin(outcome),
134  end(outcome),
135  begin(weight_),
136  0.);
137  }
138 
139  /**
140  * Computes slack
141  * @param outcome Outcome vector
142  * @param outcome_is_ray Indicates whether given outcome corresponds to ray
143  * @return outcome \\cdot weight - weighted_obj_val if outcome corresponds to point;
144  * else outcome \\cdot weight
145  */
146  double WeightSpaceVertex::computeSlack(const OutcomeType& outcome, bool outcome_is_ray) const {
147  double slack = getWeightedOutcome(outcome);
148  if (!outcome_is_ray)
149  slack -= getCurrentWOV();
150  return slack;
151  }
152 
153  /**
154  * Compute convex combination of weights
155  * @param weight1 First weight vector
156  * @param weight2 Second weight vector
157  * @param h Coefficient for convex combination
158  * @return h * weight1 + (1-h) * weight2
159  */
160  const WeightType WeightSpaceVertex::calculateWeightCombination(double h,
161  const WeightType& weight1,
162  const WeightType& weight2) {
163  assert (weight1.size() == weight2.size());
164  auto new_weight = WeightType(weight1.size(),0.);
165  // new_weight = h*weight1 + (1-h)*weight2
166  transform(begin(weight1), end(weight1), begin(weight2),
167  begin(new_weight), [h](ValueType w1, ValueType w2){return h*w1 + (1.-h)*w2;});
168  return new_weight;
169  }
170 
171  /**
172  * Compare weight vectors
173  * @param weight Weight to check against
174  * @return true if given weight vector coincides with weight vector of vertex; otherwise false
175  */
176  bool WeightSpaceVertex::hasSameWeight(const WeightType& weight) const {
177  return weight_ == weight;
178  }
179 
180  /**
181  * Indicates whether weight vector of vertex corresponds to some unit vector
182  * @return true if weight vector of vertex corresponds to some unit vector; otherwise false
183  */
185  for (std::size_t i=0; i<weight_.size(); ++i) {
186  auto weight = WeightType(weight_.size(), 0.);
187  weight[i] = 1.;
188  if (hasSameWeight(weight))
189  return true;
190  }
191  return false;
192  }
193 
194  /**
195  * Indicates whether weight vector of vertex corresponds to zero vector
196  * @return true if weight vector of vertex is zero vector; otherwise false
197  */
199  for (std::size_t i=0; i<weight_.size(); ++i) {
200  if (weight_[i] != 0)
201  return false;
202  }
203  return true;
204  }
205 
206  /**
207  * Print function
208  * @param os Output stream to write to
209  * @param printFacets Indicate whehter incident facets should be printed
210  */
211  void WeightSpaceVertex::print(ostream& os, bool printFacets) const {
212  global::print(weight_, "WeightSpaceVertex: weight = [", "]", os);
213  os << "\n wov = " << weighted_obj_val_ << "\n";
214  if (printFacets) {
215  os << " defining facets: \n";
216  for (const auto &facet : incident_facets_)
217  facet->print(os);
218  }
219  os << "Vertex-Status: ";
220  switch (vertex_status_) {
222  os << "marked\n";
223  break;
225  os << "obsolete\n";
226  break;
228  os << "unmarked\n";
229  break;
231  os << "special\n";
232  break;
233  }
234  }
235 
236 }
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
Definition: pqueue.h:28
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
Class representing the 1-skeleton of the weight space polyhedron.
SCIP_VAR * h
Definition: circlepacking.c:59
Class representing a vertex of the (partial) weight space polyhedron.
double computeSlack(const OutcomeType &outcome, bool outcome_is_ray) const
Global helper functions.
std::vector< std::shared_ptr< const WeightSpaceFacet > > FacetContainer
Container for facets.
bool hasSameWeight(const WeightType &weight) const
double getWeightedOutcome(const OutcomeType &outcome) const
Class representing a facet of the weight space polyhedron.
Class representing a vertex of the (partial) weight space polyhedron.