Accession Number : AD0691119

Title :   MIXED INTEGER PROGRAMMING: DISCRETIZATION AND THE GROUP THEORETIC APPROACH.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Wolsey,Laurence A.

Report Date : JUN 1969

Pagination or Media Count : 121

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, GROUPS(MATHEMATICS)), LINEAR PROGRAMMING, SCHEDULING, DECISION MAKING, ALGORITHMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE