Как параметр feastol используется в неравенствах?

Question

Я решаю MIP, для которого SCIP печатает следующее после решения:

violation: right hand side is violated by 4.00681341261588e-06
best solution is not feasible in original problem

optimal solution found

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

numerics/feastol = 1e-9
numerics/lpfeastol = 1e-9
numerics/sumepsilon = 1e-9

Тем не менее, кажется, что ограничение всегда нарушается примерно 1e-6, независимо от того, какие параметры указаны выше.

Я хотел бы узнать больше о том, как этот параметр используется для ограничения типа A*x <= B. Используется ли это для точности или точности? То есть

A* |x-tol| - B <= 0

или

A*x - B <= tol

или что-то еще?

Спасибо!

Answer 1

для линейных ограничений, относительная разница между активностью ограничения (A * x) и правой стороны (B) вычисляется как

Изменение чисел / feastol потребует, чтобы эта разница была ближе к нулю, чтобы решение было принято.

Однако в вашем случае проблема заключается в том, что найдено решение, которое выполнимо в преобразованной проблеме (измененной с помощью предварительного решения и различных других исправлений), но не в исходной проблеме. Это может быть либо ошибка в SCIP (если вы можете поделиться файлом своего проблемного экземпляра, я мог бы изучить это), либо это может быть связано с агрегацией небольших числовых ошибок. Какую версию SCIP вы используете? (переход на более новую версию также может решить вашу проблему)

Если ваша проблема не очень сложная, вы можете попытаться решить ее без предварительного решения, установив

set presolving emphasis off

в интерактивной оболочке SCIP ,

Счастливого SCIPing, Леон