Scippy

SCIP

Solving Constraint Integer Programs

weight_space_polyhedron.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_polyhedron.cpp
17  * @brief Implements class representing 1-skeleton of weight space polyhedron
18  * @author Sebastian Schenker
19  *
20  */
21 
23 
24 #include <algorithm> // std::transform
25 #include <cstddef> // std::size_t
26 #include <iomanip> // std::setprecision
27 #include <iostream>
28 #include <forward_list>
29 #include <functional> // std::negate
30 #include <iterator>
31 #include <memory> // std::make_shared
32 #include <numeric> // std::inner_product
33 #include <ostream>
34 #include <unordered_map>
35 #include <utility> // std::move, std::pair
36 #include <vector>
37 
39 #include "global_functions.h"
40 #include "objscip/objscip.h"
41 #include "polyscip_types.h"
42 #include "weight_space_facet.h"
43 #include "weight_space_vertex.h"
44 
45 using std::inner_product;
46 using std::make_shared;
47 using std::ostream;
48 using std::pair;
49 using std::shared_ptr;
50 using std::size_t;
51 using std::transform;
52 using std::vector;
53 
54 namespace polyscip {
55 
56  /**
57  * Default constructor
58  * @param wsp_dimension Dimension of the weight space polyhedron
59  * @param v_rep v-representation of the initial polyhedron
60  * @param h_rep h-representation of the initial polyhedron
61  */
63  V_RepC v_rep,
64  H_RepC h_rep)
65  : wsp_dimension_(dimension),
66  curr_investigated_vertex_(nullptr) {
67  assert (!v_rep.empty());
68  assert (!h_rep.empty());
69  createInitialVerticesAndSkeleton(std::move(h_rep), std::move(v_rep));
70  }
71 
72  /**
73  * Create initial weight space vertices and corresponding 1-skeleton of weight space polyhedron
74  * @param h_rep h-representation of initial weight space polyhedron
75  * @param v_rep v-representation of initial weight space polyhedron
76  */
77  void WeightSpacePolyhedron::createInitialVerticesAndSkeleton(H_RepC h_rep,
78  V_RepC v_rep) {
79  auto initial_facets = FacetContainer {};
80  for (auto& h : h_rep) {
81  initial_facets.emplace_back(make_shared<WeightSpaceFacet>(std::move(h.first), std::move(h.second)));
82  }
83  for (auto& v : v_rep) {
84  auto inc_facets = getIncidentFacets(*v, initial_facets);
85  auto vertex = new WeightSpaceVertex(inc_facets,
86  v->moveWeight(),
87  v->getWov());
88 
89  if (vertex->hasUnitWeight()) {
91  marked_and_special_vertices_.push_back(vertex);
92  }
93  else if (vertex->hasZeroWeight()) {
95  marked_and_special_vertices_.push_back(vertex);
96  }
97  else {
98  unmarked_vertices_.push_back(vertex); // VertexStatus::unmarked
99  }
100  }
101  }
102 
103  /**
104  * Get incident facets
105  * @param v Corresponding vertex
106  * @param initial_facets Facets
107  * @return Incident facets of given vertex with respect to given facets
108  */
109  WeightSpacePolyhedron::FacetContainer WeightSpacePolyhedron::getIncidentFacets(const V_RepT& v,
110  const FacetContainer& initial_facets) const {
111  auto facets = FacetContainer{};
112  for (size_t i=0; i<initial_facets.size(); i++) {
113  if (v.isZeroSlackIndex(i))
114  facets.push_back(initial_facets[i]);
115  }
116  return facets;
117  }
118 
119  /**
120  * Destructor
121  */
123  for (auto v_ptr : marked_and_special_vertices_)
124  delete v_ptr;
125  for (auto v_ptr : unmarked_vertices_)
126  delete v_ptr;
127  for (auto v_ptr : obsolete_vertices_)
128  delete v_ptr;
129  delete curr_investigated_vertex_;
130  }
131 
132  /**
133  * Indicates whether there is an unmarked vertex in the current polyhedron
134  * @return true if there is an unmarked vertex; false otherwise
135  */
137  return !unmarked_vertices_.empty();
138  }
139 
140  /**
141  * Get corresponding weight of unmarked vertex of the polyhedron
142  * @attention Should only be called after hasUnmarkedVertex() returned true
143  * @return Weight vector
144  */
146  assert (!unmarked_vertices_.empty());
147  assert (curr_investigated_vertex_== nullptr);
148  curr_investigated_vertex_ = unmarked_vertices_.front();
149  unmarked_vertices_.pop_front();
150  assert (curr_investigated_vertex_ != nullptr);
151  return curr_investigated_vertex_->getWeight();
152  }
153 
154  /**
155  * Get weighted objective value of unmarked vertex
156  * @param untested_weight Corresponding weight of currently investigated vertex
157  * @return Weighted objective value of currently investigated vertex
158  */
160  assert (curr_investigated_vertex_ != nullptr);
161  assert (curr_investigated_vertex_->hasSameWeight(untested_weight));
162  return curr_investigated_vertex_->getCurrentWOV();
163  }
164 
165  /**
166  * Set status of given vertex to obsolete status
167  * @param v Weight space vertex
168  */
169  void WeightSpacePolyhedron::makeObsolete(WeightSpaceVertex *v) {
170  if (v != curr_investigated_vertex_) {
171  auto v_status = v->getStatus();
173  auto pos = std::find(begin(unmarked_vertices_),
174  end(unmarked_vertices_),
175  v);
176  if (pos == end(unmarked_vertices_)) {
177  v->print(std::cout, true);
178  throw std::runtime_error("Weight space vertex expected in Unmarked Vertex Container.\n");
179  }
180  unmarked_vertices_.erase(pos);
181  }
182  else if (v_status == WeightSpaceVertex::VertexStatus::marked) { // v must be weakly-non-dominated point
183  auto pos = std::find(begin(marked_and_special_vertices_),
184  end(marked_and_special_vertices_),
185  v);
186  if (pos == end(marked_and_special_vertices_)) {
187  v->print(std::cout, true);
188  throw std::runtime_error("Weight space vertex expected in Marked Vertex Container.\n");
189  }
190  marked_and_special_vertices_.erase(pos);
191  }
192  else {
193  throw std::runtime_error("Unexpected weight space vertex status.\n");
194  }
195  }
196  assert (std::find(obsolete_vertices_.cbegin(),
197  obsolete_vertices_.cend(),
198  v) == obsolete_vertices_.cend());
200  obsolete_vertices_.push_back(v);
201  }
202 
203  /**
204  * Indicates whether two weight space vertices are adjacent in weight space polyhedron
205  * @param v First vertex
206  * @param w Second vertex
207  * @return true if first vertex is adjacent to second vertex; false otherwise
208  * @todo Const qualification
209  */
211  auto inc_facets = FacetContainer {};
212  std::set_intersection(v->incident_facets_.cbegin(),
213  v->incident_facets_.cend(),
214  w->incident_facets_.cbegin(),
215  w->incident_facets_.cend(),
216  std::back_inserter(inc_facets),
218  return inc_facets.size() >= wsp_dimension_-1;
219  }
220 
221  /**
222  * Add vertex to corresponding partition (minus, zero, plus) with respect to the given outcome
223  * @param scip SCIP pointer
224  * @param vertex Weight space vertex
225  * @param outcome Outcome
226  * @param outcome_is_ray Indicates whether given outcome is a ray
227  * @param minus_vertices Container storing vertices in minus partition
228  * @param plus_vertices Container storing vertices in plus partition
229  * @param zero_vertices Container storing vertices in zero partition
230  */
231  void WeightSpacePolyhedron::addVertexToCorrespondingPartition(SCIP* scip,
232  WeightSpaceVertex* vertex,
233  const OutcomeType& outcome,
234  bool outcome_is_ray,
235  vector<WeightSpaceVertex*>& minus_vertices,
236  vector<WeightSpaceVertex*>& plus_vertices,
237  vector<WeightSpaceVertex*>& zero_vertices) const {
238  auto result = vertex->computeSlack(outcome, outcome_is_ray);
239 
240  if (SCIPisNegative(scip, result)) {
241  minus_vertices.push_back(vertex);
242  }
243  else if (SCIPisPositive(scip, result)) {
244  plus_vertices.push_back(vertex);
245  }
246  else {
247  assert(SCIPisZero(scip, result));
248  zero_vertices.push_back(vertex);
249  }
250  }
251 
252  /**
253  * Update 1-skeleton of weight space polyhedron
254  * @param scip SCIP pointer
255  * @param outcome New outcome yielding a new vertex in weight space polyhedron
256  * @param outcome_is_ray Indicates whether outcome corresponds to ray
257  */
258  void WeightSpacePolyhedron::updateWeightSpacePolyhedron(SCIP* scip,
259  const OutcomeType& outcome,
260  bool outcome_is_ray) {
261 
262  auto obs_nonobs_pairs = vector<pair<WeightSpaceVertex*, WeightSpaceVertex*>> {}; // pair: obsolete vertex , adjacent non-obsolete vertex
263  assert (SCIPisNegative(scip, curr_investigated_vertex_->computeSlack(outcome, outcome_is_ray)));
264  auto plus = vector<WeightSpaceVertex*> {};
265  auto minus = vector<WeightSpaceVertex*> {};
266  auto zero = vector<WeightSpaceVertex*> {};
267 
268  for (auto vertex : marked_and_special_vertices_) {
269  addVertexToCorrespondingPartition(scip,
270  vertex,
271  outcome,
272  outcome_is_ray,
273  minus,
274  plus,
275  zero);
276  }
277  for (auto vertex : unmarked_vertices_) {
278  addVertexToCorrespondingPartition(scip,
279  vertex,
280  outcome,
281  outcome_is_ray,
282  minus,
283  plus,
284  zero);
285  }
286  minus.push_back(curr_investigated_vertex_);
287 
288  for (const auto& non_obs : plus) {
289  for (const auto& obs : minus) {
290  if (areAdjacent(non_obs, obs)) {
291  obs_nonobs_pairs.push_back({obs, non_obs});
292  }
293  }
294  }
295 
296  auto new_facet = outcome_is_ray ? make_shared<const WeightSpaceFacet>(outcome, 0) :
297  make_shared<const WeightSpaceFacet>(outcome, 1);
298 
299  auto new_vertices = vector<WeightSpaceVertex*> {};
300  auto new_edges = vector< pair<WeightSpaceVertex*, WeightSpaceVertex*> > {}; // pair: new vertex, adjacent vertex
301  for (const auto& v_pair : obs_nonobs_pairs) { // create new vertices between obsolete and non-obsolete vertices
302  auto obs_vertex = v_pair.first;
303  auto non_obs_vertex = v_pair.second;
304  double obs_coeff = non_obs_vertex->computeSlack(outcome, outcome_is_ray);
305  double non_obs_coeff = obs_vertex->computeSlack(outcome, outcome_is_ray);
306  assert (SCIPisPositive(scip,obs_coeff));
307  assert (SCIPisNegative(scip, non_obs_coeff));
308  auto new_vertex = new WeightSpaceVertex(obs_coeff, non_obs_coeff,
309  obs_vertex, non_obs_vertex,
310  new_facet, wsp_dimension_);
311  unmarked_vertices_.push_back(new_vertex);
312  new_vertices.push_back(new_vertex);
313  new_edges.push_back({new_vertex, non_obs_vertex});
314  }
315 
316  for (auto vertex : minus) {
317  makeObsolete(vertex);
318  }
319  }
320 
321  /**
322  * Incorporate new outcome (yielding new vertex) into weight space polyhedron
323  * @param scip SCIP pointer
324  * @param used_weight Weight used to compute outcome
325  * @param outcome Newly computed outcome
326  * @param outcome_is_ray Indicates whether newly computed outcome is a ray
327  */
329  const WeightType& used_weight,
330  const OutcomeType& outcome,
331  bool outcome_is_ray) {
332  assert (curr_investigated_vertex_ != nullptr);
333  assert (curr_investigated_vertex_->hasSameWeight(used_weight));
334  updateWeightSpacePolyhedron(scip, outcome, outcome_is_ray);
335  resetCurrentInvestigatedVertex(); // requirement: call after updateWeightSpacePolyhedron;
336  }
337 
338  /**
339  * Incorporate weight not yielding new vertex into weight space polyhedron
340  * @param used_weight Used weight vector
341  */
343  assert (curr_investigated_vertex_ != nullptr);
344  assert (curr_investigated_vertex_->hasSameWeight(used_weight));
345  curr_investigated_vertex_->setStatus(WeightSpaceVertex::VertexStatus::marked);
346  marked_and_special_vertices_.push_back(curr_investigated_vertex_);
347  resetCurrentInvestigatedVertex();
348  }
349 
350  /**
351  * Print function for unmarked vertices
352  * @param os Output stream to write to
353  * @param printFacets Indicates whether corresponding facets should be printed
354  */
355  void WeightSpacePolyhedron::printUnmarkedVertices(ostream &os, bool printFacets) const {
356  printVertices(unmarked_vertices_, "UNMARKED VERTICES:", os, printFacets);
357  }
358 
359  /**
360  * Print function for marked vertices
361  * @param os Output stream to write to
362  * @param printFacets Indicates whether corresponding facets should be printed
363  */
364  void WeightSpacePolyhedron::printMarkedVertices(ostream &os, bool printFacets) const {
365  printVertices(marked_and_special_vertices_, "MARKED VERTICES:", os, printFacets);
366  }
367 
368  /**
369  * Print function for obsolete vertices
370  * @param os Output stream to write to
371  * @param printFacets Indicates whether corresponding facets should be printed
372  */
373  void WeightSpacePolyhedron::printObsoleteVertices(ostream &os, bool printFacets) const {
374  printVertices(obsolete_vertices_, "OBSOLETE VERTICES:", os, printFacets);
375  }
376 
377 
378 }
bool areAdjacent(const WeightSpaceVertex *v, const WeightSpaceVertex *w)
Class for element of v-representation.
std::vector< ValueType > WeightType
Type for weight vectors.
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real ValueType
Type for computed values.
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
ValueType getUntestedVertexWOV(const WeightType &untested_weight) const
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
bool isZeroSlackIndex(std::size_t index) const
C++ wrapper classes for SCIP.
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.
VertexStatus getStatus() const
void incorporateKnownOutcome(const WeightType &used_weight)
double computeSlack(const OutcomeType &outcome, bool outcome_is_ray) const
doubledescription::H_RepC H_RepC
abbreviation
Global helper functions.
std::vector< std::shared_ptr< const WeightSpaceFacet > > FacetContainer
Container for facets.
Double description method for transforming a polyhedron given via its h-representation into its v-rep...
void setStatus(VertexStatus status)
bool hasSameWeight(const WeightType &weight) const
Class representing a facet of the weight space polyhedron.
void printObsoleteVertices(std::ostream &os=std::cout, bool printFacets=false) const
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Class representing a vertex of the (partial) weight space polyhedron.
doubledescription::V_RepC V_RepC
abbreviation
void incorporateNewOutcome(SCIP *scip, const WeightType &used_weight, const OutcomeType &outcome, bool outcome_is_ray=false)
WeightSpacePolyhedron(std::size_t wsp_dimension, V_RepC v_rep, H_RepC h_rep)
void printUnmarkedVertices(std::ostream &os=std::cout, bool printFacets=false) const
void printMarkedVertices(std::ostream &os=std::cout, bool printFacets=false) const