Несовместная система линейных однородных неравенств

[passenger]

Уважаемые форумчане!

Имеется система линейных однородных неравенств:

\left\{ \begin{array}{l} a_{11}p_1 + a_{12} p_2 + \ldots + a_{n1}p_n > 0,\\ \ldots\\ a_{m1}p_1 + a_{m2} p_2 + \ldots + a_{mn}p_n > 0.\\ \end{array} \right.

Вообще говоря, в общем случае система несовместная.
Моя задача состоит в том, чтобы найти хотя бы одно решение (p_1, p_2, \ldots, p_n), удовлетворяющее максимально возможному числу неравенств.
В случае нестрогих неравенств всегда существует возможность построения фундаментальной системы решений (метод изложен, например, в книге Солодовникова "Системы линейных неравенств").
Что происходит с такой системой в случае, когда неравенства становятся строгими?
К примеру, при n = 2 получаем множество прямых, проходящих через начало координат и разбивающих плоскость на сектора с вершиной в точке (0,0), для каждого из которых можно вычислить количество выполняемых в нем неравенств и выбрать точку из того сектора, в котором это число максимально). Могу предположить, что в общем случае геометрическая интерпретация системы позволяет решать эту задачу за O(n^m) операций.
У меня имеется система, где m = 80, n = 22. Существуют ли соответствующие эвристики, позволяющие сократить сложность вычислений и дающие приемлимые результаты?
К примеру, применим ли в данном случае метод бустинга, модификация симплекс-метода или что-то подобное?
Видимо, результат лежит где-то на поверхности.

Буду весьма благодарен за любые комментарии в этой теме.

[maxal]

Это NP-полная задача - см. последний параграф по этой ссылке:
http://www.nada.kth.se/~viggo/wwwcompen ... de208.html
Там же есть ссылка на статью:
E Amaldi, V Kann "The Complexity and Approximability of Finding Maximum Feasible Subsystems of Linear Relations"

[passenger]

Спасибо большое!
Статья оказалась очень полезной!