MIXED INTEGER PROGRAMMING: DISCRETIZATION AND THE GROUP THEORETIC APPROACH.
MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER
Pagination or Media Count:
A new approach to the solution of mixed integer programming problems is developed, largely an extension of the group theoretic methods now being applied to all-integer problems. Discretization is used to replace any mixed integer programming problem by an equivalent integer programming problem. This permits the group theoretic approach of Gomory to be applied to such problems, resulting in a new asympototic classification of mixed integer problems into three types which somewhat reflect degrees of difficulty. Given this classification, new solution methods for certain problems within these classes are developed, based mainly on the concepts of basis search and relaxation. It is also shown how mixed integer problems in which the number of constraints exceeds the number of continuous variables, and a variety of special problems, such as the plant location problem, can be very simply replaced by integer problems. This makes possible the direct solution of these problems by the existing group theoretic integer programming algorithms. Author
- Operations Research