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.
Gismondi,S J . (2013). Modelling Decision Problems Via Birkhoff Polyhedra. Journal of Algorithms and Computation, 44(1), 61-81. doi: 10.22059/jac.2013.7915
MLA
Gismondi,S J . "Modelling Decision Problems Via Birkhoff Polyhedra", Journal of Algorithms and Computation, 44, 1, 2013, 61-81. doi: 10.22059/jac.2013.7915
HARVARD
Gismondi S J. (2013). 'Modelling Decision Problems Via Birkhoff Polyhedra', Journal of Algorithms and Computation, 44(1), pp. 61-81. doi: 10.22059/jac.2013.7915
CHICAGO
S J Gismondi, "Modelling Decision Problems Via Birkhoff Polyhedra," Journal of Algorithms and Computation, 44 1 (2013): 61-81, doi: 10.22059/jac.2013.7915
VANCOUVER
Gismondi S J. Modelling Decision Problems Via Birkhoff Polyhedra. J. Algo. Comp.. 2013;44(1):61-81. doi: 10.22059/jac.2013.7915
