Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 32-41

Igor, Crévits , Saïd, Hanafi , Raïd, Mansi , Christophe, Wilbaut

Recently several hybrid methods combining exact algorithms and heuristics have been proposed for solving hard combinatorial optimization problems. In this paper, we propose new iterative relaxation-based heuristics for the 0–1 Mixed Integer Programming problem (0–1 MIP), which generate a sequence of lower and upper bounds. The upper bounds are obtained from relaxations of the problem and refined iteratively by including pseudo-cuts in the problem. Lower bounds are obtained from the solving of restricted problems generated by exploiting information from relaxation and memory of the search process. We propose a new semi-continuous relaxation (SCR) that relaxes partially the integrality constraints to…