On the integer properties of scheduling set partitioning models |
| |
Affiliation: | 1. Department of Mining Engineering, University of Kashan, Kashan, I. R., Iran;2. Department of Mining and Metallurgical Engineering, Amirkabir University of Technology, Tehran, I. R., Iran |
| |
Abstract: | Many scheduling problems, arising in the transportation industry, can be posed as massive set partitioning zero-one integer programmes. For reasons of computational complexity it is generally unrealistic to attempt to solve the model in this form using conventional integer linear programming. By the imposition of additional structure, derived from the real-world problem but not already implicit in the mathematical model, it is possible to significantly reduce the effects of computational complexity and provide an effective method of obtaining good feasible solutions.In this paper, recent results in graph theory concerning natural integer properties of set partitioning integer programmes are discussed. These results motivate the development of further implicit constraints which simultaneously reduce the dimensionality and increase the proportion of integer basic feasible solutions of the set partitioning linear programme. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|