Решение системы линейных однородных неравенств особого вида

[dremov]

Мне необходимо практически тоже самое что и человеку
http://dxdy.ru/post207253.html#p207253
С той только разницей, что количество неизвестных у меня порядка 10-20, количество неравенств -- десятки тысяч, возможно сотни тысяч или больше (фактически это обучающее множество, для которого мне хочется иметь максимальную долю выполненных неравенств).
Особенность задачи в том, что коэффициенты всех неравенств небольшие целые числа близкие к 0 - фактически это столбцы состовленные как разности двух других столбцов с небольшими неотрицательным целыми числами. При том сумма этих чисел в изначальных столбцах почти всегда меньше размерности системы.
Может кто знает какие эвристики тут могут подойти, где стоит об этом почитать. Я пока не нашел ничего полезного. Пытаюсь делать лучевой поиск добавляя по одному неравенства и строя системы фундаментальных решений неравенств и запоминая сколько неравенств на каждой из этих систем нарушено (на каждом шаге выбирая только k областей в которых меньше всего нарушений неравенств). Но такой подход кажется не очень хорош -- размер систем фундаментальных решений растут в худшем случае экспоненциально, а на деле это оказывается вычислительно слишком сложно. А лучше пока придумать ничего не удается.
Хочется идей или классических статей по этому поводу.

[mserg]

Данную задачу можно свести к частично-целочисленной задаче линейного программирования. Для каждого уравнения будет добавлена одна псевдобулева переменная, принимающая значение ноль, если ограничение «удовлетворено»; и единицу – если «не удовлетворено». Критерий – минимизация суммы псевдобулевых переменных.

После этого можно воспользоваться хорошим пакетом линейного программирования (например, бесплатным пакетом CBC или платным CPLEX) – система сама найдет оптимальное решение. Насколько мне известно, коммерческие системы позволяют решать задачи с миллионами переменных и ограничений. Маловероятно, что для этой задачи вручную написанная программа даст сколь-нибудь сравнимый результат в сравнении с пакетами линейного программирования.

[dremov]

Большое спасибо за ответ, я как раз некоторе время назад пришел к подобному выводу: полезно использовать готовые пакеты решающие задачу линейного программирования. То есть сводить эту задачу к задаче линейного программирования добавляя переменные связанные с нарушением неравенств (оказывается, полезно их делать даже не булевыми, а просто с физическим смыслом "мера нарушения неравенства"). В частности я нашел несколько эвристик в статьях Chinneck'а подходящих к задаче MaxFS (maximum feasible subsystem) которую я оказывается решаю :)
А подумав и еще чуть-чуть (ну и почитав), начал осознавать что вроде можно это свести и к задаче решаемой при помощи SVM и прочих классических методов машинного обучения. Что очень даже разумно, учитывая откуда появилась задача и сильную мусорность данных.
Суть - как только я осознал что эта задача называется именно так, я без труда начал находить то, что мне нужно - статьи, эвристики и прочее. Конечно писать все с нуля в данном случае не только долго, но и вредно, так как пишу управляющий код я на питоне, и лучше использовать готовые стандартные пакеты решения стандартных задач написанные на си и вызывать их из питона. Чем я сейчас и занимаюсь.
Коммерческие системы плохи тем что они 1) коммерческие и 2) их не особо приятно указывать в ссылках, списке литературы etc.
Это все в рамках дипломной работы, так что пользоваться коммерческими продуктами тяжело - обычно они не спешат делиться потрохами, которые мне необходимо не только понимать, но и вероятно описывать в той или иной мере. А вот открытые удобны для этого. Сейчас пробую прикрутить OpenOpt + SciPy.
Надеюсь, мое и Ваше соображения помогут еще кому, кто столкнется с подобной задачей.
Если будут еще мысли -- с удовольствием почитаю.