Численная устойчивость симплексного алгоритма

Question

Редактировать: Симплекс математического алгоритма оптимизации, не путать с симплексным шумом или триангуляцией.

Я реализую свой собственный решатель линейного программирования, и я хотел бы сделать это, используя 32-разрядные числа с плавающей запятой. Я знаю, что Simplex очень чувствителен к точности чисел, потому что он выполняет много вычислений, и если используется слишком малая точность, могут возникнуть ошибки округления. Но все же я хотел бы реализовать это с использованием 32-битных операций с плавающей запятой, чтобы я мог выполнять инструкции по четырем параметрам, то есть использовать SIMD для выполнения 4 вычислений одновременно. Я знаю, что я мог бы использовать удвоения и сделать инструкции шириной 2, но 4 больше, чем 2:)

У меня были проблемы с моей реализацией с плавающей запятой, когда решение было неоптимальным или проблема была признана невозможной. Это происходит особенно со смешанными целочисленными линейными программами, которые я решаю с помощью метода ветвей и границ.

Поэтому мой вопрос: как я могу максимально предотвратить наличие ошибок округления, приводящих к неосуществимым, неограниченным или неоптимальным решениям?

Я знаю одну вещь, которую я могу сделать, это масштабировать входные значения так, чтобы они были близки к одному ( http://lpsolve.sourceforge.net/5.5/scaling.htm). Есть ли что-то еще, что я могу сделать?

Answer 1

Да, я попытался реализовать алгоритм для задачи Extended Knapsack, используя метод Branch and bound и Greedy Algorithm в качестве эвристики, точного аналога симплекса, работающего со стратегией поворота, которая выбирает наибольшее увеличение цели.

У меня тоже были проблемы с числовой стабильностью алгоритма.

Лично я не думаю, что есть простой способ устранить проблемы, если мы продолжаем использовать числа с плавающей запятой, но есть способ обнаружить нестабильность в процессе ветвления.

Я думаю, что с помощью экспериментов, а не строгих математических расчетов по анализу устойчивости, большинство ошибок передаются через целочисленное решение, которое очень близко к ограничениям системы.

Для любого целочисленного решения мы вычисляем резерв для этого решения, и если элементы вектора чрезвычайно малы или имеют величину от 1e-14 до 1e-15, то останавливаем ветвление и сообщаем о нестабильности.