[SCIP] SCIP gives the negative dual when a <= constraint is active at rhs

[Ambros Gleixner]

Dear Liding Xu,

The sign of the dual is a matter of definition.  If I am notmistaken, 
SCIP considers the dual LP for

min c^T x
s.t. lhs <= Ax <= rhs, lb <= x <= ub

to be

max  lhs^T ylhs + rhs^T yrhs + lb^T ylb + ub^T yub
s.t. A^T (ylhs + yrhs) + ylb + yub = c^T,
      ylhs, ylb >= 0,
      yrhs, yub <= 0

When you see a negative value in the dual, then it corresponds to the 
right-hand side/upper bound and the corresponding dual for the other 
side is zero.

Hope that helps,
Ambros


Am 25.06.2019 um 10:42 schrieb liding xu:
> Hello,
>     I am using scip to implement a branch and price algorithm for 
> unsplittable multi-commodity flow problem:
>          min c^T x       (1)
>                Ax <= 1,   (2)
>                Ex = 1,     (3)
>                x is binary.
>     where x is path variable, c is positive cost vector, E matrix only 
> consists of 0, 1 binary, A is a positive capacity matrix, and 1 in (2) 
> and (3) is unit vector.
> 
>    However, in the scip reduced cost pricing plugin, I call 
> SCIPgetDualsolLinear() for one of constraints (2), but get a negative 
> dual where the constraint is active at rhs 1. In my knowledge, the dual 
> for <= constraint can never be negative!
> 
>    I recompiled SCIP to enable the SCIP_DEBUG output of the lp.c, and it 
> display the detail on that pricing LP:
> 
> Every cols and rows is right except for one row:
> 
> [/home/xld/scip-6.0.1/src/scip/lp.c:14376] debug:  row <clique 
> constraint 107> [-1e+20,1] + 0: activity=1.000000000, 
> dualsol=-5.146793449, pfeas=1/1(1), dfeas=1/1(1)
> And here is statics on this LP solving:
> [/home/xld/scip-6.0.1/src/scip/lp.c:12058] debug: solving dual LP
> [/home/xld/scip-6.0.1/src/scip/lp.c:11264] debug: calling LP algorithm 
> <dual simplex> with a time limit of 1e+100 seconds
> [/home/xld/scip-6.0.1/src/scip/lp.c:10324] debug: solving LP 7 (20 cols, 
> 164 rows) with dual simplex (diving=0, nduallps=5, ndivinglps=0)
> [/home/xld/scip-6.0.1/src/scip/lp.c:10454] debug: solved LP 7 with dual 
> simplex (diving=0, nduallps=6, ndivinglps=0)
> [/home/xld/scip-6.0.1/src/scip/lp.c:11303] debug: LP feasibility: 
> primalfeasible=1, dualfeasible=1
> [/home/xld/scip-6.0.1/src/scip/lp.c:12010] debug: solving LP with dual 
> simplex returned solstat=1 (internal status: 2, primalfeasible=1, 
> dualfeasible=1)
> [/home/xld/scip-6.0.1/src/scip/lp.c:12307] debug: lpFlushAndSolve() 
> returned solstat 1 (error=0)
> [/home/xld/scip-6.0.1/src/scip/lp.c:14197] debug: getting new LP 
> solution 7 for solstat 1
> 
>    It report feasible, but the dual is not within any tolerance, and I 
> also tried dual simplex and primal simplex of GUROBI and CPLEX, all 
> produce the same result, it cannot be a numerical result.
> 
>    Why the scip produce wrong dual on active constraint?
> 
> Liding XU
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
Ambros Gleixner, Research Group Mathematical Optimization Methods at 
Zuse Institute Berlin, http://www.zib.de/gleixner