Exploiting nested inequalities and surrogate constraints |
| |
Authors: | Saïd Hanafi Fred Glover |
| |
Institution: | 1. Laboratoire d’Automatique, de Mécanique et d’Informatique Industrielles et Humaines, UMR CNRS 8530, Groupe Recherche Opérationnelle et Informatique, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, 59313 Valenciennes Cedex, France;2. Leeds School of Business, University of Colorado, Boulder, CO 80309-0419, United States |
| |
Abstract: | The exploitation of nested inequalities and surrogate constraints as originally proposed in Glover Glover, F., 1965. A multiphase-dual algorithm for the zero–one integer programming problem. Operations Research 13, 879–919; Glover, F., 1971. Flows in arborescences. Management Science 17, 568–586] has been specialized to multidimensional knapsack problems in Osorio et al. Osorio, M.A., Glover, F., Hammer, P., 2002. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. Annals of Operations Research 117, 71–93]. We show how this specialized exploitation can be strengthened to give better results. This outcome results by a series of observations based on surrogate constraint duality and properties of nested inequalities. The consequences of these observations are illustrated by numerical examples to provide insights into uses of surrogate constraints and nested inequalities that can be useful in a variety of problem settings. |
| |
Keywords: | Integer programming Nested cuts Multidimensional knapsack problem Surrogate constraints |
本文献已被 ScienceDirect 等数据库收录! |
|