Random Linear Programs.

Abstract

In this paper, we study the random generation of a linear program of the type P : Max cx subject to Ax < or = b. We assume these random variables to be independent and symmetric around zero and to have continuous distribution functions, therefore, transforming the random generation problem into a distribution free combinatorial problem. Making use of the theory of d-Arrangements, we compute the probabilities of P being feasible and bounded, and we also calculate the expected number of faces, of all possible dimensions, of the polytope that is the feasibility set of P, given that P is feasible.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1981
Accession Number
ADA099812

Entities

People

  • Ilan Adler
  • Sancho E. De B. Berenguer

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • California
  • Coefficients
  • Continuity
  • Demographic Cohorts
  • Distribution Functions
  • Efficiency
  • Industrial Engineering
  • Iterations
  • Linear Programming
  • Military Research
  • Operations Research
  • Probability
  • Random Variables
  • Simplex Method
  • Theorems
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Statistical inference.