[SCIP] LP dual solution accuracy

[Gerald Gamrath]

Hi Jungeun,

> Hi,
>
> I have been using SCIP framework with its own solver(Soflex) to 
> implement Branch and Price, which requires dual solutions of the 
> restricted master problem to calculate the reduced costs of additional 
> columns.
>
> After running a few sample instances, I started doubt the accuracy of 
> the dual solutions because Pricer keeps generating columns at the root 
> node with the negative reduced costs but the lower bound of the node 
> didn’t reduce.  ( Sometimes it even increased very little bit (1e-10), 
> but I guess its because of the optimality tolerance setting)
>
This is not how it works. If the lower bound could reduce, it wouldn't 
be a lower bound. :-) If the LP value can still reduce because pricers 
may find improving solutions, SCIP won't use this as the lower bound for 
the node. Therefore, you should not see a change in the lower bound 
unless the pricers are done and cannot add any improving solutions (or 
you compute a valid lower bound yourself and pass it to the lowerbound 
pointer). You could set "display/lpobj/active = 2" to get a display 
column that show the actual LP value, or access it via SCIPgetLPObjval. 
This should hopefully go up.

On the other hand, there is degeneracy in many LPs, so it may happen 
that you do some degenerate pivots and the LP value does not increase 
after you added a column.

> I looked up this SCIP archive and found the related one: 
> http://listserv.zib.de/pipermail/scip/2019-November/003806.html
>
> According to the answer, I set presolving/maxrestarts = 0   , 
> propagating/maxrounds=0 and propagating/maxroundsroot=0 , but still 
> the dual solution seems not accurate.
>
This question is about something different, namely, how to call SCIP on 
your LP problem and get dual values. However, this is not recommended. 
If you really only want to solve an LP, then you should use an LP 
solver, like So*P*lex, not SCIP, which is a MIP solver. Within SCIP, 
however, many LPs are solved internally, for the presolved problem at 
the current nodes, by the linked LP solver, and this is where you get 
your dual solution from in case of branch-and-price. But those LPs are 
already solved with SoPlex or CPLEX, not with SCIP.
>
> I have tested the dual solutions in multiple ways.  For example, I let 
> SCIP and CPLEX solver read the same .lp file and obtained the dual 
> solutions using each lp solver, respectively. Then, solved the same 
> subproblem using two different sets of dual solutions.  With the dual 
> solutions of SCIP(Soflex), the subproblem found a column with the 
> negative reduced costs  whereas the subproblem objective value using 
> dual solutions of Cplex was positive.
>
As I said, SCIP is not an LP solver, and its presolving methods are not 
built to support returning dual solutions for your original problem. You 
might want to use SoPlex for this. Otherwise, you probably need to 
follow the advide given in the link above, but you should also disable 
presolving completely, as mentioned there as well.

Additionally: what do you mean with negative reduced costs, I hope you 
use a tolerance? Also, it sounds suspicious that the dual solution of 
CPLEX results in a positive objective value for the subproblem. This 
should normally not happen, because there should be variables with 
reduced cost 0, e.g., the current basic variables.

And again: due to degeneracy, there may be different optimal primal and 
dual solutions, so the behavior for a single LP relaxation and the 
resulting pricing problem may be different.

Another thing: do you have upper bounds on your variables? Did you mark 
them as lazy? Having non-lazy upper bounds on variables regularly causes 
issues, because those may have dual values that you probably don't 
regard in your pricing problems.

> As far as I know, there are many researchers using SCIP framework for 
> Branch and Price algorithm, so I believe there should be a way to 
> resolve this problem.
>
> One thing I tried to do to resolve this problem is that writing .lp 
> file of RMP within the Pricer plugin and reading it with CPLEX to 
> solve the LP relaxation and get the dual solutions. However, it didn’t 
> include the constraints generated from branching in the parents nodes 
> and wasn’t able to have the right LP model to solve.
>
Which constraints are included depends on which method you use to write 
the problem. But in general, I would not recommend this, it should all 
work with the linked LP solver.


> Long story in short,
>
> 1) I set presolving/maxrestarts = 0   , propagating/maxrounds=0 and  
> propagating/maxroundsroot=0  to get dual solutions, but it is not 
> accurate. What else should I do to get the correct dual solutions of LP ?
>
See above. This should also not be needed within the branch-and-price 
framework.


> 2) Is there a way to use Cplex to solve RMP LP relaxation within 
> Branch and Price framework?
>
> 3) Would it be resolved if I install SCIP with CPLEX as lp solver?
>
I don't know if your problem would be resolved, the branch-and-price 
framework SCIP should work both with SoPlex and CPLEX as LP solvers, 
without any tweaks. But if you install SCIP with CPLEX as LP solver, all 
LPs, including the RMP LP relaxations, are solved with CPLEX.


Best,
Gerald


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200526/92f67162/attachment.html>