Conference paper
A maximum feasible subset algorithm with application to radiation therapy
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.
| Language: | English |
|---|---|
| Year: | 1999 |
| Pages: | 405-408 |
| Proceedings: | American Control Conference 1999 |
| ISBN: | 0780349903 and 9780780349902 |
| ISSN: | 23785861 and 07431619 |
| Types: | Conference paper |
| DOI: | 10.1109/ACC.1999.782859 |
Heuristic algorithms Iterative algorithms LP Machine learning Machine learning algorithms Medical treatment Minimax techniques Operations research Pattern recognition Polynomials Vectors combinatorial mathematics combinatorial selection computational complexity double sided bounds exponential time feasible inequalities heuristic polynomial time algorithm heuristic programming iterative constraint removal procedure iterative methods linear one-sided inequality constraints linear programming linear system linear two-sided inequality constraints machine learning maximum cardinality subset maximum feasible subset algorithm medical treatment planning minimax techniques minmax linear programs operations research pattern recognition radiation therapy real vector set theory
