The Max FS problem

[ Home | People | Papers | Software | Instances | Links ]

We consider the following problem, referred to as MAX FS:

Given an infeasible linear system $ A{\bf x}
\geq {\bf b}$, where $ A\in\ensuremath{\mathbb{R}}^{m\times n}$ and $ {\bf b}\in\ensuremath{\mathbb{R}}^{m}$, 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 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 [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].

This page is maintained by Pietro Belotti.