OUZIA Hacène
Direção de pesquisa : Michel MINOUX
Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications
Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P).
Tout d'abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d'une relaxation L&P pour qu'elle coïncide avec celle d'une relaxation SRL*.
Nous montrons aussi que toute relaxation S&A s'obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2.
Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité.
Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d'utiliser des relaxations L&P partielles.
Mots clés : Programmation en nombres entiers mixtes, Relaxation SRL, Optimisation combinatoire, Programmation disjonctive, Lift-and-Project, Relaxations RLT, Optimisation pseudo booléenne, Problème Max-SAT.
Defesas : 23/10/2008
Membros da banca :
A. R. Mahjoub, Professeur, Université Paris Dauphine (Rapporteur)
G. Cornuéjols, Professeur, Carnegie Mellon University (Rapporteur)
M. Minoux, Professeur, Université Paris 6 (Directeur de thèse)
P. Perny, Professeur, Université Paris 6 (Président du jury)
P. Bonami, Chargé de recherche CNRS au LIF, Marseille (Examinateur)
V. H. Nguyen, Maître de conférences, Université Paris 6 (Examinateur)
Publicações 2004-2024
-
2024
- H. Ouzia : “Partial reformulation-linearization based optimization models for the Golomb ruler problem”, RAIRO - Operations Research, vol. 58 (4), pp. 3171-3188, (EDP Sciences) (2024)
-
2023
- H. Ouzia, R. Vicente Pinto, N. Maculan : “A New Second-Order Conic Optimization Model for the Euclidean Steiner Tree Problem in R^d”, International Transactions in Operational Research, (Wiley) (2023)
-
2021
- H. Ouzia, N. Maculan : “Mixed Integer Nonlinear Optimization Models for the Euclidean Steiner Tree Problem in R”, Journal of Global Optimization, (Springer Verlag) (2021)
-
2019
- Th. Hilaire, H. Ouzia, B. Lopez : “Optimal Word-Length Allocation for the Fixed-Point Implementation of Linear Filters and Controllers”, ARITH 2019 - IEEE 26th Symposium on Computer Arithmetic, Kyoto, Japan, pp. 175-182, (IEEE) (2019)
-
2018
- R. Costa Dias, L. Santos, H. Ouzia, R. Schledjewski : “Improving degree of cure in pultrusion process by optimizing die-temperature”, Materials Today Communications, vol. 17, pp. 362-370, (Elsevier) (2018)
-
2016
- R. Costa Dias, H. Ouzia, A. Schledjewski : “Optimization of die-temperature in pultrusion of thermosetting composites for improved cure”, International Conference on Swarm Intelligence Based Optimization (ICSIBO 2016), Mulhouse, France (2016)
- M. S. Ibrahim, N. Maculan, H. Ouzia : “An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs”, RAIRO - Operations Research, vol. 50 (3), pp. 665-675, (EDP Sciences) (2016)
-
2015
- H. Ouzia : “Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs”, Advances in Operations Research, vol. 2015, pp. 784817, (Hindawi Publishing Corporation) (2015)
-
2014
- H. Ouzia : “Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs”, International Symposium on Combinatorial Optimization, Lisbon, Portugal (2014)
-
2010
- M. Minoux, H. Ouzia : “DRL*: A Hierarchy of Strong Block-Decomposable Linear Relaxations for 0-1 MIPs”, Discrete Applied Mathematics, vol. 158 (18), pp. 2031-2048, (Elsevier) (2010)
- M. Minoux, H. Ouzia : “Using DRL* relaxations for quadratically constrained pseudoboolean optimization: application to robust Min-Cut”, Electronic Notes in Discrete Mathematics, vol. 36, pp. 1217-1224, (Elsevier) (2010)
-
2008
- H. Ouzia : “Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications”, tese, defesas 23/10/2008, direção de pesquisa Minoux, Michel (2008)
- M. Minoux, H. Ouzia : “On Connections between RLT and Lift-and-Project Relaxations for Ranks 2 and more”, INFORMS annual meeting, Washington, United States (2008)
-
2004
- H. Ouzia, S. Haddadi : “Effective Algorithm and Heuristic for the Generalized Assignment Problem”, European Journal of Operational Research, vol. 153 (1), pp. 184-190, (Elsevier) (2004)