Distributed Decomposition of Block-Angular Linear Programs on a Hypercube Computer

Abstract

Algorithms based on the Dantzig-Wolfe decomposition principle for linear programs are implemented on an Intel iPSC-2 Hypercube computer with 64- processors. Computational results with block-angular linear programs from diverse applications are reported. They indicate that the approach of distributed computation on relatively inexpensive multiple processor computers may be very cost-effective for large, structured linear programs. It is also shown that by studying certain characteristics of the interaction among the master and subproblems, one can select algorithms that best exploit the parallel processing environment. Keywords: Large-scale systems; Linear programming decomposition; Parallel processing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1989
Accession Number
ADA216433

Entities

People

  • James K. Ho
  • S. K. Gnanendran

Organizations

  • University of Tennessee

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Electric Power
  • Environment
  • Linear Programming
  • Mainframe Computers
  • Operating Systems
  • Operations Management
  • Operations Research
  • Parallel Computing
  • Parallel Processing
  • Simplex Method
  • Very Large Scale Integration

Fields of Study

  • Engineering

Readers

  • Operations Research
  • Parallel and Distributed Computing.