Modelling Decision Problems Via Birkhoff Polyhedra

	Modelling Decision Problems Via Birkhoff Polyhedra
Journal of Algorithms and Computation
مقاله 5، دوره 44، شماره 1، اسفند 2013، صفحه 61-81 اصل مقاله (1.68 M)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2013.7915
نویسنده
Stephen J. Gismondi^*
Department of Mathematics & Statistics, University of Guelph, Guelph, ON, CA. N1G 2W1
چکیده
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.
کلیدواژه‌ها
Combinatorial optimization؛ linear programming

آمار تعداد مشاهده مقاله: 1,988 تعداد دریافت فایل اصل مقاله: 1,657

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب