Skip to Main content Skip to Navigation
Journal articles

New convergent heuristics for 0–1 mixed integer programming

Abstract : 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:44:34 AM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM


Wilbaut et Hanafi - 2009 - New...
Publisher files allowed on an open archive




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



Record views


Files downloads