Why gurobi report negative reduced cost for some variables in optimal solution?
Answered
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (win64)
Optimize a model with 106 rows, 65 columns and 135 nonzeros
Model fingerprint: 0x12f24080
Coefficient statistics:
Matrix range [1e+00, 7e+00]
Objective range [2e+02, 2e+04]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Presolve removed 106 rows and 65 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration Objective Primal Inf. Dual Inf. Time
0 2.5661851e+04 0.000000e+00 0.000000e+00 0sSolved in 0 iterations and 0.00 seconds
Optimal objective 2.566185081e+040 -
-
-
The y variables have a finite upper bound, in this case an upper bound of 1. For this reason, the reduced costs can be negative. This means that such a variable is non-basic at its upper bound.
For example, if a variable y with y <= 1 has reduced costs of -3, it means that it has an optimal solution value of 1 (it is at its upper bound) and, if you reduce its value you would deteriorate (i.e., increase) your objective function value by at least 3 units per unit decrement in y. So, for example, if your optimal objective function value is 100 and you push the y variable from 1 to 0.8, then you increase the objective function value by at least (-0.2)*(-3) = 0.6 to 100.6.
Finite upper bounds are an extension to the text-book simplex algorithm, which only works on a standard problem min{cx : Ax >= b, x >= 0}. For this standard problem, it is true that reduced costs in an optimal solution are non-negative. If you introduce upper bounds, you get a second set of reduced costs (one reduced cost for the lower bound, one for the upper bound). But because at most one of the two reduced costs values for each variable can be non-zero, one can equivalently combine the two reduced cost values into a single one, with negative values meaning that they correspond to the upper bound.
Regards,
Tobias
1 -
-
Thank you very much, Tobias. You provide me with very important information. I also notice that Gurobi provides the Presolve method by default so that it's possible no further to use the simplex method to solve some "easy" problem. In this case, it's also incorrect to call var.RC method to obtain reduced costs. In my column generation implementation, it does happen in initial iterations. Thus I close Presolve, and I obtain positive reduced costs. Your answer also provides me other matters needing attention! Thank you again.
0 -
-
-
This issue arises very frequently in column generation approaches, and then people are surprised why their pricing algorithm seems to be wrong (because the pricing algorithm often assumes standard form with non-negative variables without upper bounds).
In many of these applications, the master problem is the LP relaxation of binary variables, and those binary variables appear in set packing or set partitioning constraints, i.e., sum xi <= 1 or sum xi = 1. In this case, the upper bound 1 of the binary variables is implied by the constraint. Hence, it is often an easy solution to this issue to just discard the upper bound. Then, you can be sure that your reduced cost values are always non-negative.
Tobias
1 -
-
Exactly, thank you very much!
0 -
Post is closed for comments.
Comments
6 comments