[SCIP] Unresolved numerical problems in a set covering formulation

[Christoph Hansknecht]

Hello Ambros,

thank you very much for your help and suggestions.

Apparently the problem was indeed due to the different magnitudes of
cost coefficients. I was focused on the condition of the base matrices
instead, so I did not consider that possibility. I implemented Farkas
pricing (Although I would prefer some other means of ensuring primal
feasibility, I will have to think on that).

If you could find the time, I would appreciate it if you could make it
easier to track down numerical problems. "Unresolved numerical problem"
is just a little vague.

Christoph

On Fri, 2018-03-23 at 12:04 +0100, Ambros Gleixner wrote:
> 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
> > 
> 
>