Почему двойные цены отличаются для одной и той же модели Gurobi LP?

Question

Среда: Gurobi 8.1.1 + python3

Я попытался построить следующую линейную программную модель и вывести двойную цену.

min 100 x + y

st x + y> = 1 && 0 <= x, y <= 1 </strong>

Ниже приведен код:

from gurobipy import *

m = Model()

x = m.addVar(name='X', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0)
y = m.addVar(name='Y', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0) # first x then y

m.setObjective( x + 100 * y , sense=GRB.MINIMIZE  )

m.addConstr( x + y >= 1 )

m.optimize()

print(m.getAttr('Pi', m.getConstrs()))

Выходное значение равно 1.

Но когда две переменные определены в разном порядке, см. Следующий код, , выходное значение равно 100.

from gurobipy import *

m = Model()

y = m.addVar(name='Y', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0)
x = m.addVar(name='X', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0) # first y then x

m.setObjective( x + 100 * y , sense=GRB.MINIMIZE  )

m.addConstr( x + y >= 1 )

m.optimize()

print(m.getAttr('Pi', m.getConstrs()))

Почему они разные?

Answer 1

Я полагаю, это происходит потому, что все переменные исключаются при предварительном разрешении, и симплекс не требуется для решения проблемы. Если отключить предварительную проверку, двойное значение одинаково для обеих рецептур: m.Params.Presolve = 0

edit:

Это на самом деле связано с вырождением. Увеличение верхних границ переменных снимает вырождение. Смотрите ответ здесь .