# 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):

# Report Date:

## 1970-08-01

# Pagination or Media Count:

## 172.0

# 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 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

# Descriptors:

# Subject Categories:

- Theoretical Mathematics
- Operations Research