Accession Number : AD0697301

Title :   A SIMPLEX-SEARCH ALGORITHM FOR SOLVING ZERO-ONE MIXED INTEGER PROGRAMS.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Davis,Ronald E.

Report Date : 13 OCT 1969

Pagination or Media Count : 65

Abstract : An algorithm for solving zero-one mixed integer programming problems which has been developed and implemented in an all-in-core FORTRAN program is reported with computational experience on a variety of well-known problem types. The imbedded linear programs of Land and Doig, the derived binary constraints of Benders, and the binary feasibility tests introduced by Balas, are used in conjunction with augmented linear programs obtained by summarizing in the form of a linear inequality the set of solutions remaining to be (implicitly) enumerated when only partial completion of a branch-and-bound search has been accomplished. These augmented linear programs yield new sufficient conditions for optimality of an incumbent solution which have significantly accelerated convergence of the search procedure on a number of problem types, notably the Savage-Lorie project selection or multi-dimensional knapsack variety. Computational experience with scheduling, warehouse location, and economic investment planning models is also reported. The algorithm has proven satisfactory for use on a production basis, and is currently in use for selection of water resource development projects. (Author)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), SEARCH THEORY, SIMPLEX METHOD, MATHEMATICAL MODELS, OPTIMIZATION, INEQUALITIES, SPECIAL FUNCTIONS(MATHEMATICAL), MATHEMATICAL LOGIC, MANAGEMENT PLANNING AND CONTROL, BUDGETS, SCHEDULING

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE