Analysis of Solution Methods for Interval Linear Programming

Abstract

In this paper, solution methods for ILP are studied. First of all, the principals and assumptions of two-step method (TSM) are analyzed. Secondly, the definition of feasible decision space for ILP is introduced. Also the existence of infeasible solutions and how these solutions are generated in TSM is examined. Thirdly, new solution method named three-step method (ThSM) is developed for solving ILP models. It is based on three proposed steps: TSM, feasibility test, and constricting method. The main advantage of ThSM is that no infeasible solutions would be included in the obtained results. Moreover, ThSM can generated interval solutions and does not have high computational requirements. An example has been presented to explain in detail the solution process of ThSM. Fourthly, three scenarios of Monte Carlo simulations have been introduced to further explore the detailed solutions for ILP. The results demonstrate that when all coefficients of ILP are assumed to obey normal or uniform distribution the developed methods are applicable. Under other distribution assumptions for coefficients in ILP, further studies should be developed.

Keywords: interval linear programming, approximate method, two-step method, three-step method, feasibility test, constricting method, Monte Carlo simulation