An asymptotic simplex method for singularly perturbed linear programs

An asymptotic simplex method for singularly perturbed linear programs

0.00 Avg rating0 Votes
Article ID: iaor20031623
Country: Netherlands
Volume: 30
Issue: 5
Start Page Number: 295
End Page Number: 307
Publication Date: Oct 2002
Journal: Operations Research Letters
Authors: , ,
Abstract:

We study singularly perturbed linear programs. These are linear programs whose constraints and objective coefficients depend on a small perturbation parameter, and furthermore the constraints become linearly dependent when the perturbation parameter goes to zero. Problems like that were studied by Jeroslow in 1970s. He proposed simplex-like method, which works over the field of rational functions. Here we develop an alternative asymptotic simplex method based on Laurent series expansions. This approach appears to be more computationally efficient. In addition, we point out several possible generalizations of our method and provide simple updating formulae for the perturbed solution.

Reviews

Required fields are marked *. Your email address will not be published.