|The Max FS problem|
We consider the following problem, referred to as MAX FS:
|Given an infeasible linear system , where and , find a feasible subsystem containing as many inequalities as possible.|
This problem has a number of interesting applications in various fields such as operations research [7,12], radiation therapy , image and signal processing , statistical discriminant analysis and machine learning [4,14]. There is growing interest in MAX FS due to the fact that many complex phenomena that can be well-approximated with linear models yield formulations involving large and generally infeasible linear systems for which approximate solutions in terms of l1- or l2 -norms are not meaningful.
Note that since linear system feasibility can be checked in polynomial time, the MAX FS structure differs substantially from that of MAX SAT, the well-known problem of satisfying a maximum number of Boolean clauses. Like MAX SAT though, MAX FS can be approximated within a factor of 2 but it does not admit a polynomial-time approximation scheme, unless P = NP .
Apart from large-scale instances arising in classification problems [4,14] and in the context of infeasible linear programs [7,12], very large MAX FS instances with up to millions of inequalities and thousands of variables occur in several challenging applications in telecommunications (digital video broadcasting ) and computational biology (modelling the energy function that drives the folding of proteins ) that are of current interest.
Such instances are beyond the reach of available computational approaches, which include state-of-the-art MIP solvers applied to big-M formulations, the best available heuristics , as well as the latest polyhedral techniques based on partial set covering formulations [3,19] and combinatorial Benders' cuts .