NONCONVEX LINEAR PROGRAMMING.

Abstract

An algorithm for solving the 'nonconvex linear programming problem' Maximize z = cx, Subject to: (A sub i)x = or < (b sub i), 1 = 1,...,p for at least one i, x = or > 0 is given. The problem is viewed as one of n-dimensional geometry with the union of the p distinct solution sets a general nonconvex (possibly disconnected) polyhedral set. A continuous path in n-space is generated which passes from solution set to solution set as the optimum is sought. The core of the solution procedure is a 'linking linear program' which is a efficient, highly flexible substitute for Phase I of the simplex method. Given an arbitrary linear programming problem in n decision variables and having m constraints, the linking linear program solution approach can conceivably produce an optimum basic feasible solution with little more computational effort than minimum (n,m)+1 'simplex' pivot operations. (Author)

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1970
Accession Number
AD0713484

Entities

People

  • Robert E. Fricks

Organizations

  • Case Western Reserve University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Evolutionary Algorithms
  • Geometry
  • Heuristic Methods
  • Linear Programming
  • Mathematics
  • Simplex Method

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.
  • Linear Algebra

Technology Areas

  • Space