Integral convex polyhedra and an approach to integralization
Project MAC, Massachusetts Institute of Technology, 1970 - Linear programming - 170 pages
Many combinatorial optimization problems may be formulated as integer linear programming problems, that is, problems of the form: given a convex polyhedron P contained in the non-negative orthant of n-dimensional space, find an integer point in P which maximizes (or minimizes) a given linear objective function. Well known linear programming methods would suffice to solve such a problem if: (1) P is an integral convex polyhedron, or (2) P is transformed into the integral convex polyhedron that is the convex hull of the set of integer points in P, a process which is called integralization. This thesis provides some theoretical results concerning integral convex polyhedra and the process of integralization. Necessary and sufficient conditions for a convex polyhedron P to have the integral property are derived in terms of the system of linear inequalities defining P. A number-theoretic method for integralizing two-dimensional convex polyhedra is developed which makes use of a generalization of the division theorem for integers. The method is applicable to a restricted class of higher dimensional polyhedra as well. (Author).
What people are saying - Write a review
We haven't found any reviews in the usual places.
THE INTEGRAL PROPERTY IN CONVEX POLYHEDRA
THE TOTALLY INTEGRAL PROPERTY IN CONVEX POLYHEDRA
5 other sections not shown
2,2)-corner polyhedron atoms of M(A boundary point Chapter combination of integer combinatorial optimization contains convex combination convex hull convex set convex subset corner of I(P Corollary 2-4 defined by Ax defines an integral denote division theorem equation Euclidean algorithm finite number fixed real flat subsets half-flat half-space I(tt independent set inequalities defining integer combination integer linear programming integer m-vector integer points integer solution integral convex polyhedron integral k-flat intersection irreducible faces isomorphism linear programming polyhedra linear programming problem linearly independent M+(W matrix of rank minimal face n-dimensional n,k)-polyhedron normal vectors objective inequality orthant partially ordered set point of I(P polyhedron defined PROJECT MAC Proof real numbers real points sequence set of integer slack vector submatrix subset of Rn supporting corner system of inequalities Theorem 2-1 totally integral convex totally integral property two-dimensional vectors and vertices vectors of I(P vertex of I(P