Учитывая эффективный алгоритм решения системы разностных ограничений при некоторых х должен быть целыми

Question

Этим упражнение из КСПСА 24.4-12 (не домашнее задания, я просто пытаюсь решить все упражнения в КСПСЕ)

Дайте эффективный алгоритм для решения системы Ax ≤ b разностных ограничений, когда все элементы b являются вещественнозначными, а указанное подмножество некоторых, но не обязательно всех, неизвестных xi должно быть целым числом.

Если все хи являются целыми числами, мы можем позволить Ь = пол (б) и с использованием алгоритма Беллмана-Форда нахождения кратчайшего пути, чтобы решить эту проблему в ограничении графа, но как о некоторых из XI являются целыми числами и некоторые нет? Он похож на задачу целочисленного программирования, но целочисленное программирование NP-hard, этот вопрос имеет меньше ограничений, есть ли более эффективный алгоритм?

Answer 1

У вас есть аналогичные вещи в линейной оптимизации - единственная разница в том, что у вас нет минимального или максимального требования. Возможно, вы можете адаптировать некоторые из методов. Начиная с реального решения, существует алгоритм Гомория, добавляющий дополнительные ограничения, чтобы заставить целое число xi стать целочисленным, и существуют алгоритмы Branch-and-Bound, пытаясь как можно скорее исключить большие части поискового пространства.

Answer 2

Сначала найдите элемент с минимальным абсолютным значением в векторе b, умножьте его на C, чтобы все значения в векторе b целого числа (например, если минимальное абсолютное значение равно 3.102, мы можем умножить вектор b на 1000), затем разрешите его алгоритмом bellman-ford и, наконец, разделите его на C!

Answer 3

Ну. Чувак, это упражнение Введение в Алгоритм. Мой собственный способ - адаптировать алгоритм Беллмана-Форда, который состоит в том, чтобы в принципе построить ориентированный взвешенный граф, основанный на неравенствах, а затем при ослаблении ребер, только для целых чисел только ключевое значение узла. Я думаю, это сработает.