A constraint selection technique for a class of linear programs

DOI10.1016/0167-6377(88)90027-2MaRDI QIDQ1105487zbMATH OpenOpenAlexFDO

Authors Danny C. Meyers, Wei Shih

Publication date 1988

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(88)90027-2

zbMATH Keywords

binding constraints identificationconstraint selectionheuristic

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

It is well known that, for most linear programs, only a relatively small percentage of constraints are binding at the optimal solution. Significant effort has been directed towards methods which identify those constraints most likely to be tight at optimality. We present here a simple, but highly effective, heuristic for finding solutions to linear programming problems by using only a small proportion of the original constraints.

Recommendations

• A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming
• Constraint optimal selection techniques (COSTs) for nonnegative linear programming problems
• A heuristic approach for identification of redundant constraints in linear programming models
• Constraint Reduction for Linear Programs with Many Inequality Constraints
• A simplex method based on reducing the constraint conditions of linear programming

Cites work

• A note on detecting simple redundancies in linear systems
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Finding duplicate rows in a linear programming model
• On trivial and binding constraints in programming problems
• Redundancy in mathematical programming. A state-of-the-art survey
• Some Properties of Redundant Constraints and Extraneous Variables in Direct and Dual Linear Programming Problems
• Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems
• The pivot and probe algorithm for solving a linear program

Cited in

(12)

• The transformation technique for a class of variable upper bounding constraints in linear programming
• A constraint selection technique in limit analysis
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• A heuristic approach for identification of redundant constraints in linear programming models
• scientific article; zbMATH DE number 4158377 (Why is no real title available?)
• A fast method for a class of one-stage bounded variables and single constrained linear programming problems
• Technical Note—On the Weighted Selection Algorithm for Certain Linear Programs with Nested Constraint Coefficients
• scientific article; zbMATH DE number 4095202 (Why is no real title available?)
• A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming
• Dual extrapolation for sparse GLMs
• A comparative study of redundant constraints identification methods in linear programming problems
• Constraint optimal selection techniques (COSTs) for nonnegative linear programming problems

This page was built for publication: A constraint selection technique for a class of linear programs

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