Issue with Barrier Problem not terminating in simplex after crossover

[William Zappa]

Hi,

I am trying to solve a relatively large LP problem using the Barrier Method (Simplex is far too slow). It has some numerical issues due to a wide range of coefficients, but I have reformulated the problem as best I can, and use both coefficient and objective function scaling.

The pre-processing, main barrier, push-phase and crossover seem to solve fine (Push phase complete: Pinf 0.0000000e+00, Dinf 1.3861116e-09). However, in the next step when simplex is used to bring the basic solution to optimality, Simplex doesn't terminate even when both Dinf and Pinf reach zero shortly after starting (see attached image), but instead keeps going for hours with increasing values for the Obj and Pinf and doesn't solve.

Can someone give me any suggestions?

Thanks!

[Tobias Achterberg]

The objective, bounds, and rhs values are still pretty big, and 2e-6 is also pretty small
for a matrix coefficient, so you probably won't get rid of numerical issues unless you
reformulate your model.

My guess is that the simplex algorithm has introduced some perturbation of the objective
function at the time it reaches 0 for primal and dual infeasibility and then needs to
remove the perturbation (which introduces a small dual infeasibility). Then, dual phase 1
is used to clean up the dual infeasibilities. It does some small pivots which, due to the
bad numerics, correspond to big steps in the primal space, which introduces large primal
infeasibilities.

Do you need a vertex solution? If not, you could turn off crossover. But note that often a
barrier solution is not as clean as a simplex solution.


Regards,

Tobias

[William Zappa]

Thanks Tobias!

I did some modifications and reduced the variable ranges a bit (see below), but my problem is that the formulation is built using 3rd party software which I cannot modify, so my options to reformulate are limited. The problem solves quicker now and with much better convergence with the barrier, but the cleanup still results in issues.

  Matrix range    [2e-04, 9e+02]

  Objective range [1e+00, 1e+09]

  Bounds range    [4e-01, 3e+08]

  RHS range       [1e-01, 4e+09]

I can run without crossover, but I am looking for an optimal solution.

Is it generally better to run with higher numerical focus and avoid coefficient and objective scaling (as this can lead to infeasibilities later), or employ both?

Thanks,

Will

[Tobias Achterberg]

Note that barrier without crossover will also provide an optimal solution. But typically
this is not a vertex solution. Often, LP models from practice have a multiple optimal
solutions. These solutions define a face of the polyhedron of feasible solutions, i.e.,
there is actually an infinite amount of optimal solutions, because every convex
combination of optimal solutions is again an optimal solution. For example, if you have

min x + y
s.t. x + y >= 1
x >= 0
y >= 0

then the whole line segment from (1,0) to (0,1) is optimal. The simplex algorithm always
yields a vertex solution, i.e., either (1,0) or (0,1) in this example. The barrier
algorithm, however, will end up in the analytic center of the optimal face, which is
(0.5,0.5) in the example. Often, one wants to have a vertex solution, which is why
crossover is enabled by default. This will go from the center solution (0.5,0.5) to one of
the vertex solutions. But nevertheless, (0.5,0.5) is optimal as well. So, you can just
disable crossover and still get an optimal solution.

Whether it is better to use higher numerical focus or play with the scaling flag depends a
lot on the problem instance. You have to try what works best for you. The default scaling
is pretty aggressive. If this leads to solutions with unscaled infeasibilities, then you
could first try to set ScaleFlag to 1.

Regards,

Tobias