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 [13], image and signal processing [15], 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 l₁- or l₂ -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 [2].

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 [21]) and computational biology (modelling the energy function that drives the folding of proteins [16]) 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 [7], as well as the latest polyhedral techniques based on partial set covering formulations [3,19] and combinatorial Benders' cuts [8].