Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств

Предложен эвристический алгоритм решения систем псевдобулевых линейных неравенств, являющийся модификацией алгоритма Балаша. Выход из тупиковой точки производится с помощью техники выбора очередного состояния, как в алгоритме имитации отжига. Приводятся результаты экспериментального сравнения предложенного алгоритма и упомянутых эвристик для решения случайных систем линейных неравенств с использованием двух типов целевых функций – суммы и максимума невязок неравенств решаемой системы. Экспериментально установлена бо́льшая эффективность предложенного алгоритма. Этот же алгоритм был применён к решению систем линейных неравенств, описывающих линейный регистр сдвига с булевой пороговой функцией выхода. Описывающая линейный регистр сдвига система линейных неравенств характеризуется экспоненциальным числом неравенств по отношению к длине выходной последовательности линейного регистра сдвига. Описываются способы сокращения объёма указанной системы линейных неравенств без сокращения длины выхода. Во всех исследованных случаях предложенный алгоритм находит решения системы линейных неравенств, не всегда совпадающие с оригинальным решением.