О надежности алгоритма решения псевдобулевых систем линейных неравенств, основанного на методе внутренней точки

Для решения непрерывной задачи линейного программирования известен метод внутренней точки (метод Кармаркара [1]). Целью работы является разработка и исследование надежности алгоритма решения псевдобулевых систем линейных неравенств, построенного на основе метода внутренней точки. Идея алгоритма заключается в релаксация исходной задачи, применении метода внутренней точки и возврате к булевому решению. Вместо традиционно используемой целевой функции - невязки системы - в предлагаемом алгоритме выбрана линейная функция от коэффициентов системы. Экспериментальный анализ показал высокую (86%) среднюю надежность алгоритма, превосходящую аналогичные результаты ранее примененных к этой задаче эвристических алгоритмов [2; 3] при решении случайно выбираемых псевдобулевых систем линейных неравенств (77 и 85%, соответственно). В результате экспериментальных исследований выявлены классы систем неравенств, на которых сравниваемые эвристические алгоритмы существенно различаются в эффективности решения. Это позволяет рекомендовать разработанный алгоритм для пополнения класса эвристик, ориентированных на исследуемую задачу. Недостатком разработанного алгоритма является относительно большое время работы.