|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||Abstract:||
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 Mar 19, 2023
checked on Mar 20, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.