Parametric Linear Programming and Anti-Cycling Pivoting Rules
The traditional perturbution (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore,restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5332 |
| _version_ | 1811088203229167616 |
|---|---|
| author | Magnanti, Thomas L. Orlin, James B., 1953- |
| author_facet | Magnanti, Thomas L. Orlin, James B., 1953- |
| author_sort | Magnanti, Thomas L. |
| collection | MIT |
| description | The traditional perturbution (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore,restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anti-cycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables. |
| first_indexed | 2024-09-23T13:57:53Z |
| format | Working Paper |
| id | mit-1721.1/5332 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:57:53Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53322019-04-12T08:16:24Z Parametric Linear Programming and Anti-Cycling Pivoting Rules Magnanti, Thomas L. Orlin, James B., 1953- The traditional perturbution (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore,restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anti-cycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables. 2004-05-28T19:34:10Z 2004-05-28T19:34:10Z 1985-10 Working Paper http://hdl.handle.net/1721.1/5332 en_US Operations Research Center Working Paper;OR 144-85 722045 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Magnanti, Thomas L. Orlin, James B., 1953- Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title | Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title_full | Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title_fullStr | Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title_full_unstemmed | Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title_short | Parametric Linear Programming and Anti-Cycling Pivoting Rules |
| title_sort | parametric linear programming and anti cycling pivoting rules |
| url | http://hdl.handle.net/1721.1/5332 |
| work_keys_str_mv | AT magnantithomasl parametriclinearprogrammingandanticyclingpivotingrules AT orlinjamesb1953 parametriclinearprogrammingandanticyclingpivotingrules |