CODEWITHSUNDEEP
optimizationlinear-programminggurobi
Alexander Svozil
Alexander Svozil

Reputation: 38

Gurobi: Objective Value of Primal not equal to dual (transportation problem)

Using the solution here for the transportation problem with the model:

m = Model("transport_problem_2")
flow = {}
for c in cities:
    for b in bases:
        flow[c,b] = m.addVar(obj=distance[c,b], name='flow_%s_%s' %(c,b))
m.update()
for c in cities:
    m.addConstr(quicksum(flow[c,b] for b in bases) <= supply[c], 'supply_%s' %(c))
for b in bases:
    m.addConstr(quicksum(flow[c,b] for c in cities) >= demand[b], 'demand_%s' %(b))
m.optimize()

For practice, I wrote the dual of the above program in Gurobi:

m_dual = Model("transport_problem_2_dual")


alpha = m_dual.addVars(cities,name='alpha')
beta = m_dual.addVars(bases,name='beta')

m_dual.setObjective(alpha.prod(supply)+beta.prod(demand), GRB.MAXIMIZE)
m_dual.addConstrs((alpha[c] + beta[b] <= distance[c,b] for c,b in arcs), 'alpha_beta')
m_dual.optimize()

Unfortunately, the two optimal objective values are different even though the dual is correct. (I checked it by hand using m_dual.display()). Does someone know why? I thought that the Strong Duality Theorem guarantees this property because both objective values are optimal.

Edit: To make the dual LP work, I had to bound the variables in the dual correctly (as pointed out by the answer)

alpha = m_dual.addVars(cities,name='alpha',lb=-GRB.INFINITY)

Upvotes: 0

Views: 354

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

I think there may be a sign error in the variables in the dual formulation. This is what I have used:

enter image description here

Upvotes: 1

Related Questions