Computing Block-Angular Karmarker Projections with Applications to Stochastic Programming. Revision.

Abstract

This document presents a variant of Karmarkar's projective algorithm for block angular structured linear programs, such as stochastic linear programs. By computing the projection efficiently, the authors give a worst case bound on the order of the running time that can be an order of magnitude better than that of Karmarkar's standard algorithm. A related variant is applied to the dual program, and its implications for very large-scale problems are given. Keywords: Iterations; Points (Mathematics). (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1986
Accession Number
ADA185647

Entities

People

  • John R. Birge
  • Liqun Qi

Organizations

  • University of Michigan

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computational Science
  • Computations
  • Computer Programming
  • Engineering
  • Evolutionary Algorithms
  • Industrial Engineering
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Simplex Method
  • Systems Engineering
  • Universities

Readers

  • Operations Research