4
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ What are the bounds on your variables? $\endgroup$
    – RobPratt
    Commented Feb 7, 2023 at 16:09
  • $\begingroup$ Hi @RobPratt bounds are $0\leq x_j\leq \infty$ $\endgroup$
    – Djames
    Commented Feb 7, 2023 at 16:19
  • 3
    $\begingroup$ 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. $\endgroup$
    – fontanf
    Commented Feb 7, 2023 at 16:22
  • $\begingroup$ 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 $\endgroup$
    – Djames
    Commented Feb 7, 2023 at 16:25
  • 1
    $\begingroup$ 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? $\endgroup$
    – fontanf
    Commented Feb 7, 2023 at 16:38

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.