We consider the maximum feasible subsystem problem in which, given an infeasible system of linear inequalities, one wishes to determine a largest feasible subsystem. The focus is on the version with bounded variables that naturally arises in several fields of application. To tackle this NP-hard problem, we propose a simple but efficient two-phase relaxation-based heuristic. First a feasible subsystem is derived from a relaxation (linearization) of an exact continuous bilinear formulation, and then a smaller subproblem is solved to optimality in order to identify all other inequalities that can be added to the current feasible subsystem while preserving feasibility. Computational results, reported for several classes of instances, arising from classification and telecommunication applications, indicate that our method compares well with one of the best available heuristics and with state-of-the-art exact algorithms.

A two-phase relaxation-based heuristic for the maximum feasible subsystem problem

AMALDI, EDOARDO;BRUGLIERI, MAURIZIO;
2008-01-01

Abstract

We consider the maximum feasible subsystem problem in which, given an infeasible system of linear inequalities, one wishes to determine a largest feasible subsystem. The focus is on the version with bounded variables that naturally arises in several fields of application. To tackle this NP-hard problem, we propose a simple but efficient two-phase relaxation-based heuristic. First a feasible subsystem is derived from a relaxation (linearization) of an exact continuous bilinear formulation, and then a smaller subproblem is solved to optimality in order to identify all other inequalities that can be added to the current feasible subsystem while preserving feasibility. Computational results, reported for several classes of instances, arising from classification and telecommunication applications, indicate that our method compares well with one of the best available heuristics and with state-of-the-art exact algorithms.
File in questo prodotto:
File Dimensione Formato  
maxfs-COR.08.pdf

Accesso riservato

: Pre-Print (o Pre-Refereeing)
Dimensione 222.84 kB
Formato Adobe PDF
222.84 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/544536
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 12
social impact