University of TehranJournal of Algorithms and Computation2476-277644120131101Modelling Decision Problems Via Birkhoff Polyhedra6181791510.22059/jac.2013.7915ENStephen J. GismondiDepartment of Mathematics & Statistics, University of Guelph, Guelph, ON, CA. N1G 2W1Journal Article20130126A 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.https://jac.ut.ac.ir/article_7915_3fb7c1065f20646ec7ca90750ff4a8c7.pdf