title:
New Views in Linear Programming on: 
(i) Degeneracy and (ii) Solving Large Scale LPs

Henry Wolkowicz, Dept Comb. & Opt., University of Waterloo, Canada

abstract:
(i) We first look at 
Strict Feasibility and Degeneracy in Linear Programming, LP.
We show that if strict feasibility fails, then every basic feasible solution
is degenerate. We study the theoretical and numerical ramifications of this
result. We include an efficient preprocessing technique for facial reduction
for strict feasibility.

(ii) We then look at the best approximation problem to a polyhedral set, BAP.
We exploit compact optimality conditions to obtain an
efficient nonsmooth Newton method for BAP.
We then apply a parameterized version to solve large scale LPs. 
The efficiency arises from applying sensitivity analysis. This results in a
stepping stone external path following method, a simplex like path following
method.

Empirical evidence is provided for both parts of the talk.