Experiments in mixed-integer linear programming using pseudo-costs |
| |
Authors: | J. -M. Gauthier G. Ribière |
| |
Affiliation: | (1) Program Product Center, IBM-France, Paris, France |
| |
Abstract: | This paper discusses heuristic branch and bound methods for solving mixed integer linear programming problems. The research presented on here is the follow on to that recorded in [3].After a resumé of the concept of pseudo-costs and estimations, new heuristic rules for generating a tree which make use of pseudo-costs and estimations are presented. Experiments have shown that models having a low percentage of integer variables behave in a radically different way from models with a high percentage of integer variables. The new heuristic rules seem to apply generally to the first type of model.Later, other heuristic rules are presented that are used with models having a high percentage of integer variables and with models having a special structure (models including special ordered sets.)The rules introduced here have been implemented in the IBM Mathematical Programming System Extended/370. They are used to solve large mixed integer linear programming models.Numerical results that permit comparisons to be made among the different rules are provided and discussed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|