Randomized Relaxation Methods for
the Maximum Feasible Subsystem
problem
by
Pietro Belotti
Politecnico di Milano
The Maximum Feasible Subsystem (MaxFS) problem consists, given an infeasible set
A of constraints, in finding a feasible subset S of A of maximum cardinality.
Applications of MaxFS are found e.g. in Telecommunications, Computational
Biology (with instances of up to hundreds of millions of inequalities), Data
Mining, Radiation Therapy, and Image Processing. We present a method which, at
each iteration, given an infeasible point x_k and a subset B of constraints
violated by x_k, generates a new point x_(k+1) exploiting the distance
information of the constraints in B. Our computational tests show that the
method finds, in relatively short time, provably good solutions of instances
with up to 400,000 inequalities.