[Scip] why the dual solution is non-positive?

[Tobias Achterberg]

XiangyongLi wrote:
> <mailto:lixiangyong at hotmail.com>
> Hi, Tobias, If I rewrite constraints (2) as standard form x_{ij} -
> Dz>=0, then the dual constraint should be
> \sum_{k} v_{ijk} <= c_{ij}
> and dual multiplier should be non-negative.

This is correct. But since you multiplied the constraint with -1 to get your form (2), the 
dual values are also multiplied with -1 and consequentially become non-positive.


Tobias



> Xiangyong
> ------------------------------------------------------------------------
> *发件人：* Tobias Achterberg
> *发送时间：* 2010-01-06 18:28:12
> *收件人：* XiangyongLi
> *抄送：* scip
> *主题：* Re: [Scip] why the dual solution is non-positive?
> XiangyongLi wrote:
>  > min \sum_{(i,j)} c_{ij}x_{ij}
>  > s.t. Az ==1 for each k (1)
>  > Dz - x_{ij} <= 0, for each arc (i,j) and each k (2)
>  > x, z >=0
>  > For constraints (2), I define dual multiplier v_{ijk}. So in my dual
>  > model, I should have \sum_{k} v_{ijk} <= c_{ij}. And dual multiplier
>  > v_{ijk} should be non-negative. But the SCIP returns non-positive
> v_{ijk}.
> Not correct. Note that the coefficients of the x_{ij} variables in the
> matrix is -1.
> Therefore, you have the dual constraint
> \sum_{k} -v_{ijk} <= c_{ij},
> and because the primal inequality is a '<=' row of a minimization
> problem, the dual
> multiplier v_{ijk} must be non-positive.
> Tobias
> __________ Information from ESET Smart Security, version of virus
> signature database 4747 (20100106) __________
> The message was checked by ESET Smart Security.
> http://www.eset.com