New convergent heuristics for 0–1 mixed integer programming - Université Polytechnique des Hauts-de-France Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2008

New convergent heuristics for 0–1 mixed integer programming

Résumé

Several hybrid methods have recently been proposed for solving 0-1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0-1 multidimensional Knapsack problem. Other encouraging results obtained for 0-1 MIP problems are also presented.
Fichier principal
Vignette du fichier
Wilbaut et Hanafi - 2009 - New convergent heuristics for 0–1 mixed integer pr.pdf (242.51 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03723751 , version 1 (15-07-2022)

Identifiants

Citer

Christophe Wilbaut, Said Hanafi. New convergent heuristics for 0–1 mixed integer programming. European Journal of Operational Research, 2008, 195, pp.62 - 74. ⟨10.1016/j.ejor.2008.01.044⟩. ⟨hal-03723751⟩
7 Consultations
144 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More