[SCIP] Unresolved numerical problems in a set covering formulation

[Ambros Gleixner]

Hi Christoph,

Some answers inline:


Am 22.03.2018 um 17:51 schrieb Christoph Hansknecht:
> Hello all,
> 
> I am currently solving a combinatorial problem which consists of
> covering a set of edges in a graph with a limited number of (s,t)-
> paths. I have employed a pricing approach which consists of a master
> program with the following structure:
> 
> - Each (s,t)-path has a variable, the path variables
>   have costs which are supposed to be minimized
> - Each edge has to be covered by an (s,t)-path
> - The number of paths is bounded from above
> - All edges in the graph have binary variables assigned to
>   them, the variable of an edge has zero cost, an equality
>   constraint ensures that the value of the edge variable 
>   is equal to the sum of the variables of the (s,t)-paths
>   containing that edge.
> 
> The exact formulation can be seen here: http://mathb.in/23666
> 
> I have added some artificial variables with high cost in order to
> ensure feasibility. Also, the path variables will be implicitly binary
> as soon as the edge variables are fixed. 
> 
> 
> 
> I am pricing new paths based on the dual solution values of the current
> master problem. I use the edge variables to make sure that the pricing
> problem is well-behaved deeper down the B&B tree (which would not be
> the case for 0/1 path variables).

What do you mean by well-behaved?


> I implemented the formulation in C++ using scip 4.0.0 / soplex 3.0.0.
> The approach works as expected and I am able to solve smaller problems.
> 
> I therefore ran the program on a larger instance (1200 vertices, 45,000
> edges, 300 edges need to be covered by 30 paths). After several pricing
> rounds I got the following message:
> 
> (node 1) solution of LP 57 not optimal (pfeas=1, dfeas=0) -- solving
> again with tighter feasibility tolerance
> 
> ...
> 
> (node 1) unresolved numerical troubles in LP 87 -- using pseudo
> solution instead (loop 1)
> 
> The message was sent while trying to solve the root LP. Scip then went
> on and started branching immediately. Similar problems occurred in
> different nodes in the tree:
> 
> (node 2) solution of LP 87 not optimal (pfeas=1, dfeas=0) -- solving
> again with tighter feasibility tolerance
> (node 2) solution of LP 87 not optimal (pfeas=1, dfeas=0) -- solving
> again from scratch
> (node 2) unresolved numerical troubles in LP 88
> 
> Still, scip seemed to work reasonably well nonetheless. After a short
> while it was reported that the optimal solution has been found. It is
> however the case that the pricing did not find any new paths after the
> first occurrence of the numerical problems.
> 
> 
> 
> I browsed the archives and found a thread with a similar problem:
> 
> http://listserv.zib.de/pipermail/scip/2012-March/000891.html
> 
> However, the thread seems to be unresolved (apparently, the OP gave up
> on it?)
> 
> Following a suggestion in the thread, I dumped out the problem right
> before the unresolved numerical problems start in the root LP:
> 
> https://pastebin.com/N42NE7Bd
> 
> I solved the problem directly (which for some reason works without
> problems) and displayed the LP solution quality. I got the following
> back:
> 
> Basis matrix condition (estimated): 2.369756e+03
> Basis matrix condition (exact):     2.369756e+03
> 
> The condition seems high to me, but I really have no comparison.
> 
> 
> 
> 
> My questions are:
> - Is this kind of problem common with set covering formulations?

Not that I would know.


> - Is the condition of the basis matrix the problem? If
>   so, do you know of any numerically better set covering formulations?

No, <1e4 is rather small.


> - Or is the problem caused by the large costs of the artificial
>   variables compared to the path costs?

That could very well be, especially since SCIP reports that dual
feasibility is the problem (dfeas=0).  If you can reduce the big-M or
ensure initial feasibility without the z variables or implement the
Farkas pricing callback, either might solve your issues.  How large is
the M?


> - Is it a coincidence that the pricer does not find any more
>   paths as
> soon as the numerical problem occurs or is the
>   pricer not able to find
> new paths due to
>   numerical problems (dfeas=0 seems to indicate that
> there
>   is no feasible dual solution)?

Without dual solution the redcost pricing cannot be called, so this is
not a coincidence.


> Is it possible that
>   a path has
> been missed and the reportedly optimal
>   solution is in fact not
> optimal?

I don't think so, SCIP should recognize this and treat the dual bound
from the LP relaxation as invalid.  What does the dual bound column say?

Further suggestions:
- Update to SCIP 5.0.1 / SoPlex 3.1.1.
- Experiment with a different LP solver to see if it is a systemative
formulation or an LP solver issue.

Best,
Ambros


> 
> I would very much appreciate any help on the problem.
> 
> Sincerely,
> Christoph Hansknecht
> _______________________________________________
> 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