
Accession Number : AD0712070
Title : INTEGRAL CONVEX POLYHEDRA AND AN APPROACH TO INTEGRALIZATION.
Descriptive Note : Doctoral thesis,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Personal Author(s) : Edelberg,Murray
Report Date : AUG 1970
Pagination or Media Count : 172
Abstract : 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 nonnegative orthant of ndimensional 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 numbertheoretic method for integralizing twodimensional 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)
Descriptors : (*LINEAR PROGRAMMING, CONVEX SETS), COMBINATORIAL ANALYSIS, MATRICES(MATHEMATICS), SET THEORY, VECTOR SPACES, OPTIMIZATION, GROUPS(MATHEMATICS), MINIMAX TECHNIQUE, BOUNDARY VALUE PROBLEMS, ALGORITHMS, THESES
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE