Scippy

SCIP

Solving Constraint Integer Programs

weight_space_polyhedron.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_polyhedron.h
17  * @brief Class representing the 1-skeleton of the weight space polyhedron
18  * @author Sebastian Schenker
19  *
20  */
21 
22 #ifndef POLYSCIP_SRC_WEIGHT_SPACE_POLYHEDRON_H_INCLUDED
23 #define POLYSCIP_SRC_WEIGHT_SPACE_POLYHEDRON_H_INCLUDED
24 
25 #include <cstddef>
26 #include <deque>
27 #include <list>
28 #include <iomanip> //std::set_precision
29 #include <iostream>
30 #include <iterator>
31 #include <map>
32 #include <memory> // std::shared_ptr
33 #include <ostream>
34 #include <string>
35 #include <tuple>
36 #include <unordered_map>
37 #include <utility> // std::pair
38 #include <vector>
39 
40 #include "objscip/objscip.h"
41 #include "polyscip_types.h"
42 #include "weight_space_facet.h"
44 
45 namespace polyscip {
46 
47  using V_RepT = doubledescription::V_RepT; ///< abbreviation
48  using V_RepC = doubledescription::V_RepC; ///< abbreviation
49  using H_RepC = doubledescription::H_RepC; ///< abbreviation
50  class WeightSpaceVertex;
51 
52  /**
53  * @class WeightSpacePolyhedron
54  * @brief Class representing the 1-skeleton of the weight space polyhedron
55  * @details The (partial) weight space polyhedron
56  * P = {(w,a) \\in W \\times R : w \\cdot y >= a \\forall y \\in Y'}
57  * where Y' is the set of non-dominated extreme points computed so far and
58  * W = {w \\in R^k: w_i >= 0, w_1 + ... + w_k = 1} is the set of non-negative normalized weights
59  */
61  public:
62  using FacetContainer = std::vector<std::shared_ptr<const WeightSpaceFacet>>; ///< Container for facets
63 
64  /**
65  * Default constructor
66  * @param wsp_dimension Dimension of the weight space polyhedron
67  * @param v_rep v-representation of the initial polyhedron
68  * @param h_rep h-representation of the initial polyhedron
69  */
70  explicit WeightSpacePolyhedron(std::size_t wsp_dimension,
71  V_RepC v_rep,
72  H_RepC h_rep);
73 
74  /**
75  * Destructor
76  */
78 
79  /**
80  * Indicates whether there is an unmarked vertex in the current polyhedron
81  * @return true if there is an unmarked vertex; false otherwise
82  */
83  bool hasUntestedWeight() const;
84 
85  /**
86  * Get corresponding weight of unmarked vertex of the polyhedron
87  * @attention Should only be called after hasUnmarkedVertex() returned true
88  * @return Weight vector
89  */
91 
92  /**
93  * Get weighted objective value of unmarked vertex
94  * @param untested_weight Corresponding weight of currently investigated vertex
95  * @return Weighted objective value of currently investigated vertex
96  */
97  ValueType getUntestedVertexWOV(const WeightType& untested_weight) const;
98 
99  /**
100  * Incorporate new outcome (yielding new vertex) into weight space polyhedron
101  * @param scip SCIP pointer
102  * @param used_weight Weight used to compute outcome
103  * @param outcome Newly computed outcome
104  * @param outcome_is_ray Indicates whether newly computed outcome is a ray
105  */
107  const WeightType& used_weight,
108  const OutcomeType& outcome,
109  bool outcome_is_ray = false);
110 
111  /**
112  * Incorporate weight not yielding new vertex into weight space polyhedron
113  * @param used_weight Used weight vector
114  */
115  void incorporateKnownOutcome(const WeightType& used_weight);
116 
117  /**
118  * Print function for unmarked vertices
119  * @param os Output stream to write to
120  * @param printFacets Indicates whether corresponding facets should be printed
121  */
122  void printUnmarkedVertices(std::ostream& os = std::cout,
123  bool printFacets = false) const;
124 
125  /**
126  * Print function for marked vertices
127  * @param os Output stream to write to
128  * @param printFacets Indicates whether corresponding facets should be printed
129  */
130  void printMarkedVertices(std::ostream& os = std::cout,
131  bool printFacets = false) const;
132 
133  /**
134  * Print function for obsolete vertices
135  * @param os Output stream to write to
136  * @param printFacets Indicates whether corresponding facets should be printed
137  */
138  void printObsoleteVertices(std::ostream& os = std::cout,
139  bool printFacets = false) const;
140 
141  /**
142  * Indicates whether two weight space vertices are adjacent in weight space polyhedron
143  * @param v First vertex
144  * @param w Second vertex
145  * @return true if first vertex is adjacent to second vertex; false otherwise
146  * @todo Const qualification
147  */
148  bool areAdjacent(const WeightSpaceVertex* v,
149  const WeightSpaceVertex* w);
150 
151  private:
152 
153  using MarkedVertexContainer = std::vector<WeightSpaceVertex*>; ///< Container for marked vertices @attention needs to support empty(), size(), valid iterators after erasing objects
154  using UnmarkedVertexContainer = std::list<WeightSpaceVertex*>; ///< Container for unmarked vertices
155  using ObsoleteVertexContainer = std::vector<WeightSpaceVertex*>; ///< Container for obsolete vertices
156 
157  /**
158  * Create initial weight space vertices and corresponding 1-skeleton of weight space polyhedron
159  * @param h_rep h-representation of initial weight space polyhedron
160  * @param v_rep v-representation of initial weight space polyhedron
161  */
162  void createInitialVerticesAndSkeleton(H_RepC h_rep,
163  V_RepC v_rep);
164 
165  /**
166  * Get incident facets
167  * @param v Corresponding vertex
168  * @param initial_facets Facets
169  * @return Incident facets of given vertex with respect to given facets
170  */
171  FacetContainer getIncidentFacets(const V_RepT& v,
172  const FacetContainer& initial_facets) const;
173 
174  /**
175  * Update 1-skeleton of weight space polyhedron
176  * @param scip SCIP pointer
177  * @param outcome New outcome yielding a new vertex in weight space polyhedron
178  * @param outcome_is_ray Indicates whether outcome corresponds to ray
179  */
180  void updateWeightSpacePolyhedron(SCIP* scip,
181  const OutcomeType& outcome,
182  bool outcome_is_ray);
183 
184  /**
185  * Nullify currently investigated vertex
186  */
187  void resetCurrentInvestigatedVertex() {
188  curr_investigated_vertex_ = nullptr;
189  }
190 
191  /**
192  * Add vertex to corresponding partition (minus, zero, plus) with respect to the given outcome
193  * @param scip SCIP pointer
194  * @param vertex Weight space vertex
195  * @param outcome Outcome
196  * @param outcome_is_ray Indicates whether given outcome is a ray
197  * @param minus_vertices Container storing vertices in minus partition
198  * @param plus_vertices Container storing vertices in plus partition
199  * @param zero_vertices Container storing vertices in zero partition
200  */
201  void addVertexToCorrespondingPartition(SCIP* scip,
202  WeightSpaceVertex* vertex,
203  const OutcomeType& outcome,
204  bool outcome_is_ray,
205  std::vector<WeightSpaceVertex*>& minus_vertices,
206  std::vector<WeightSpaceVertex*>& plus_vertices,
207  std::vector<WeightSpaceVertex*>& zero_vertices) const;
208 
209  /**
210  * Set status of given vertex to obsolete status
211  * @param v Weight space vertex
212  */
213  void makeObsolete(WeightSpaceVertex *v);
214 
215 
216  /**
217  * Print function for vertex container
218  * @tparam Container Container type
219  * @param container Container with elements to be printed
220  * @param description Description to be printed before elements
221  * @param os Output stream to write to
222  * @param printFacets Indicates whether corresponding facets should be printed
223  */
224  template <typename Container>
225  void printVertices(const Container& container,
226  std::string description,
227  std::ostream& os,
228  bool printFacets) const;
229 
230  std::size_t wsp_dimension_; ///< Corresponding dimension of weight space polyhedron
231 
232  MarkedVertexContainer marked_and_special_vertices_; ///< Marked weight space vertices
233  UnmarkedVertexContainer unmarked_vertices_; ///< Unmarked weight spaces vertices
234  ObsoleteVertexContainer obsolete_vertices_; ///< Obsolete weight space vertices
235  WeightSpaceVertex* curr_investigated_vertex_; ///< Weight space vertex currently investigated
236  };
237 
238 
239  template <typename Container>
240  void WeightSpacePolyhedron::printVertices(const Container& container,
241  std::string description,
242  std::ostream &os,
243  bool printFacets) const {
244  os << description << "\n";
245  for (const auto& elem : container) {
246  elem->print(os, printFacets);
247  os << "\n";
248  }
249  os << "\n";
250  }
251 
252 }
253 
254 #endif //POLYSCIP_SRC_WEIGHT_SPACE_POLYHEDRON_H_INCLUDED
bool areAdjacent(const WeightSpaceVertex *v, const WeightSpaceVertex *w)
Class for element of v-representation.
std::vector< ValueType > WeightType
Type for weight vectors.
SCIP_Real ValueType
Type for computed values.
std::vector< std::shared_ptr< V_RepT > > V_RepC
Container for v-representations.
ValueType getUntestedVertexWOV(const WeightType &untested_weight) const
std::vector< H_RepT > H_RepC
Container for h-representations.
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.
doubledescription::V_RepT V_RepT
abbreviation
void incorporateKnownOutcome(const WeightType &used_weight)
doubledescription::H_RepC H_RepC
abbreviation
Class representing the 1-skeleton of the weight space polyhedron.
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...
Class representing a facet of the weight space polyhedron.
void printObsoleteVertices(std::ostream &os=std::cout, bool printFacets=false) const
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