A note on resolving infeasibility in linear programs by constraint relaxation

DOI10.1016/0167-6377(93)90079-VMaRDI QIDQ2367035zbMATH OpenFDO

Authors Jayaram K. Sankaran

Publication date 16 August 1993

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

Full work available at URL https://doi.org/10.1016/0167-6377(93)90079-V

zbMATH Keywords

constraint relaxationpolynomial-time solvabilitypost-infeasibility analysistotally unimodular matrix

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Locating Minimal Infeasible Constraint Sets in Linear Programs
• Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear Program
• An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Minimally Infeasible Set-Partitioning Problems with Balanced Constraints

Cites work

• scientific article; zbMATH DE number 3185418 (Why is no real title available?)
• On the computational power of pushdown automata

Cited in

(17)

• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Resolving infeasibility in extremal algebras
• Consistency, redundancy, and implied equalities in linear systems
• Finding the minimum weight IIS cover of an infeasible system of linear inequalities
• An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
• Complexity of minimum irreducible infeasible subsystem covers for flow networks
• A note on unsolvable systems of max-min (fuzzy) equations
• On refinement strategies for solving \(\textsc{MINLP}\)s by piecewise linear relaxations: a generalized red refinement
• Automatic repair of convex optimization problems
• A two-phase relaxation-based heuristic for the maximum feasible subsystem problem
• Faster maximum feasible subsystem solutions for dense constraint matrices
• scientific article; zbMATH DE number 4166931 (Why is no real title available?)
• Preferential reducts and constructs in robust multiple criteria ranking and sorting
• Minimally Infeasible Set-Partitioning Problems with Balanced Constraints
• The maximum feasible subset problem (maxFS) and applications
• Efficient MIP techniques for computing the relaxation complexity
• Extended McCormick relaxation rules for handling empty arguments representing infeasibility

This page was built for publication: A note on resolving infeasibility in linear programs by constraint relaxation

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