An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem

DOI10.1007/BF02284627zbMath0887.90112MaRDI QIDQ1380443

John W. Chinneck

Publication date: 4 March 1998

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

zbMATH Keywords

heuristic algorithmirreducible infeasible setselastic programming

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (18)

Some approaches to the solution of optimization problems in supervised learning ⋮ The maximum feasible subset problem (maxFS) and applications ⋮ An Interactive Algorithm to Deal with Inconsistencies in the Representation of Cardinal Information ⋮ 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 ⋮ A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set ⋮ A characterization of the 2-additive Choquet integral through cardinal information ⋮ Generalized filtering algorithms for infeasibility analysis ⋮ A two-phase relaxation-based heuristic for the maximum feasible subsystem problem ⋮ Infeasibility resolution based on goal programming ⋮ Automatic repair of convex optimization problems ⋮ 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 ⋮ On optimal zero-preserving corrections for inconsistent linear systems ⋮ An aggregation/disaggregation approach to obtain robust conclusions with ELECTRE TRI ⋮ Resolving inconsistencies among constraints on the parameters of an MCDA model

Uses Software

• CPLEX
• LINDO
• MINOS

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Irreducibly inconsistent systems of linear inequalities
• A computer-assisted analysis system for mathematical programming models and solutions. A user's guide for ANALYZE. Incl. 1 disk
• MINOS(IIS): Infeasibility analysis using MINOS
• Some results concerning post-infeasibility analysis
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• A note on resolving infeasibility in linear programs by constraint relaxation
• Identifying Minimally Infeasible Subsystems of Inequalities
• Locating Minimal Infeasible Constraint Sets in Linear Programs
• Computer Codes for the Analysis of Infeasible Linear Programs
• The Composite Simplex Algorithm

This page was built for publication: An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem