Scippy

SCIP

Solving Constraint Integer Programs

double_description_method.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 double_description_method.cpp
17  * @brief Implements the double description method for transforming a polyhedron given
18  * via its h-representation into its v-representation
19  * @author Sebastian Schenker
20  *
21  */
22 
24 
25 #include <algorithm>
26 #include <numeric>
27 #include <bitset>
28 #include <cmath> //std::fabs
29 #include <functional>
30 #include <iterator>
31 #include <memory>
32 #include <set>
33 #include <tuple>
34 #include <utility>
35 #include <vector>
36 
37 #include "global_functions.h"
38 #include "objscip/objscip.h"
39 #include "polyscip_types.h"
40 #include "PolySCIPConfig.h"
41 
42 using std::make_shared;
43 using std::size_t;
44 using std::vector;
45 
46 namespace polyscip {
47 
48  namespace doubledescription {
49 
50  /**
51  * Constructor
52  * @param scip SCIP pointer
53  * @param weight Corresponding weight for the constructed vertex
54  * @param wov Corresponding weighted objective value for the constructed vertex
55  * @param h_rep Current h-representation
56  */
57  V_RepT::V_RepT(SCIP* scip, WeightType&& weight, ValueType&& wov, const H_RepC& h_rep)
58  : weight_(weight),
59  wov_(wov),
60  min_infeas_ind_(false, 0)
61  {
62  if (shouldNormalize(kNormalizingThreshold))
63  normalize(kNormalizingThreshold);
64 
65  setSlacksAndMinInfeasInd(scip, h_rep);
66  }
67 
68  /**
69  * Constructor
70  * @param scip SCIP pointer
71  * @param plus
72  * @param minus
73  * @param index_of_ineq
74  * @param h_rep
75  */
77  const V_RepT& plus,
78  const V_RepT& minus,
79  std::size_t index_of_ineq,
80  const H_RepC& h_rep)
81  : min_infeas_ind_(false, 0)
82  {
83  auto m_coeff = plus.getSlack(index_of_ineq);
84  auto p_coeff = minus.getSlack(index_of_ineq);
85  assert (SCIPisPositive(scip, m_coeff));
86  assert (SCIPisNegative(scip, p_coeff));
87 
88  std::transform(minus.weight_.cbegin(), minus.weight_.cend(),
89  plus.weight_.cbegin(), std::back_inserter(weight_),
90  [m_coeff, p_coeff](ValueType m_val, ValueType p_val) {
91  return m_coeff * m_val - p_coeff * p_val;
92  });
93  wov_ = m_coeff*minus.wov_ - p_coeff*plus.wov_; // return m_coeff * ray_minus - p_coeff * ray_plus
94 
95  if (shouldNormalize(kNormalizingThreshold))
96  normalize(kNormalizingThreshold);
97 
98  setSlacksAndMinInfeasInd(scip, h_rep);
99  }
100 
101  /**
102  * Equal operator
103  * @param rhs v-representation object to compare with
104  * @return true if objects are considered equal; otherwise false
105  */
106  bool V_RepT::operator==(const V_RepT& rhs) const {
107  return std::tie(weight_, wov_) == std::tie(rhs.weight_, rhs.wov_);
108  }
109 
110  /**
111  * Not equal operator
112  * @param rhs v-representation object to compare with
113  * @return true if objects are considered not equal; otherwise false
114  */
115  bool V_RepT::operator!=(const V_RepT& rhs) const {
116  return !(operator==(rhs));
117  }
118 
119  /**
120  * Get slack value
121  * @param index Corresponding index to get slack for
122  * @return Slack value
123  */
124  ValueType V_RepT::getSlack(std::size_t index) const {
125  assert (inds_to_slacks_.count(index) != 0);
126  return inds_to_slacks_.at(index);
127  }
128 
129  /**
130  * Get minimal infeasibility index
131  * @return minimal infeasibility index
132  */
133  size_t V_RepT::getMinInfeasIndex() const {
134  assert (min_infeas_ind_.first);
135  return min_infeas_ind_.second;
136  }
137 
138  /**
139  * Indicates whether given index is zero index
140  * @param index Index to check
141  * @return true if index is zero index; false otherwise
142  */
143  bool V_RepT::isZeroSlackIndex(size_t index) const {
144  return zero_slacks_.test(index);
145  }
146 
147  /**
148  * Indicates whether corresponding weight is neither unit vector nor zero vector
149  * @return true if weight is neither unit vector nor zero vector; false otherwise
150  */
152  return (std::count_if(weight_.cbegin(), weight_.cend(), [](const ValueType& val){return val != 0.;}) > 1);
153  }
154 
155 
156  /**
157  * Set slack and minimal infeasibility index
158  * @param scip SCIP pointer
159  * @param h_rep h-representation
160  */
161  void V_RepT::setSlacksAndMinInfeasInd(SCIP* scip, const H_RepC& h_rep) {
162  for (size_t i=0; i<h_rep.size(); ++i) {
163  auto result = std::inner_product(weight_.cbegin(), weight_.cend(),
164  h_rep[i].first.cbegin(), -(h_rep[i].second * wov_));
165 
166  inds_to_slacks_.emplace(i, result);
167  if (SCIPisZero(scip, result)) {
168  inds_to_slacks_[i] = 0.;
169  zero_slacks_.set(i, 1);
170  }
171  else if (SCIPisNegative(scip, result) && !min_infeas_ind_.first) {
172  min_infeas_ind_.first = true;
173  min_infeas_ind_.second = i;
174  }
175  }
176  if (!min_infeas_ind_.first) {
177  min_infeas_ind_.first = true;
178  min_infeas_ind_.second = h_rep.size();
179  }
180  }
181 
182  /**
183  * Indicates whether corresponding weight should be normalized
184  * @param threshold Normalizing threshold
185  * @return true if weight should be normalized; false otherwise
186  */
187  bool V_RepT::shouldNormalize(double threshold) const {
188  if (std::fabs(wov_) > threshold)
189  return true;
190  else if (std::any_of(weight_.cbegin(), weight_.cend(), [threshold](ValueType w){return w > threshold;}))
191  return true;
192  return false;
193  }
194 
195 
196  /**
197  * Normalizing weight function
198  * @param normalizing_val Value by which weights are normalized
199  */
200  void V_RepT::normalize(double normalizing_val) {
201  std::transform(begin(weight_), end(weight_), begin(weight_),
202  [normalizing_val](const ValueType &val) { return val / normalizing_val; });
203  wov_ /= normalizing_val;
204  }
205 
206  /**
207  * Print function
208  * @param os Output stream to print to
209  * @param withIncidentFacets Boolean indicating whether incident facets should also be printed
210  * @param h_rep
211  */
212  void V_RepT::print(std::ostream& os, bool withIncidentFacets, const H_RepC& h_rep) const {
213  global::print(weight_, "Weight = [", "]", os);
214  os << " Coeff = " << wov_ << "\n";
215  os << "MinInfeasIndex = " << min_infeas_ind_.second << "\n";
216  if (withIncidentFacets) {
217  os << "Facets: \n";
218  for (size_t i=0; i<kMaxInitialHrepSize; ++i) {
219  if (zero_slacks_[i]) {
220  global::print(h_rep[i].first, "", "", os);
221  os << " " << h_rep[i].second << "\n";
222  }
223  }
224  os << "\n";
225  }
226  }
227 
228 
229  /**
230  * Indicates whether zero indices are subset of given zero indices
231  * @param common_zero_inds Zero indices
232  * @return true if zero indices are subset of given common_zero_inds
233  */
234  bool V_RepT::hasZeroIndsSuperSet(const std::bitset<kMaxInitialHrepSize>& common_zero_inds) const {
235  return (common_zero_inds & zero_slacks_).count() >= common_zero_inds.count();
236  }
237 
238 
239  /**
240  * Constructor
241  * @param scip SCIP pointer
242  * @param no_all_obj Number of objectives
243  * @param bounded Bounded results
244  * @param unbounded Unbounded results
245  */
247  size_t no_all_objs,
248  const ResultContainer& bounded_results,
249  const ResultContainer& unbounded_results)
250  : scip_(scip),
251  outcome_dimension_(no_all_objs),
252  current_hrep_index_(no_all_objs),
253  adj_pairs_(no_all_objs+bounded_results.size()+unbounded_results.size(), AdjPairContainer{})
254  {
255  /* build up h-representation for which v-representation is to be found */
256  assert (!bounded_results.empty());
257 
258  for (size_t i=0; i<outcome_dimension_; ++i) {
259  auto unit_vec = OutcomeType(outcome_dimension_, 0.);
260  unit_vec[i] = 1.;
261  h_rep_.emplace_back(std::move(unit_vec), 0.); // add constraint: e_i 0 >= 0 with e_i being i-th unit vector
262  }
263 
264  for (const auto &bd : bounded_results) {
265  h_rep_.emplace_back(bd.second, 1.); // add constraint; bd_outcome -1 >= 0
266  }
267  for (const auto &unbd : unbounded_results) {
268  h_rep_.emplace_back(unbd.second, 0.); // add constraint; unbd_outcome 0 >= 0
269  }
270  }
271 
272  /**
273  * Check for minimal infeasibility condition
274  * @param r1 First element
275  * @param r2 Second element
276  * @return Tuple
277  */
278  std::tuple<bool, DoubleDescriptionMethod::VarOrder, size_t> DoubleDescriptionMethod::minInfeasCondition(const V_RepT& r1, const V_RepT& r2) const {
279  auto minInfeasInd1 = r1.getMinInfeasIndex();
280  auto minInfeasInd2 = r2.getMinInfeasIndex();
281  if (minInfeasInd1 < minInfeasInd2 && !r2.isZeroSlackIndex(minInfeasInd1)) {
282  assert (current_hrep_index_ < minInfeasInd1 && minInfeasInd1 < h_rep_.size());
283  return std::make_tuple(true, VarOrder::change_var_order, minInfeasInd1);
284  }
285  else if (minInfeasInd2 < minInfeasInd1 && !r1.isZeroSlackIndex(minInfeasInd2)) {
286  assert (current_hrep_index_ < minInfeasInd2 && minInfeasInd2 < h_rep_.size());
287  return std::make_tuple(true, VarOrder::keep_var_order, minInfeasInd2);
288  }
289  else {
290  return std::make_tuple(false, VarOrder::keep_var_order, 0);
291  }
292  }
293 
294  /**
295  * Detailed description of algorithm can be found on page 13 in "Double Description Method Revisited"
296  * @param r1
297  * @param r2
298  * @param k
299  * @param i
300  * @param v_rep
301  * @param with_adjacency_test
302  */
303  void DoubleDescriptionMethod::conditionalStoreEdge(const V_RepT& plus,
304  const V_RepT& minus,
305  size_t k,
306  size_t i,
307  const V_RepC& v_rep,
308  bool with_adjacency_test) {
309  assert (i <= k);
310  for (auto index=i+1; index<k; ++index) {
311  if (plus.isZeroSlackIndex(index) && minus.isZeroSlackIndex(index))
312  return;
313  }
314  if (!with_adjacency_test || rayPairIsAdjacent(plus, minus, v_rep)) {
315  adj_pairs_.at(k).push_back({std::cref(plus), std::cref(minus)});
316  }
317  }
318 
319  /**
320  * Print function
321  * @param os Output stream to write to
322  * @param withIncidentFacets Indicates whether corresponding facets should be printed
323  */
324  void DoubleDescriptionMethod::printVRep(std::ostream &os, bool withIncidentFacets) const {
325  for (const auto& v : v_rep_)
326  v->print(os, withIncidentFacets, h_rep_);
327  }
328 
329  /**
330  * Standard double description algorithm
331  */
333  auto current_v_rep = computeInitialVRep();
334  ++current_hrep_index_;
335  while (current_hrep_index_ < h_rep_.size()) {
336  current_v_rep = extendVRep(std::move(current_v_rep));
337  ++current_hrep_index_;
338  }
339  v_rep_ = current_v_rep;
340  }
341 
342  /**
343  * Applies infeasibility condition
344  * @param r1
345  * @param r2
346  * @param current_v_rep
347  * @param index
348  * @param with_adjacency_test
349  */
350  void DoubleDescriptionMethod::applyInfeasCondition(const V_RepT& r1,
351  const V_RepT& r2,
352  const V_RepC& v_rep,
353  size_t index,
354  bool with_adjacency_test
355  ) {
356  auto infeasTuple = minInfeasCondition(r1, r2);
357  if (std::get<0>(infeasTuple)) {
358  if (std::get<1>(infeasTuple) == VarOrder::keep_var_order){
359  conditionalStoreEdge(r1, r2, std::get<2>(infeasTuple), index, v_rep, with_adjacency_test);
360  }
361  else {
362  conditionalStoreEdge(r2, r1, std::get<2>(infeasTuple), index, v_rep, with_adjacency_test);
363  }
364  }
365  }
366 
367  /**
368  * Variation 1 of double description algorithm
369  */
371  auto current_v_rep = computeInitialVRep();
372 
373  for (auto r1_it=begin(current_v_rep); r1_it!=std::prev(end(current_v_rep)); ++r1_it) {
374  for (auto r2_it=std::next(r1_it); r2_it!=end(current_v_rep); ++r2_it) {
375  const V_RepT& r1 = r1_it->operator*();
376  const V_RepT& r2 = r2_it->operator*();
377  applyInfeasCondition(r1, r2, current_v_rep, current_hrep_index_, true);
378  }
379  }
380 
381  ++current_hrep_index_;
382  while (current_hrep_index_ < h_rep_.size()) {
383  current_v_rep = extendVRep_Var1(std::move(current_v_rep));
384  ++current_hrep_index_;
385  }
386  v_rep_ = current_v_rep;
387  }
388 
389 
390  /**
391  * Incorporate next hyperplane into v-representation; Variation1 algorithm
392  * @param current_v_rep Current v-representation
393  * @return Extended v-representation
394  */
395  V_RepC DoubleDescriptionMethod::extendVRep_Var1(V_RepC&& current_v_rep) {
396 
397  auto extended_v_rep = V_RepC{};
398  const H_RepT& h = h_rep_[current_hrep_index_];
399 
400  for (const auto& v : current_v_rep) { // partition current v-representation
401  auto result = std::inner_product(v->weight_.cbegin(), v->weight_.cend(),
402  h.first.cbegin(), -(v->wov_ * h.second));
403  if (SCIPisZero(scip_, result)) {
404  extended_v_rep.push_back(v); // element will also be in extended v-representation
405  }
406  else if (SCIPisPositive(scip_, result)) {
407  extended_v_rep.push_back(v);
408  }
409  }
410 
411  for (auto p : adj_pairs_[current_hrep_index_]) {
412  auto new_ray = make_shared<V_RepT>(scip_, p.first.get(), p.second.get(), current_hrep_index_, h_rep_);
413  extended_v_rep.push_back(new_ray);
414  applyInfeasCondition(*new_ray, p.first.get(), extended_v_rep, current_hrep_index_, false);
415  }
416 
417  for (auto r1_it=extended_v_rep.cbegin(); r1_it!=std::prev(extended_v_rep.cend()); ++r1_it) {
418  for (auto r2_it=std::next(r1_it); r2_it!=extended_v_rep.cend(); ++r2_it) {
419  const V_RepT& r1 = r1_it->operator*();
420  const V_RepT& r2 = r2_it->operator*();
421  if (r1.isZeroSlackIndex(current_hrep_index_) && r2.isZeroSlackIndex(current_hrep_index_)) {
422  applyInfeasCondition(r1, r2, extended_v_rep, current_hrep_index_, true);
423  }
424  }
425  }
426 
427  return extended_v_rep;
428  }
429 
430  /**
431  * Incorporate next hyperplane into v-representation; standard algorithm
432  * @param cur_v_rep Current v-representation
433  * @return Extended v-representation
434  */
435  V_RepC DoubleDescriptionMethod::extendVRep(V_RepC&& cur_v_rep) {
436  auto extended_v_rep = V_RepC{};
437  auto plus = V_RepC{};
438  auto minus = V_RepC{};
439  const H_RepT& hrep = h_rep_[current_hrep_index_];
440 
441  for (const auto& v : cur_v_rep) {
442  auto result = std::inner_product(v->weight_.cbegin(), v->weight_.cend(),
443  hrep.first.cbegin(), -(v->wov_ * hrep.second));
444  if (SCIPisNegative(scip_, result)) {
445  minus.push_back(v);
446  }
447  else if (SCIPisZero(scip_, result)) {
448  extended_v_rep.push_back(std::move(v)); // element will also be in extended v-representation
449  }
450  else {
451  assert(SCIPisPositive(scip_, result));
452  plus.push_back(v);
453  }
454  }
455 
456  auto adj_pairs = computeAdjacentPairs(plus, minus, cur_v_rep);
457  for (const auto& p : adj_pairs)
458  extended_v_rep.push_back(make_shared<V_RepT>(scip_, p.first.get(), p.second.get(), current_hrep_index_, h_rep_));
459 
460  for (const auto& p : plus)
461  extended_v_rep.push_back(std::move(p));
462 
463  return extended_v_rep;
464  }
465 
466 
467  /**
468  * Compute adjacent pairs of elements in v-representation
469  * @param plus Elements in plus partition
470  * @param minus Elements in minus partition
471  * @param current_v_rep Current v-representation
472  * @return Adjacent elements
473  */
474  DoubleDescriptionMethod::AdjPairContainer DoubleDescriptionMethod::computeAdjacentPairs(const V_RepC& plus,
475  const V_RepC& minus,
476  const V_RepC& current_v_rep) const {
477  auto adj_pairs = AdjPairContainer{};
478  for (const auto& p_ptr : plus) {
479  for (const auto& m_ptr : minus) {
480  assert (*p_ptr != *m_ptr);
481  if (rayPairIsAdjacent(*p_ptr, *m_ptr, current_v_rep))
482  adj_pairs.push_back({std::cref(*p_ptr), std::cref(*m_ptr)});
483  }
484  }
485  return adj_pairs;
486  }
487 
488  /**
489  * Computes the intersection of zero indices for two given v-representation elements
490  * @param v First element
491  * @param w Second element
492  * @return bitset with ones indicating common zero slacks
493  */
494  std::bitset<V_RepT::kMaxInitialHrepSize> DoubleDescriptionMethod::getCommonZeroSlackIndices(const V_RepT &v,
495  const V_RepT &w) const {
496  return v.zero_slacks_ & w.zero_slacks_;
497  }
498 
499 
500  /**
501  * Indicates whether given elements are adjacent
502  * @param ray1
503  * @param ray2
504  * @param v_rep
505  * @return True if r1 and r2 are adjancent; false otherwise
506  */
507  bool DoubleDescriptionMethod::rayPairIsAdjacent(const V_RepT& ray1,
508  const V_RepT& ray2,
509  const V_RepC& v_rep) const {
510  auto common_zero_inds = getCommonZeroSlackIndices(ray1, ray2);
511 
512  for (const auto& ray_sptr : v_rep) {
513  if (ray1 == *ray_sptr || ray2 == *ray_sptr) {
514  continue;
515  }
516  else if (ray_sptr->hasZeroIndsSuperSet(common_zero_inds)) {
517  /* check whether current_rep[i] is multiple of current_rep[index1] or current_rep[index2] */
518  if (!isMultiple(*ray_sptr, ray1) && !isMultiple(*ray_sptr, ray2))
519  return false;
520  }
521  }
522  return true;
523  }
524 
525 
526  /**
527  * Indicates whether first element is multiple of second element
528  * @param v First v-representation element
529  * @param w Second v-representation element
530  * @return true if v is multiple of w; false otherwise
531  * @todo Rewrite in less complicated fashion
532  */
533  bool DoubleDescriptionMethod::isMultiple(const V_RepT& v, const V_RepT& w) const {
534  assert (v.weight_.size() == w.weight_.size());
535  auto scip_ptr = scip_; // needed for lambda functions
536  if (SCIPisEQ(scip_, v.wov_, w.wov_)) { //v.wov = w.wov
537  auto mismatch_pair = std::mismatch(begin(v.weight_),
538  end(v.weight_),
539  begin(w.weight_),
540  [scip_ptr](ValueType v_val, ValueType w_val)
541  {return SCIPisEQ(scip_ptr, v_val, w_val);});
542  if (mismatch_pair.first == end(v.weight_)) {// v.weight = w.weight
543  return true; // multiple is 1
544  }
545  else { // v.weight != w.weight
546  if (SCIPisZero(scip_, v.wov_)) { // v.wov=0 && w.wov=0
547  auto v_val = *mismatch_pair.first;
548  auto w_val = *mismatch_pair.second;
549  if (SCIPisZero(scip_, v_val) || SCIPisZero(scip_, w_val)) { // implies v_val!=0 || w_val!=0
550  return false; // v cannot be multiple of w
551  }
552  else { // v.wov=w.wov=0 && v_val!=w_val && v_val!=0 && w_val!=0
553  auto multiple = w_val / v_val; // multiple * v_val = w_val
554  return weightIsMultiple(scip_ptr, multiple, v, w);
555  }
556  }
557  else { // v.wov = w.wov && v.wov!=0 && v.weight!=w.weight
558  return false;
559  }
560  }
561  }
562  else { // v.wov != w.wov_
563  if (SCIPisZero(scip_, v.wov_)) { // -> w.wov!=0 implying v == k*w only if k=0 && v=0 implying something is wrong since v.weight should != 0
564  assert (!std::all_of(begin(v.weight_), end(v.weight_), [scip_ptr](ValueType val){return SCIPisZero(scip_ptr,val);})); // assert (v.weight!=0)
565  return false;
566  }
567  else if (SCIPisZero(scip_, w.wov_)) { // -> v.wov!=0 implying w == k*v only if k=0 && w=0 implying something is wrong since w.weight should != 0
568  assert (!std::all_of(begin(w.weight_), end(w.weight_), [scip_ptr](ValueType val){return SCIPisZero(scip_ptr,val);})); // assert (w.weight!=0)
569  return false;
570  }
571  else { // v.wov!=w.wov && v.wov!=0 && w.wov!=0
572  auto multiple = w.wov_ / v.wov_; // multiple * v.wov = w.wov
573  return weightIsMultiple(scip_ptr, multiple, v, w);
574  }
575  }
576  }
577 
578  /**
579  * Indicates whether weight of first element is a multiple (with value v_multiple) of weight of second element
580  * @param scip SCIP pointer
581  * @param v_multiple Value
582  * @param v First element
583  * @param w Second element
584  * @return true if weight of first element is a v_multiple of weight of second element; false otherwise
585  */
586  bool DoubleDescriptionMethod::weightIsMultiple(SCIP* scip, double v_multiple, const V_RepT& v, const V_RepT& w) const {
587  auto mismatch_weight = std::mismatch(begin(v.weight_),
588  end(v.weight_),
589  begin(w.weight_),
590  [scip, v_multiple](ValueType v_val, ValueType w_val)
591  {return SCIPisEQ(scip, v_multiple * v_val, w_val);});
592  return mismatch_weight.first == end(v.weight_);
593  }
594 
595 
596  /**
597  * Computes initial v-representation of following h-representation:
598  * 1) bounded \\cdot (w_1,...,w_k) -a >= 0
599  * 2) w_1 >= 0
600  * ...
601  * k+1) w_k >= 0
602  * where (w_1,...,w_k) is a weight vector
603  * @return Initial v-representation
604  */
605  V_RepC DoubleDescriptionMethod::computeInitialVRep() const {
606  // create initial v_rep
607  auto init_v_rep = V_RepC{};
608  init_v_rep.push_back(make_shared<V_RepT>(scip_, WeightType(outcome_dimension_, 0.), -1., h_rep_)); // add v_rep: 0 0 ... 0 -1
609  for (size_t i=0; i<current_hrep_index_; ++i) {
610  auto unit_vec = WeightType(outcome_dimension_, 0.);
611  unit_vec[i] = 1.;
612  auto wov = h_rep_[current_hrep_index_].first.at(i);
613  init_v_rep.push_back(make_shared<V_RepT>(scip_, std::move(unit_vec), std::move(wov), h_rep_)); // add v_rep: e_i, vrep_wov with e_i being i-th unit vector
614  }
615  return init_v_rep;
616  }
617 
618  }
619 
620 }
Some preprocessor directives.
bool hasZeroIndsSuperSet(const std::bitset< kMaxInitialHrepSize > &common_zero_inds) const
Class for element of v-representation.
std::vector< ValueType > WeightType
Type for weight vectors.
std::vector< AdjPair > AdjPairContainer
Container for adjacent pairs.
V_RepT(SCIP *scip, WeightType &&weight, ValueType &&wov, const H_RepC &h_rep)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real ValueType
Type for computed values.
void print(std::ostream &os, bool withIncidentFacets, const H_RepC &h_rep) const
static constexpr std::size_t kMaxInitialHrepSize
Maximal initial size of h-representation.
void printVRep(std::ostream &os=std::cout, bool withIncidentFacets=false) const
std::vector< std::shared_ptr< V_RepT > > V_RepC
Container for v-representations.
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
std::vector< H_RepT > H_RepC
Container for h-representations.
General types used for PolySCIP.
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
std::vector< ValueType > OutcomeType
Type for points, rays in objective space.
SCIP_VAR * w
Definition: circlepacking.c:58
bool isZeroSlackIndex(std::size_t index) const
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
C++ wrapper classes for SCIP.
SCIPInterval fabs(const SCIPInterval &x)
SCIP_VAR * h
Definition: circlepacking.c:59
DoubleDescriptionMethod(SCIP *scip, std::size_t no_all_obj, const ResultContainer &bounded, const ResultContainer &unbounded)
std::vector< Result > ResultContainer
Container type for results.
Global helper functions.
std::pair< OutcomeType, ValueType > H_RepT
Type for element of h-representation.
Double description method for transforming a polyhedron given via its h-representation into its v-rep...
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)