MIXED INTEGER PROGRAMMING: DISCRETIZATION AND THE GROUP THEORETIC APPROACH.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1969
- Accession Number
- AD0691119
Entities
People
- Laurence A. Wolsey
Organizations
- Massachusetts Institute of Technology