Article ID: | iaor1993345 |
Country: | United Kingdom |
Volume: | 43 |
Issue: | 2 |
Start Page Number: | 177 |
End Page Number: | 180 |
Publication Date: | Feb 1992 |
Journal: | Journal of the Operational Research Society |
Authors: | Myers D.C. |
The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a large relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.