TY - JOUR
ID - 7915
TI - Modelling Decision Problems Via Birkhoff Polyhedra
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Gismondi, Stephen J.
AD - Department of Mathematics & Statistics, University of Guelph, Guelph, ON, CA. N1G 2W1
Y1 - 2013
PY - 2013
VL - 44
IS - 1
SP - 61
EP - 81
KW - Combinatorial optimization
KW - linear programming
DO - 10.22059/jac.2013.7915
N2 - A compact formulation of the set of tours neither in a graph nor its complement is presented and illustrates a general methodology proposed for constructing polyhedral models of decision problems based upon permutations, projection and lifting techniques. Directed Hamilton tours on n vertex graphs are interpreted as (n-1)- permutations. Sets of extrema of Birkhoff polyhedra are mapped to tours neither in a graph nor its complement and these sets are embedded into disjoint orthogonal spaces as the solution set of a compact formulation. An orthogonal projection of its solution set into the subspace spanned by the Birkhoff polytope is the convex hull of all tours neither in a graph nor its complement. Itâ€™s suggested that these techniques might be adaptable for application to linear programming models of network and path problems.
UR - https://jac.ut.ac.ir/article_7915.html
L1 - https://jac.ut.ac.ir/article_7915_3fb7c1065f20646ec7ca90750ff4a8c7.pdf
ER -