A note on resolving infeasibility in linear programs by constraint relaxation

DOI10.1016/0167-6377(93)90079-VzbMATH Open0771.90068MaRDI QIDQ2367035FDOQ2367035

Authors: Jayaram K. Sankaran 

Publication date: 16 August 1993

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

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

zbMATH Keywords

polynomial-time solvabilitytotally unimodular matrixpost-infeasibility analysisconstraint relaxation

Mathematics Subject Classification ID

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

Cites Work

• On the computational power of pushdown automata
• Title not available (Why is that?)

Cited In (17)

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

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)