Laboratoire de Génie Informatique et d’Automatique de l’Artois


Hybrid Approaches Combining Metaheuristics and Mathematical Programming for 0–1 mixed integer programming

Le 26 mai 2014 à 14h00 Salle des séminaires du LGI2A, FSA, Béthune
Said HANAFI Professeur University of Valenciennes, France

The 0–1 mixed integer programming (0–1 MIP) problem consists of maximizing or minimizing a linear function subject to equality or inequality constraints and binary choice restrictions on some of the variables. Several special cases of the 0-1 MIP problem, such as knapsack, traveling salesman and routing problems, are known to be NP-hard. Branch-and-bound and branch-and-cut methods have long been considered the methods of choice for solving mixed integer programming problems. Many contributions have led to successive improvements in these methods. Metaheuristic methods have attracted attention as possible alternatives or supplements to the more classical approaches. The view adopted in this talk is that metaheuristic approaches can benefit from a change of perspective in order to perform at their best in the MIP setting. Recent adaptive memory and evolutionarymetaheuristics for MIP have included proposals for introducing inequalities and target objectives to guide the search. These guidance approaches are useful in intensification and diversification strategies related to fixing subsets of variables at particular values, and in strategies that use linear programming to generate trial solutions whose variables are induced to receive integer values. Glover and Hanafi (2010) introduced procedures for generating target objectives and solutions by exploiting proximity in original space or projected space. In this talk, we will develop more advanced approaches for generating the target objective based on exploiting the mutually reinforcing notions of reaction and resistance. Model embedded memory, as proposed in parametric tabu search, will be integrated to provide a range of recency and frequency memory structures for achieving goals associated with short term and long term solution strategies. We propose supplementary linear programming models that exploit the new inequalities for intensification and diversification, and introduce additional inequalities from sets of elite solutions that enlarge the scope of these models.

References :

S. Hanafi, C. Wilbaut, (2011). Improved Convergent Heuristic for the 0–1 Multidimensional Knapsack Problem. Annals of Operations Research, Volume 183, Number 1, 125–142.
F. Glover, S. Hanafi, (2010). Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization Part II : Exploiting Reaction and Resistance. International Journal of Applied Metaheuristic Computing. Volume 2, No 1, pp. 1–17.