Understanding reduced costs and dual values

Question

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?

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. — fontanf, Feb 07 '23 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 — Djames, Feb 07 '23 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? — fontanf, Feb 07 '23 at 16:38
@Djames, Why not try to write the problem in an LP format to illustrate the model coefficients precisely and see what may be wrong? — A.Omidi, Feb 08 '23 at 04:52
@A.Omidi This is embarrassing! Printing to an .lp file I discovered that I calculated the reduced costs correctly, but I did not solve the model I thought I did. Hence, the problem was in the modelling, not in calculating the reduced costs. Your comment pointed me in the right direction, so if you can turn it into an answer, I will gladly accept it! — Djames, Feb 08 '23 at 08:24

score 1 · Accepted Answer · answered Feb 08 '23 at 12:04

One of the best possible ways for the models with some difficulties to understand how the model can be treating in the solving process, specifically in the situations like infeasibility, comparing some solver outputs by handy calculations, etc. would be by writing the model in an LP file and investigating which one of the typos cause the issue.

Understanding reduced costs and dual values

1 Answers1