Problem with dual prices

[Art Cohen]

I am using AMPL with Gurobi to solve an LP minimization  problem. I am getting a negative dual price for an upper bound constraint on a variable which is clearly incorrect (if I increase the upper bound the solution does not change and the dual price goes to 0). Note that the variable effected by the constraint also has a lower bound which is equal to the upper bound.  I thought presolve may be causing the problem since there are several redundant constraints that affect this variable. I tried turning off AMPL presolve however when I did this all the dual prices reported by AMPL were 0 (??).  I get the same prices when using Cplex. Any suggestions?   Thanks.

[Robert Fourer]

There are two possibilities I see here.

If you have a constraint like "LB <= [expression] <= UB" but LB is equal to UB, then this appears to AMPL and the solvers as "[expression] = UB" and the dual value is relative to this equality constraint. Thus the dual value won't tell you what happens when UB is increased while LB is left at its old value.

Also it can happen that you are at a breakpoint in the sensitivity function, so that the rate of change in the objective when UB is marginally increased is different from the rate of change in the objective when UB is marginally decreased. In that case the dual solution is not unique, and the solver in effect chooses arbitrarily between the different optimal dual values.

What gets reported also depends on whether you specify bounds in a "var" declaration or separately in a "subject to" statement. So, it could help to give an example of the AMPL statements that you are working with.

Bob Fourer
am...@googlegroups.com

=======

[Art Cohen]

Thanks for your response. The upper and lower bound constraints are in separate statements, i,e,

 

          expression <= UB

          expression >= LB

 

where UB and LB. The expression contains a single variable. I tried to set up a simple example with the same characteristics and got correct dual prices.

 

I noticed something else. The dual variable for the constraint in question is equal to the value for that constraint as if the cost associated with that variable were 0.  Is it possible that the presolve removes the variable from the cost objective and that this is the reason that the dual price is not what is expected? Also, please comment on my question regarding turning off AMPL presolve and not getting any dual variables reported.

[Robert Fourer]

Normally AMPL's presolve phase removes any "subject to" constraints that represent simple lower or upper bounds on variables. These bounds are passed to the solver as part of the variables' definitions; or in the special case where the lower bound equals the upper bound, the variable is fixed and also is removed from the problem. After the solver returns dual values for the reduced problem, AMPL recreates dual values for the constraints that presolve dropped. The dual values should be correct even if the bounds were equal and the variable was removed from the problem.

When AMPL's presolve is turned off (option presolve 0) then all of the "subject to" constraints are sent to the solver as given in their AMPL definitions (except in trivial cases such as where a constraint contains no variables). I would expect Gurobi to then return correct dual values for those constraints, which would be reported by AMPL.

In my experience, the most common cause of seemingly wrong dual values is that there are multiple optimal solutions to the dual problem, and the one that is returned (or recreated) does not provide the marginal values that are expected. However, we're willing to investigate cases where the dual solution appears to be suboptimal or infeasible for the dual problem.

Bob Fourer
4...@ampl.com