An Explicit Solution to the Multi-level Programming Problem.

Abstract

The multi-level programming problem is defined as an n-person nonzero-sum game with perfect information in which the players move sequentially. The bi-level linear case is addressed in detail. Solutions are obtained by recasting this problem as a standard mathematical program and appealing to its implicitly separable structure. The reformulated optimization problem is linear save for a complementarity constraint of the form <u,g> = 0. This constraint is decomposed in a manner that permits us to achieve separability with very little cost in dimensionality. A general branch and bound algorithm is then applied to obtain solutions. Unlike the conventional mathematical program though, the multi-level program may fail to have a solution even when the decision variables are defined over a compact set. An auxiliary optimization problem is employed to detect such failure. Finally, the general max-min problem is discussed within the bi-level programming framework. Examples are given for a variety of related problems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 26, 1979
Accession Number
ADA069310

Entities

People

  • James E. Falk
  • Jonathan F. Bard

Organizations

  • George Washington University

Tags

Communities of Interest

  • Human Systems
  • Space
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Engineering
  • Game Theory
  • Linear Programming
  • Mathematical Programming
  • Matrix Games
  • New York
  • Nonconvex Programming
  • Nonlinear Programming
  • Optimization
  • Probability
  • Simplex Method
  • Systems Engineering

Fields of Study

  • Mathematics

Readers

  • Game Theory.
  • Operations Research