Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms
The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax b, x > 0 ), then there are two mathemat...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5318 |
| _version_ | 1826198880964837376 |
|---|---|
| author | Birge, John R. Freund, Robert M. |
| author_facet | Birge, John R. Freund, Robert M. |
| author_sort | Birge, John R. |
| collection | MIT |
| description | The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax b, x > 0 ), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of (A AT). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of (ATA). Depending on the structure of the matrix A, one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints. |
| first_indexed | 2024-09-23T11:11:27Z |
| format | Working Paper |
| id | mit-1721.1/5318 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:11:27Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53182019-04-12T08:07:45Z Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms Birge, John R. Freund, Robert M. interior-point algorithm, linear program, factorization, fill-in. The efficiency of interior-point algorithms for linear programming is related to the effort required to factorize the matrix used to solve for the search direction at each iteration. When the linear program is in symmetric form (i.e., the constraints are Ax b, x > 0 ), then there are two mathematically equivalent forms of the search direction, involving different matrices. One form necessitates factoring a matrix whose sparsity pattern has the same form as that of (A AT). The other form necessitates factoring a matrix whose sparsity pattern has the same form as that of (ATA). Depending on the structure of the matrix A, one of these two forms may produce significantly less fill-in than the other. Furthermore, by analyzing the fill-in of both forms prior to starting the iterative phase of the algorithm, the form with the least fill-in can be computed and used throughout the algorithm. Finally, this methodology can be applied to linear programs that are not in symmetric form, that contain both equality and inequality constraints. 2004-05-28T19:33:26Z 2004-05-28T19:33:26Z 1990-07 Working Paper http://hdl.handle.net/1721.1/5318 en_US Operations Research Center Working Paper;OR 220-90 329642 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | interior-point algorithm, linear program, factorization, fill-in. Birge, John R. Freund, Robert M. Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title | Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title_full | Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title_fullStr | Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title_full_unstemmed | Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title_short | Prior Reduced Fill-In in Solving Equations in Interior Point Algorithms |
| title_sort | prior reduced fill in in solving equations in interior point algorithms |
| topic | interior-point algorithm, linear program, factorization, fill-in. |
| url | http://hdl.handle.net/1721.1/5318 |
| work_keys_str_mv | AT birgejohnr priorreducedfillininsolvingequationsininteriorpointalgorithms AT freundrobertm priorreducedfillininsolvingequationsininteriorpointalgorithms |