%0 Journal Article
%T Modelling Decision Problems Via Birkhoff Polyhedra
%J Journal of Algorithms and Computation
%I University of Tehran
%Z 2476-2776
%A Gismondi, Stephen J.
%D 2013
%\ 11/01/2013
%V 44
%N 1
%P 61-81
%! Modelling Decision Problems Via Birkhoff Polyhedra
%K Combinatorial optimization
%K linear programming
%R 10.22059/jac.2013.7915
%X 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.
%U https://jac.ut.ac.ir/article_7915_3fb7c1065f20646ec7ca90750ff4a8c7.pdf