Accession Number : AD0749896

Title :   A Constraint-Activating Outer Polar Method for Solving Pure or Mixed Integer 0-1 Programs.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Balas,Egon

Report Date : JUN 1972

Pagination or Media Count : 39

Abstract : The paper discusses a procedure for solving pure and mixed integer 0-1 programs, based on the properties of outer polar sets introduced in another paper. Rather than generating cutting planes from outer polars, here the author uses the latter in a different way. Starting with a subset of the problem constraints, the author activates as many of the remaining constraints as are needed to produce a convex polytope that is contained in the outer polar of the convex hull of feasible integer points. When this is achieved, the algorithm terminates and the best solution found in the process is optimal. (Author)

Descriptors :   (*MATHEMATICAL PROGRAMMING, CONVEX SETS), INEQUALITIES, SIMPLEX METHOD, VECTOR SPACES, THEOREMS, LINEAR PROGRAMMING, QUADRATIC PROGRAMMING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE