Authors: Hanafi, Saïd
Lazić, Jasmina
Mladenović, Nenad 
Wilbaut, Christophe
Crévits, Igor
Title: Hybrid variable neighbourhood decomposition search for 0-1 mixed integer programming problem
Journal: Electronic Notes in Discrete Mathematics
Volume: 36
Issue: C
First page: 883
Last page: 890
Issue Date: 1-Aug-2010
ISSN: 1571-0653
DOI: 10.1016/j.endm.2010.05.112
In this paper we propose new hybrid heuristics for the 0-1 mixed integer programming problem, based on the variable neighbourhood decomposition search principle and on exploiting information obtained from a series of relaxations. In the case of a maximization problem, we add iteratively pseudo-cuts to the problem in order to produce a sequence of lower and upper bounds of the problem, so that integrality gap is reduced. We validate our approaches on the well-known 0-1 multidimensional knapsack problem, in which the general-purpose CPLEX MIP solver is used as a black box for solving subproblems generated during the search process. The results obtained with these methods are comparable with the current state-of-the-art heuristics on a set of large scale instances.
Keywords: 0-1 Mixed Integer Programming | Multidimensional Knapsack Problem | Variable Neighbourhood Search
Publisher: Elsevier

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.