Consider a set of linear one sided or two sided inequality constraints on a real vector X. The problem of interest is selection of X so as to maximize the number of constraints that are simultaneously satisfied, or equivalently, combinatorial selection of a maximum cardinality subset of feasible inequalities. Special classes of this problem are of interest in a variety of areas such as pattern recognition, machine learning, operations research, and medical treatment planning. This problem is generally solvable in exponential time. A heuristic polynomial time algorithm is presented in this paper. The algorithm relies on an iterative constraint removal procedure where constraints are eliminated from a set proposed by solutions to minmax linear programs. The method is illustrated by a simulated example of a linear system with double sided bounds and a case from the area of radiation therapy.
|Title of host publication||Proceedings of American Control Conference|
|Publication status||Published - 1999|
|Event||American Control Conference 1999 - San Diego, CA, United States|
Duration: 2 Jun 1999 → 4 Jun 1999
|Conference||American Control Conference 1999|
|City||San Diego, CA|
|Period||02/06/1999 → 04/06/1999|