[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