Найдите точные решения линейной программы

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

GLPK может выполнять точные арифметические действия, но не может отображать решения в виде рациональных чисел (т.е. я получаю 0,3333 для 1/3). Я, вероятно, мог бы попытаться угадать, какое число имеется в виду, но это кажется очень хрупким.

Мне не удалось найти LP-решатель, который может делать такие вещи. Есть ли один? Производительность не является большой проблемой; мои проблемы очень маленькие. (Я рассматривал возможность использования решателя SMT, такого как Z3; они могут решать такие проблемы и предоставлять точные рациональные решения, но они прибегают к устранению квантификаторов вместо использования более подходящего алгоритма для линейных программ, таких как Simplex)


linear-programming arbitrary-precision
person Manuel Eberl    schedule 27.03.2016    source источник
comment
QSopt_ex Rational LP Solver (link) имеет доступный исходный код   -  person Erwin Kalvelagen    schedule 27.03.2016
comment
Это выглядит хорошо, и это дает бонусные баллы за то, что это бесплатное программное обеспечение. Спасибо! Если вы превратите это в ответ, я приму это.   -  person Manuel Eberl    schedule 29.03.2016
comment
Для будущих читателей: мне не удалось получить указанный выше QSopt_ex для сборки в моей системе, но эта вилка QSopt_ex на Github работала отлично: github.com/jonls/qsopt-ex   -  person Manuel Eberl    schedule 21.04.2016

Ответы (1)


arrow_upward
2
arrow_downward

SoPlex может использовать рациональную арифметику для точного решения LP. Используйте это так:

soplex -X -Y -o0 -f0 problem.lp

Опции X и Y будут печатать простое и двойственное решение в рациональных числах, а o0 и f0 задают допуск оптимальности и выполнимости равным 0, следовательно, решение LP точно.

Вам необходимо установить GMP (или MPIR в Windows), чтобы использовать рациональные функции. Одним из преимуществ по сравнению с QSopt_exact является то, что SoPlex использует гибридный метод, сочетающий скорость вычисления двойной точности с точной точностью рациональной арифметики (итеративное уточнение).

person mattmilten    schedule 28.03.2016
comment
Выглядит хорошо. Я бы предпочел, чтобы это было бесплатное программное обеспечение, и мои задачи были в формате Cplex, но, тем не менее, оно того стоило. Спасибо! - person Manuel Eberl; 29.03.2016