[Scip] why the dual solution is non-positive?
Tobias Achterberg
achterberg at zib.de
Wed Jan 6 09:48:52 MET 2010
Hi Xiangyong,
If I am not completely wrong you mixed up the inequality senses and signs in your argument.
Your primal LP is
min c^T x
s.t.
Ax == b (1)
Cx <= d (2)
x >= 0
Therefore, the dual problem asks you to find a linear combination of the rows (i.e., dual
multipliers) that give a valid lower bound on the objective function. Therefore, the
outcome of the linear combination has to be a ">=" constraint (to represent a lower
bound). Consequentially, the dual multipliers of the inequalities (2) have to be
non-positive. Of course, the signs of dual variables for equations (1) are not restricted.
Tobias
XiangyongLi wrote:
> Dear all,
> For my B&P, I have some problem:
> SCIP returned non-positive dual solution for all constraints. These dual
> solutions logically should be non-negative.
> My problem is a minimization model with some equalities and some "<="
> constraints.
> min f(x)
> s.t.
> Ax=b (1)
> Cx<=d (2)
> x is binary
> Logically I know that the dual solutions of constraints (2) are
> non-negative. In SCIP, we should create initial constraints using format
> "lhs <= .... <= rhs" for either minimization or maximization problem. In
> my code SCIPgetDualsolLinear() returns non-positive dual solutions of
> constraints (2).
> For minimization problem, can I say SCIP returns the dual solutions of
> constraints for a standard formulation (say all constraints are ">=") ?
> Concerning my problem, the dual solution of each equality constraint is
> the same as the one SCIP returns. But for inequality constraints, the
> dual solutions should be negative of values that SCIP returns.
> Is the above argument is correct? Thanks.
> Best regards.
> Xiangyong Li
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list