879
eng
reportzib
0
2005-11-11
2005-11-11
--
A Branch-And-Cut for the Maximum Feasible Subsystem Problem
We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications.
05-46
879
urn:nbn:de:0297-zib-8797
Appeared in: SIAM J. Optimization 19 (2008) 21-38
Marc Pfetsch
ZIB-Report
05-46
eng
uncontrolled
infeasible linear inequality system
eng
uncontrolled
irreducible infeasible subsystem
eng
uncontrolled
(IIS) maximum feasible subsystem problem
eng
uncontrolled
minimum IIS-cover
eng
uncontrolled
branch-and-cut
Informatik, Informationswissenschaft, allgemeine Werke
Combinatorial optimization
ZIB Allgemein
ZIB-Infeas
https://opus4.kobv.de/opus4-zib/files/879/ZR_05_46.pdf
https://opus4.kobv.de/opus4-zib/files/879/ZR-05-46.pdf
https://opus4.kobv.de/opus4-zib/files/879/ZR_05_46.ps
https://opus4.kobv.de/opus4-zib/files/879/ZR-05-46.ps