Scippy

SCIP

Solving Constraint Integer Programs

polyscip::WeightSpacePolyhedron Class Reference

Detailed Description

Class representing the 1-skeleton of the weight space polyhedron.

The (partial) weight space polyhedron P = {(w,a) \in W \times R : w \cdot y >= a \forall y \in Y'} where Y' is the set of non-dominated extreme points computed so far and W = {w \in R^k: w_i >= 0, w_1 + ... + w_k = 1} is the set of non-negative normalized weights

Definition at line 60 of file weight_space_polyhedron.h.

Class representing the 1-skeleton of the weight space polyhedron. More...

#include <weight_space_polyhedron.h>

Public Types

using FacetContainer = std::vector< std::shared_ptr< const WeightSpaceFacet > >
 Container for facets. More...
 

Public Member Functions

 WeightSpacePolyhedron (std::size_t wsp_dimension, V_RepC v_rep, H_RepC h_rep)
 
 ~WeightSpacePolyhedron ()
 
bool hasUntestedWeight () const
 
WeightType getUntestedWeight ()
 
ValueType getUntestedVertexWOV (const WeightType &untested_weight) const
 
void incorporateNewOutcome (SCIP *scip, const WeightType &used_weight, const OutcomeType &outcome, bool outcome_is_ray=false)
 
void incorporateKnownOutcome (const WeightType &used_weight)
 
void printUnmarkedVertices (std::ostream &os=std::cout, bool printFacets=false) const
 
void printMarkedVertices (std::ostream &os=std::cout, bool printFacets=false) const
 
void printObsoleteVertices (std::ostream &os=std::cout, bool printFacets=false) const
 
bool areAdjacent (const WeightSpaceVertex *v, const WeightSpaceVertex *w)
 

Member Typedef Documentation

◆ FacetContainer

using polyscip::WeightSpacePolyhedron::FacetContainer = std::vector<std::shared_ptr<const WeightSpaceFacet> >

Container for facets.

Definition at line 62 of file weight_space_polyhedron.h.

Constructor & Destructor Documentation

◆ WeightSpacePolyhedron()

polyscip::WeightSpacePolyhedron::WeightSpacePolyhedron ( std::size_t  wsp_dimension,
V_RepC  v_rep,
H_RepC  h_rep 
)
explicit

Default constructor

Parameters
wsp_dimensionDimension of the weight space polyhedron
v_repv-representation of the initial polyhedron
h_reph-representation of the initial polyhedron

Definition at line 62 of file weight_space_polyhedron.cpp.

References h, polyscip::doubledescription::V_RepT::isZeroSlackIndex(), polyscip::WeightSpaceVertex::marked, polyscip::WeightSpaceVertex::setStatus(), and polyscip::WeightSpaceVertex::special.

◆ ~WeightSpacePolyhedron()

polyscip::WeightSpacePolyhedron::~WeightSpacePolyhedron ( )

Destructor

Definition at line 122 of file weight_space_polyhedron.cpp.

Member Function Documentation

◆ hasUntestedWeight()

bool polyscip::WeightSpacePolyhedron::hasUntestedWeight ( ) const

Indicates whether there is an unmarked vertex in the current polyhedron

Returns
true if there is an unmarked vertex; false otherwise

Definition at line 136 of file weight_space_polyhedron.cpp.

◆ getUntestedWeight()

WeightType polyscip::WeightSpacePolyhedron::getUntestedWeight ( )

Get corresponding weight of unmarked vertex of the polyhedron

Attention
Should only be called after hasUnmarkedVertex() returned true
Returns
Weight vector

Definition at line 145 of file weight_space_polyhedron.cpp.

References polyscip::WeightSpaceVertex::getWeight().

◆ getUntestedVertexWOV()

ValueType polyscip::WeightSpacePolyhedron::getUntestedVertexWOV ( const WeightType untested_weight) const

Get weighted objective value of unmarked vertex

Parameters
untested_weightCorresponding weight of currently investigated vertex
Returns
Weighted objective value of currently investigated vertex

Definition at line 159 of file weight_space_polyhedron.cpp.

References polyscip::WeightSpaceVertex::getCurrentWOV(), polyscip::WeightSpaceVertex::getStatus(), polyscip::WeightSpaceVertex::hasSameWeight(), polyscip::WeightSpaceVertex::marked, polyscip::WeightSpaceVertex::obsolete, polyscip::WeightSpaceVertex::print(), polyscip::WeightSpaceVertex::setStatus(), and polyscip::WeightSpaceVertex::unmarked.

◆ incorporateNewOutcome()

void polyscip::WeightSpacePolyhedron::incorporateNewOutcome ( SCIP scip,
const WeightType used_weight,
const OutcomeType outcome,
bool  outcome_is_ray = false 
)

Incorporate new outcome (yielding new vertex) into weight space polyhedron

Parameters
scipSCIP pointer
used_weightWeight used to compute outcome
outcomeNewly computed outcome
outcome_is_rayIndicates whether newly computed outcome is a ray

Definition at line 328 of file weight_space_polyhedron.cpp.

References polyscip::WeightSpaceVertex::hasSameWeight().

◆ incorporateKnownOutcome()

void polyscip::WeightSpacePolyhedron::incorporateKnownOutcome ( const WeightType used_weight)

Incorporate weight not yielding new vertex into weight space polyhedron

Parameters
used_weightUsed weight vector

Definition at line 342 of file weight_space_polyhedron.cpp.

References polyscip::WeightSpaceVertex::hasSameWeight(), polyscip::WeightSpaceVertex::marked, and polyscip::WeightSpaceVertex::setStatus().

◆ printUnmarkedVertices()

void polyscip::WeightSpacePolyhedron::printUnmarkedVertices ( std::ostream &  os = std::cout,
bool  printFacets = false 
) const

Print function for unmarked vertices

Parameters
osOutput stream to write to
printFacetsIndicates whether corresponding facets should be printed

Definition at line 355 of file weight_space_polyhedron.cpp.

◆ printMarkedVertices()

void polyscip::WeightSpacePolyhedron::printMarkedVertices ( std::ostream &  os = std::cout,
bool  printFacets = false 
) const

Print function for marked vertices

Parameters
osOutput stream to write to
printFacetsIndicates whether corresponding facets should be printed

Definition at line 364 of file weight_space_polyhedron.cpp.

◆ printObsoleteVertices()

void polyscip::WeightSpacePolyhedron::printObsoleteVertices ( std::ostream &  os = std::cout,
bool  printFacets = false 
) const

Print function for obsolete vertices

Parameters
osOutput stream to write to
printFacetsIndicates whether corresponding facets should be printed

Definition at line 373 of file weight_space_polyhedron.cpp.

◆ areAdjacent()

bool polyscip::WeightSpacePolyhedron::areAdjacent ( const WeightSpaceVertex v,
const WeightSpaceVertex w 
)

Indicates whether two weight space vertices are adjacent in weight space polyhedron

Parameters
vFirst vertex
wSecond vertex
Returns
true if first vertex is adjacent to second vertex; false otherwise

Indicates whether two weight space vertices are adjacent in weight space polyhedron

Parameters
vFirst vertex
wSecond vertex
Returns
true if first vertex is adjacent to second vertex; false otherwise

Definition at line 210 of file weight_space_polyhedron.cpp.

References polyscip::WeightSpaceVertex::computeSlack(), SCIPisNegative(), SCIPisPositive(), and SCIPisZero().

Referenced by polyscip::WeightSpaceVertex::setStatus().