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.