Automatic Identification of Network Rows in Large-Scale Optimization Models.

Abstract

The solution of contemporary large-scale linear, integer, and mixed integer programming problems is often facilitated by the exploitation of intrinsic special structure in the model. This paper deals with the problem of identifying embedded pure network rows within the coefficient matrix of such models and presents two heuristic algorithms for identifying such structure. The problem of identifying the maximum size embedded pure network is shown to be among the class of NP-hard problems, therefore, the polynomially-bounded algorithms presented here do not guarantee network sets of maximum size. However, upper bounds on the size of the maximum network set are developed and used to evalaute the algorithms. Finally, the algorithms were tested with a number of large-scale, real-world models and the results of these benchmark runs are presented. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1980
Accession Number
ADA093256

Entities

People

  • William Gordon Wright

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automatic
  • Computational Complexity
  • Computers
  • Conversion
  • Evolutionary Algorithms
  • Guarantees
  • Inclusions
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Plastic Explosives
  • Simplex Method
  • United States
  • Vector Spaces

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.
  • Theoretical Analysis.