DIRECT REDUCTION OF LARGE CONCAVE PROGRAMS

Abstract

A very simple and flexible procedure is given for reducing a concave mathematical program to a finite sequence of subproblems, each involving a subset of the original constraints. While very much in the spirit of the 'secondary constraint' idea, constraints are dropped as well as added from subproblem to subproblem. The reduction procedure is of quite general applicability, and is designed to be used with various concave programming algorithms for solving the subproblems. It seems particularly suited to facilitating the solution of problems with more constraints than could otherwise be handled. It is shown that an obvious specialization to linear programs yields the dual Simplex method, and that various 'cutting-plane' methods can also be naturally described from the general viewpoint offered in the report.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1966
Accession Number
AD0647552

Entities

People

  • A. M. Geoffrion

Organizations

  • University of California, Los Angeles

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Classification
  • Computer Programming
  • Contractors
  • Contracts
  • Evolutionary Algorithms
  • Identification
  • Integer Programming
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Optimization
  • Quadratic Programming
  • Security
  • Sequences
  • Simplex Method
  • Terminals

Fields of Study

  • Engineering

Readers

  • Operations Research