Une approche exacte de résolution de problèmes de pooling appliquée à la fabrication d’aliments Manuel Ruiz To cite this version: Manuel Ruiz. Une approche exacte de résolution de problèmes de pooling appliquée à la fabrication d’aliments. Génie des procédés. Université de Grenoble, 2013. Français. ￿NNT: 2013GRENI030￿. ￿tel-00992383￿ HAL Id: tel-00992383 https://theses.hal.science/tel-00992383 Submitted on 17 May 2014 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. THÈSE Pourobtenirlegradede DOCTEUR DE L’UNIVERSITÉ DE GRENOBLE Spécialité: GénieIndustriel Arrêtéministériel:7aôut2006 Présentéepar Manuel Ruiz ThèsedirigéeparBernardPenz etcoencadréeparOlivierBriant préparéeausein dulaboratoireG-SCOP 2 etdel’écoledoctoraleI-MEP Une approche exacte de résolution de problèmes de pooling appliquée à la fabrication d’aliments Thèsesoutenuepubliquementle, devantlejurycomposéde: Philippe Mahey Professeur,UniversitéBlaisePascalClermontII,Présidentproposé Leo Liberti Professeur,ÉcolePolytechnique,Rapporteur Frédé´ric Messine Maître de Conférences Habilité à Diriger les Recherches, Institut de Recherche enInformatiquedeToulouse,Rapporteur Bernard Penz Professeur,InstitutPolytechniquedeGrenoble,Directeurdethèse Olivier Briant Maitre de conférences, Institut Polytechnique de Grenoble, Co-Encadrant de thèse Jean-Maurice Clochard DirecteurtechniquedeA-Systems,Versailles,Co-Encadrantdethèse Table des matières Table des matières i Table des figures vii Liste des tableaux ix Introduction 1 1 La fabrication d’aliments pour bétail 3 1.1 Le contexte métier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 La formulation d’aliments . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Les contraintes métiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 La formulation simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Le problème de fabrication directe . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Les notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 La modélisation mathématique . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.4 La résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 i TABLE DES MATIÈRES 1.3 La formulation avec pré-mélanges . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1 Une fabrication à deux niveaux de mélange . . . . . . . . . . . . . . . . . 9 1.3.2 Les notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.3 La modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.4 La résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Revue de la littérature sur les problèmes de pooling et les méthodes de résolution 15 2.1 Définitions et modélisation des problèmes de pooling . . . . . . . . . . . . . . . 15 2.1.1 Exemple historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Définition formelle du pooling standard et quelques extensions . . . . . . 17 2.1.3 Les deux principales formulations du pooling standard . . . . . . . . . . . 18 2.1.4 Les applications des problèmes de pooling . . . . . . . . . . . . . . . . . . 20 2.2 Notations utilisées pour décrire les méthodes de la littérature . . . . . . . . . . . 21 2.3 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1 Les méthodes basées sur les Branch-and-Bound . . . . . . . . . . . . . . 25 2.3.2 Les méthodes de type décomposition de Benders . . . . . . . . . . . . . 27 2.3.3 L’algorithme Global OPtimization (GOP) . . . . . . . . . . . . . . . . . 29 2.4 Les méthodes de calcul de solutions réalisables . . . . . . . . . . . . . . . . . . . 32 2.5 Les méthodes de calcul de bornes inférieures . . . . . . . . . . . . . . . . . . . . 33 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 ii TABLE DES MATIÈRES 3 Un approche de résolution par Branch-and-Bound 39 3.1 Description générale de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.1 Notations allégées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.1.2 Schéma de principe pour l’algorithme . . . . . . . . . . . . . . . . . . . 41 3.2 Les techniques de contraction de bornes utilisées . . . . . . . . . . . . . . . . . . 43 3.2.1 Réduction du domaine réalisable . . . . . . . . . . . . . . . . . . . . . . 43 3.2.2 Réduction du domaine en utilisant une relaxation . . . . . . . . . . . . . 46 3.3 Calcul de la borne inférieure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.3.1 Amélioration de la convexification des termes bilinéaires . . . . . . . . . 47 3.3.2 Génération de coupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3.3 La linéarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.4 Alternate pour la recherche de solutions réalisables . . . . . . . . . . . . . . . . 51 3.5 La stratégie de branchement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.6 Deux formulations pour notre problème : FP et RFP . . . . . . . . . . . . . . . 54 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4 Implémentation et test 57 4.1 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.2 Génération d’instances à partir de données industrielles . . . . . . . . . . . . . . 58 4.2.1 Distribution des matières premières et des caractéristiques . . . . . . . . 59 4.2.2 Construction d’une solution de référence . . . . . . . . . . . . . . . . . . 59 iii TABLE DES MATIÈRES 4.2.3 Génération des contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Résultats obtenus sur les instances industrielles . . . . . . . . . . . . . . . . . . 62 4.3.1 Comparaison du calcul des bornes inférieures pour FP et RFP . . . . . . 62 4.3.2 Calibrage d’Alternate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.3 Comparaison des performances de notre approche avec Couenne pour les instances industrielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 Résultats obtenus sur des instances générales de fabrication d’aliment . . . . . . 65 4.5 Résultats obtenus sur les instances de pooling standard . . . . . . . . . . . . . . 67 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5 Le problème de fabrication 71 5.1 Définition du problème et génération d’instances . . . . . . . . . . . . . . . . . . 71 5.2 L’approche Branch-and-Bound générique . . . . . . . . . . . . . . . . . . . . . . 74 5.2.1 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2.2 La limite de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 Une approche lagrangienne pour le calcul d’une borne inférieure . . . . . . . . . 77 5.3.1 Définition de nouveaux ensembles . . . . . . . . . . . . . . . . . . . . . . 77 5.3.2 Une relaxation lagrangienne . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.3.3 Définition des générateurs . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3.4 Simplification de la relaxation lagrangienne . . . . . . . . . . . . . . . . . 81 5.4 Calcul de la borne lagrangienne . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.4.1 Les algorithmes utilisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 iv TABLE DES MATIÈRES 5.4.2 Initialisation de la procédure . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.5.1 L(FP), L(RFP) et l’approche lagrangienne . . . . . . . . . . . . . . . . 84 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Conclusion et perspectives 87 Annexe 1 : Résultat sur les instances de fabrications d’aliments 89 Annexe 2 : Résultat sur les instances de pooling standard 93 Bibliographie 95 v Table des figures 1.2.1 Un exemple d’aliment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Le problème de pooling standard Haverly 1 . . . . . . . . . . . . . . . . . . . . 16 3.3.1 Plus petit ensemble convexe contenant l’hyperboloïde . . . . . . . . . . . . . . 48 vii