Re: [Help-glpk] non-official updated version of glpk (4.62 pre-release)

[Andrew Makhorin]

Hi Chris,

> 
> > NEW: The bound perturbation technique was implemented in the primal
> > simplex solver (now this feature is enabled by default).
> 
> I did some testing and it seems to work fine: I run most of the
> instances in the "Benchmark of Simplex LP solvers" by H. Mittelmann (
> http://plato.asu.edu/ftp/lpsimp.html ) and for many fewer iterations
> are needed now, while two more can be solved (neos2 and neos3).

Thank you very much for testing.

> 
> One thing I noticed is that in some cases primal feasibility is lost
> when removing the perturbation. The attached patch is a hack to
> continue using the dual simplex solver when this happens. This further
> improves solution times for some instances and allows two more to be
> solved (self and stat96v1). I'm not suggesting to add this patch as
> is, just sending it for easy testing.
> 

Yes, switching to the dual simplex in this case is a natural choice,
because the perturbed lp being optimal is dual feasible and removing
perturbation keeps dual feasibility since objective coefficients are not
changed. However, such feature needs some additional options, namely: 
i) if the primal simplex detects primal infeasibility, it should return
rather than continue the search starting from phase I; and ii) in the
dual simplex perturbation should be disabled.

Besides, there remain some questions, e.g. how to perturb/relax bounds
for basic fixed variables. Currently only one (lower or upper) bound is
relaxed, so the fixed variable turns into a double-bounded one. This,
however, guarantees that the feasible region of the original lp is a
proper subset of the feasible region of the perturbed lp.

Best regards,

Andrew Makhorin