[SCIP] Pricer keeps generating single-vertex segments for partitioning problem

[Gerald Gamrath]

Hi Robert,

do you apply some tolerance when checking if a segment has negative 
reduced costs? You should probably use SCIPisDualfeasNegative() to check 
this.

Did you print information about the variables you created to see that 
there are duplicates? From the output you added to your mail, I don't 
see an immediate problem. Actually, there is obviously something 
changing in your LP solution, since you find a new primal feasible 
solution by rounding the LP solution. You could activate the display 
column for the optimal objective value of your current (restricted) LP 
to see if this improves: display/lpobj/active = 2

Concerning the things you tried:
- explicit upper bounds on variable cause a lot of problems for column 
generation, so you should use lazy upper bounds whenever you have upper 
bounds on your variables which are implicitly enforced by some constraints
- the maxrestarts parameter is about restarting the complete solving 
process, including another round of presolving. As you guessed, this 
does not refer to reoptimizing the LP, which will need to be done in 
order to complete the column generation process and obtaining a dual bound.

Best,
Gerald

Am 13.07.2017 um 12:25 schrieb Robert Schütz:
> Hey all,
>
> I have implemented an image partitioning problem in SCIP, involving a
> pricer that generates segments with negative reduced costs.
> Each possible segment has a fitting error calculated by the sum of the
> fitting errors of each pixel in it and the fitting value of a segment is
> given by the color of one "super" node in that segment and therefore
> constant when solving the pricing problem.
> The pricing problem is of itself a MIP involving constraints on the
> connectivity of the generated segment and solved using SCIP.
>
> Now the problem is that after a while, the pricer keeps generating
> single-pixel segments consisting only of a  super node (which are
> therefore added multiple times, even though they should have positive
> reduced costs after adding them once).
> This happens shortly after I get the following output:
>
>      (node 1) solution of LP 43 not optimal (pfeas=1, dfeas=0) -- solving again with tighter feasibility tolerance
>       34.6s|     1 |     0 |   844 |     - |2444k|   0 |   0 | 215 |  56 | 215 |  56 |   0 |   0 |   0 |      --      | 5.000000e+04 |    Inf
>      r34.6s|     1 |     0 |   844 |     - |2444k|   0 |   0 | 215 |  56 | 215 |  56 |   0 |   0 |   0 |      --      | 1.955779e+04 |    Inf
>
> and after another round of the pricer:
>
>       time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
>       36.6s|     1 |     0 |   877 |     - |2583k|   0 |   0 | 220 |  56 | 220 |  56 |   0 |   0 |   0 |      --      | 1.955779e+04 |    Inf
>      r36.6s|     1 |     0 |   877 |     - |2583k|   0 |   0 | 220 |  56 | 220 |  56 |   0 |   0 |   0 |      --      | 1.912082e+04 |    Inf
>
> After doing some research on the mailing list etc, I tried these two
> - SCIPchgVarUbLazy(scip, var, 1.0)
>    but the behaviour does not change regardless of the segment variables
>    being binary or contiunous and this setting being set.
> - SCIPsetIntParam(scip, "presolving/maxrestarts", 0)
>    which did obviously not hinder SCIP from solving again (see SCIP's
>    output above) so I guess this does not count as restarting :)
>
> Do you have an idea what the problem could be?
>
> Yours, Robert
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip