Finding the minimum weight IIS cover of an infeasible system of linear inequalities

DOI10.1007/BF02284626zbMath0889.90110MaRDI QIDQ1380442

Mark Parker, Jennifer K. Ryan

Publication date: 22 April 1998

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

set coveringfeasibilityirreducible inconsistent subsystems

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items (14)

Some approaches to the solution of optimization problems in supervised learning ⋮ The maximum feasible subset problem (maxFS) and applications ⋮ Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures ⋮ Solution techniques for the large set covering problem ⋮ Consistency, redundancy, and implied equalities in linear systems ⋮ Faster maximum feasible subsystem solutions for dense constraint matrices ⋮ Logic-based benders decomposition with a partial assignment acceleration technique for avionics scheduling ⋮ Bi‐objective optimization of the tactical allocation of job types to machines: mathematical modeling, theoretical analysis, and numerical tests ⋮ A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set ⋮ A two-phase relaxation-based heuristic for the maximum feasible subsystem problem ⋮ Identifying relatively irreducible infeasible subsystems of linear inequalities ⋮ Complexity of minimum irreducible infeasible subsystem covers for flow networks ⋮ Optimization approaches to supervised classification ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems

Uses Software

• Netlib

Cites Work

• Irreducibly inconsistent systems of linear inequalities
• Some results concerning post-infeasibility analysis
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Consistency, redundancy, and implied equalities in linear systems
• A note on resolving infeasibility in linear programs by constraint relaxation
• Diagnosing Infeasibility in Min-cost Network Flow Problems Part II: Primal Infeasibility
• Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
• A Greedy Heuristic for the Set-Covering Problem
• Approaches to Diagnosing Infeasible Linear Programs
• Identifying Minimally Infeasible Subsystems of Inequalities
• Locating Minimal Infeasible Constraint Sets in Linear Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding the minimum weight IIS cover of an infeasible system of linear inequalities