[SCIP] LP dual solution accuracy

Tue May 26 10:37:48 CEST 2020

Thank you for the quick reply, Gerald.

Sorry, I wasn't rigorous enough in explaining my current situations. Please see my new comments below yours.

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 shouldn't have used " lower bound of the node".  I meant the LP value of RMP ( via SCIPgetLPObjval) was not decreasing after adding columns generated by pricers. I agree that it can happen when there are degenerate LP solutions and the LP value does not decrease after adding a column with the negative reduced cost.  ( Sorry, I assumed it was typo when you said "LP value does not INCREASE after you added a column".  If you really meant that, please let me know.)

Another question :  If I access to SCIPgetLPObjval within the tree, does it give the LP solution of the RMP problem at the current node (after applying branching rules until the node) or the current lower bound of the RMP? I thought it was the former case, but I am a bit confused now.

I looked up this SCIP archive and found the related one:   http://listserv.zib.de/pipermail/scip/2019-November/003806.html<https://urldefense.proofpoint.com/v2/url?u=http-3A__listserv.zib.de_pipermail_scip_2019-2DNovember_003806.html&d=DwMD-g&c=OCIEmEwdEq_aNlsP4fF3gFqSN-E3mlr2t9JcDdfOZag&r=Osh6OZnwQvU8HwUOMplSvwODWzfjaDwvgHwMpaTarpQ&m=2z0tuM88JD-5xXEHV1VMgcb6Tl4PqI4cGjNg69cNQfk&s=Mc-HSRXloQyLu9CPMfT-hPw2lkOtYEAx059jWojoJd8&e=>
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.

Thank you for the clarification.

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.

Sorry for the bad explanation. I used a tolerance for the reduced cost = 1e-07. While CPLEX results gives the most negative reduced costs around -1e-10 ( > -tolerance), SCIP with disabled presolving and propagating gives the subproblem objective value less than -tolerance (about -0.06).  I agree that I shouldn't use SCIP as LPsolver, but it was just more convenient way to test it within Python interface. I will try to compare it with Soflex.

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.

I understand the optimal primal and dual solutions could be different due to degeneracy, but I missed that the reduced costs of some columns could be still negative at optimal in this case.  Thank you.

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.

I see. The columns that I generate are binary variables and I didn't explicitly put the upper bound for the variable other than defining it as "B" type variables. Will I need to define it as just integer variables and set its  upper bound <=1 as lazy constraints?
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
Thank you for your kind answer, Gerald.

Best
Jungeun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200526/530f455f/attachment.html>