A computational study of redundancy in randomly generated polytopes

DOI10.1007/BF02248692MaRDI QIDQ1207047zbMATH OpenFDO

Authors H. A. Eiselt, Carl-Louis Sandblom

Publication date 4 May 1993

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02248692

zbMATH Keywords

degree of redundancyrandom polytopesrandomly generated polytopessurvey

Mathematics Subject Classification ID

Polyhedra and polytopes; regular figures, division of spaces (51M20) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Large-scale problems in mathematical programming (90C06)

Recommendations

• Generation of degenerate linear programming problems
• scientific article; zbMATH DE number 176291
• Combinatorial redundancy detection
• scientific article; zbMATH DE number 1163814
• scientific article; zbMATH DE number 1866915

Cites work

• A comparison of the primal-simplex and primal-dual algorithms for linear programming
• A comparison of the primal‐simplex and complementary pivot methods for linear programming
• A feasible direction method for linear programming
• A note on detecting simple redundancies in linear systems
• A practicable steepest-edge simplex algorithm
• An analysis of an available set of linear programming test problems
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Computational behavior of a feasible direction method for linear programming
• Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
• Experiments with external pivoting
• General criteria for redundant and nonredundant linear inequalities
• scientific article; zbMATH DE number 3961338 (Why is no real title available?)
• scientific article; zbMATH DE number 3744912 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 3206575 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3354790 (Why is no real title available?)
• Nonadjacent extreme point methods for solving linear programs
• On the choice of the pivot columns of the simplex-method: Gradient criteria
• Random polytopes: Their definition, generation and aggregate properties
• Randomly generated polytopes for testing mathematical programming algorithms
• Redundancy in mathematical programming. A state-of-the-art survey
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• The Efficiency of the Simplex Method: A Survey
• The gravitational method for linear programming
• The Probability that a Random Polytope is Bounded

Cited in

(3)

• GENGUB: A generator for linear programs with generalized upper bound constraints
• Generation of degenerate linear programming problems
• Complexity analysis of random geometric structures made simpler

This page was built for publication: A computational study of redundancy in randomly generated polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1207047)