[SCIP] Unresolved numerical problems in a set covering formulation

[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).

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?
- Is the condition of the basis matrix the problem? If
  so, do you know of any numerically better set covering formulations?
- Or is the problem caused by the large costs of the artificial
  variables compared to the path costs?
- 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)? Is it possible that
  a path has
been missed and the reportedly optimal
  solution is in fact not
optimal?

I would very much appreciate any help on the problem.

Sincerely,
Christoph Hansknecht