The Parallel of Decomposition of Linear Programs

Abstract

This thesis introduces a new calculus for manipulating linear-program decomposition schemes. A linear program is represented by a communication network, which is decomposed by splitting nodes in two, and a transformation is defined to recover subproblems from the network. We also define a dual-symmetric oracle that provides solutions to linear program, and can be performed by the simplex method, nested decomposition, and finally, parallel decomposition. Two important classes of linear program serve as examples for the above calculus: staircase linear programs and stochastic linear programs. For the former case, a sophisticated yet experimental computer codes has been written for an IBM 3090/ 600E with six processors. The code performs the parallel decomposition algorithm and is tested on twenty-two small to medium sized real-world problems. Experiments show that in addition to speedups provided by decomposition alone, performance is improved by using parallel processors.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1989
Accession Number
ADA216100

Entities

People

  • Robert Entriken

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computer Programming
  • Computers
  • Convex Programming
  • Evolutionary Algorithms
  • Flow Network
  • Linear Programming
  • Mathematical Programming
  • Network Science
  • Operations Research
  • Optimization
  • Parallel Computing
  • Parallel Processors
  • Plastic Explosives
  • Simplex Method

Readers

  • Computer Science.
  • Operations Research
  • Parallel and Distributed Computing.