# Understanding reduced costs and dual values

I have a headache regarding calculating the reduced costs of a linear program. I am using Pulp for modelling and CBC for solving.

What I do is, I model a linear programming problem based on a rhs vector $$b$$, a constraint matrix $$A$$ and a cost vector $$c$$. When I have solved the model, I want to print the duals, reduced costs and the solution itself. I do this in Python using Pulp as follows

# Print variable values and reduced costs
for v in model.variables():
print(v.name, "=", v.varValue, "\tReduced Cost =", v.dj)


and

# Print duals and slacks
for name, c in list(model.constraints.items()):
print("Duals=", c.pi, "\tSlack=", c.slack)


This seems to work fine. Then, for the fun of it, I wanted to calculate the reduced costs "by hand". I do this using the formula $$\bar{c}_j=c_j-\mu^TA_j$$ where $$c_j$$ is the objective function coefficient of the $$j$$'th variable, $$\mu$$ is the duals, and $$A_j$$ is the $$j$$'th column of $$A$$. I do this as follows

for it, col in enumerate(A):
# Reduced costs
print(c[it]-sum(duals[i]*col[i] for i in range(len(duals)))


(Note that $$A$$ is transposed for practical purposes in my implementation)

The problem is, these "by hand calculated reduced costs" do not have the same values as the ones provided by the solver. I have observed that the dual values printed are very small positive numbers, and consequently, the reduced costs I calculate are rather large compared to those provided by the solver. What am I doing wrong here? Is there something obvious that I am missing?

• What are the bounds on your variables? Commented Feb 7, 2023 at 16:09
• Hi @RobPratt bounds are $0\leq x_j\leq \infty$ Commented Feb 7, 2023 at 16:19
• Is your matrix A stored in a dense way? In case you're maximizing, try replacing - by +, solvers might have different conventions on the definition of duals. Commented Feb 7, 2023 at 16:22
• No dense matrix, but I only add non-zero entries from $A$ to the LP. I am minimising and all constrains are $\geq$-type so duals are non negative Commented Feb 7, 2023 at 16:25
• If A is sparse, then are you sure of the 3 lines you wrote? Is col[i] the coefficient of variable i in the row or the ith non-zero? Commented Feb 7, 2023 at 16:38