Financement prévu Cofinancement éventuel

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
Titre : Financement prévu : Cofinancement éventuel : (Co)-Directeur de thèse : HANAFI Saïd (LAMIH/UVHC) E-mail : Co-directeur de thèse : GENDRON Bernard (CIRRELT/Canada) E-mail : Laboratoire : LAMIH UMR 8201 CNRS – Université de Valenciennes et du Hainaut Cambrésis Equipe ou Groupe de recherche : Projet de thèse en français Descriptif : Le problème de programmation en nombres entiers mixtes (MIP) consiste à optimiser (minimiser ou maximiser) une fonction linéaire sous des contraintes linéaires d'inégalité et/ou d'égalité, où certaines ou toutes les variables sont des entiers. De nombreux problèmes d'optimisation peuvent être modélisés comme un problème MIP. Les résultats de complexité n'ont pas encore définitivement identifié le niveau de difficulté de ces problèmes, mais des découvertes empiriques suggèrent que les ressources calculatoires requises pour résoudre certaines instances de problème MIP peuvent augmenter exponentiellement avec la taille du problème. Les méthodes de «Branch-and-bound» (B&B) et «branch-and-cut» (B&C) ont longtemps été considérées comme les méthodes de prédilection pour résoudre les problèmes de programmation en nombres entiers mixtes. Depuis plusieurs décennies beaucoup de contributions ont conduit à des améliorations successives de ces méthodes.

  • méthode

  • métaheuristiques

  • relaxation method

  • mip problems resist

  • hybridation de la relaxation lagrangienne avec la recherche

  • collaboration avec le centre interuniversitaire de recherche sur les réseaux d'entreprise

  • problèmes mip

  • convex hull


Publié le : mardi 19 juin 2012
Lecture(s) : 320
Source : univ-valenciennes.fr
Nombre de pages : 4
Voir plus Voir moins
Titre : Financement prévu :Cofinancement éventuel : (Co)-Directeur de thèse :HANAFI Saïd (LAMIH/UVHC)E-mail:said.hanafi@univ-valenciennes.frCo-directeur de thèse :GENDRON Bernard (CIRRELT/Canada)E-mail:Bernard.Gendron@cirrelt.caLaboratoire:LAMIH UMR 8201 CNRS – Université de Valenciennes et du Hainaut Cambrésis http://www.univ-valenciennes.fr/LAMIH/Equipe ou Groupe de recherche : Projet de thèse en françaisDescriptif : Le problème de programmation en nombres entiers mixtes (MIP) consiste à optimiser (minimiser ou maximiser) une fonction linéaire sous des contraintes linéaires d’inégalité et/ou d’égalité, où certaines ou toutes les variables sont des entiers. De nombreux problèmes d’optimisation peuvent être modélisés comme un problème MIP. Les résultats de complexité n’ont pas encore définitivement identifié le niveau de difficulté de ces problèmes, mais des découvertes empiriques suggèrent que les ressources calculatoires requises pour résoudre certaines instances de problème MIP peuvent augmenter exponentiellement avec la taille du problème. Lesméthodes de «Branch-and-bound» (B&B) et «branch-and-cut» (B&C) ont longtemps été considérées comme les méthodes de prédilection pour résoudre les problèmes de programmation en nombres entiers mixtes. Depuis plusieurs décennies beaucoup de contributions ont conduit à des améliorations successives de ces méthodes. Cependant, beaucoup de problèmes MIP résistent à la résolution par les meilleures méthodes courantes de B&B et B&C. Comme conséquence, les méthodes heuristiques ont attiré l’attention comme des alternatives possibles ou des compléments aux approches plus classiques. Aujourd’hui encore, le niveau d’effort consacré à développer de bonnes métaheuristiques pour les problèmes MIP est négligeable comparé à l’effort consacré à développer des versions raffinées des méthodes classiques. Le point de vue adopté dans cette thèse est que ces approches métaheuristiques peuvent bénéficier d’un changement de perspective pour améliorer les modèles MIP. La recherche dispersée est une métaheuristique évolutionnaire qui a été appliquée avec succès pour plusieurs problèmes d’optimisation depuis quelques années. Maintenir la diversité dans les métaheuristiques basées sur la population a toujours joué un rôle important dans leur efficacité.
Nous proposons l’utilisation de solutions partielles dans la recherche dispersée pour la programmation en nombres entiers 0-1 pour (i) donner plus de flexibilité aux générateurs de solutions et (ii) reporter la fixation des variables à 0 ou 1 dans une seconde phase. La Relaxation et la Recherche Dispersée produisent des bornes inférieure et supérieure respectivement sur la valeur optimale des problèmes de minimisation. Ces bornes encadrent la valeur optimale du problème original. Guignard a proposé une méthode appelée «relax and cut » pour restreindre les bornes Lagrangiennes en identifiant les coupes qui sont violées par la solution Lagrangienne courante, et en les dualisant. Pour réduire l’écart résiduel nous proposerons une hybridation de la relaxation Lagrangienne avec la recherche dispersée. Enfin, nous introduirons un processus d’intensification qui renforce la recherche en ajoutant des pseudo-coupes pour réduire l’espace de recherche. Notre approche sera validée sur des variantes du problème de sac à dos. RécemmentGuignard et Ahlatcioglu (2010) ont introduit une méthode de «Relaxation Hull Convexe» pour calculer à la fois une borne inférieure sur la valeur optimale d’un programme de minimisation en nombres entiers non linéaires (NLIP) et de bonnes solutions réalisables. Ils ont montré que la borne inférieure peut être calculée en utilisant n’importe quelle version de décomposition simpliciale avec des sous-problèmes qui ont les mêmes contraintes que le NLIP mais avec des fonctions objectives linéaires. Nous travaillerons sur l’intégrationde laMéthode de Relaxation Hull Convexe dans la relaxation itérative basée sur des heuristiques proposée par Hanafi et Wilbaut (2009). Le projet de thèse se fera en collaboration avec le Centre interuniversitaire de recherche sur les réseaux d'entreprise, la logistique et le transport(CIRRELT), (Professeur Bernard Gendron directeur du CIRRELT). Enfin, toujours dans un contexte international, un stage (d’au moins 3 mois) à Wharton School (University of Pennsylvania)est envisagé, pour collaborer avec le professeur Monique Guignard. Projet de thèse en anglaisThe 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, set packing, cutting and packing, network design, protein alignment, travelling salesman and routing problems, are known to be NP-hard. Branch-and-bound (B&B) and branch-and-cut (B&C) 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 It remains true, however, that many MIP problems resist solution by the best current B&B and B&C methods. As a consequence, metaheuristic methods have attracted attention as possible alternatives or supplements to the more classical approaches. Yet to date, the amount of effort devoted to developing good metaheuristics for MIP problems is almost negligible compared to the effort being devoted to developing refined versions of the classical methods. The view adopted in this project is that metaheuristic approaches can benefit from a change of perspective in order to perform at their best in the MIP setting.
Scatter search is an evolutionary metaheuristic which has been successfully applied to several optimization problems for a few years. Maintaining diversity in population–based metaheuristics has always played an important role on their efficiency. We propose to use partial solutions in scatter search for 0–1 integer programming to (i) give more flexibility to the solution generators and (ii) postpone setting the variables to 0 or 1 to a second phase. Relaxation and SS produce lower and upper bounds respectively on the optimal value of minimizing MIP problems. These bounds provide intervals bracketing the optimal value of the original problem. Guignard proposed relax-and-cut method to 'strengthen' the Lagrangean bounds by identifying cuts which are violated by the current Lagrangean solution, and dualizing them. To reduce the residual gap we will propose an hybridation of the Lagrangean relaxation with scatter search. Finally, we will introduce an intensification process that reinforces the search by adding pseudo-cuts to reduce the search space. Our approach will be validated on a variant of the knapsack problem. Recently Guignard and Ahlatcioglu (2010) introduced a Convex Hull Relaxation method for computing both a lower bound on the optimal value of a nonlinear integer minimization program (NLIP), and good integer feasible solutions. They showed that the lower bound can then be computed using any version of simplicial decomposition, with sub-problems that have the same constraints as the NLIP, but with linear objective functions. We will work on the integration of the Convex Hull Relaxation method into the iterative heuristics based relaxation proposed by Hanafi and Wilbaut (2011). The thesis will be done in collaboration with the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) (Professor Bernard Gendron). It is also intended for the candidate to do a period (at least 3 months) at the Wharton School (University of Pennsylvania) to collaborate with Professor Monique Guignard. Le candidat doit avoir un très bon niveau en optimisation combinatoire, incluant les métaheuristiques et la programmation mathématique. The candidate needs a strong knowledge in combinatorial optimization field including metaheuristics and mathematical programming. French language is not necessary. References -Chouman M., Crainic T.G., Gendron B., ``Revue des inégalités valides pertinentes aux problèmes de conception de réseaux'', INFOR 41, 5-33, 2003. -Crainic T.G., Frangioni A., Gendron B., ``Bundle-Based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems'', Discrete Applied Mathematics 112, 73-99, 2001.
-Croxton K.L., Gendron B., Magnanti T.L., ``A Comparison of Mixed-Integer Programming Models for Non-Convex Piecewise Linear Cost Minimization Problems'', Management Science 49, 1268-1273, 2003. -Gendron B., Potvin J.-Y., Soriano P., ``Diversification Strategies in Local Search for a Nonbifurcated Network Loading Problem'', European Journal of Operational Research 142, 231-241, 2002. -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. -M. Guignard (1998). Efficient cuts in Lagrangean 'Relax-and-Cut' schemes. European Journal of Operational Research 105, pp. 216-223. -M. Guignard, A. Ahlatcioglu (2010). The Convex Hull Relaxation for Nonlinear Integer Programs with Convex Objective and Linear Constraints. Report, OPIM Department, The Wharton School, University of Pennsylvania. -S. Hanafi, C. Wilbaut, (2008). Scatter search for the 0-1 multidimensional knapsack problem, Journal of Mathematical Modelling and Algorithms, 7(2), pp. 143-159. -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. -C. Wilbaut, S. Elaoud, I. Crévits, S. Hanafi (2009). Diversification Generators for Partial Solutions in Scatter Search. MIC 2009: the VIII Metaheuristics International Conference, Hamburg (Allemagne), juillet.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.