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