Data-driven decomposition and constraint customization for combinatorial optimization

Récemment, on a assisté à une montée en puissance des méthodes basées sur les données dans le domaine de l’optimisation. En général, la construction de modèles mathématiques pour un système implique d’obtenir des informations sur le système pour le modéliser. D’une part, l’émergence du big data motive l’utilisation des méthodes basées sur les données pour trouver les modèles latents des données, estimer les paramètres et construire des modèles d’optimisation. D’autre part, comme la disponibilité des données conduit à des modèles d’optimisation plus sophistiqués, il est nécessaire de développer des méthodes basées sur les données pour s’attaquer à la complexité de résolution de ces problèmes d’optimisation. Certaines études dans ce domaine s’appuient sur des techniques axées sur les données pour évaluer les paramètres des problèmes d’optimisation afin de détecter automatiquement les modèles sous-jacents. Elles tentent d’explorer la structure de la matrice des coûts ou de la matrice des contraintes et de trouver des modèles dans une classe spécifique de problèmes. L’utilisation de l’apprentissage automatique pour traiter directement les instances d’un problème d’optimisation est une autre application des méthodes basées sur les données dans le domaine de l’optimisation. La résolution de modèles d’optimisation par des approches d’apprentissage automatique et l’incorporation du problème d’optimisation dans l’étape d’apprentissage sont quelques exemples dans ce domaine. Dans cette thèse, nous tirons parti des techniques basées sur les données pour étudier et développer des méthodes de résolution de certains problèmes d’optimisation difficiles à résoudre. Les méthodes de décomposition sont utilisées dans la littérature de l’optimisation depuis de nombreuses années comme une alternative pour traiter les problèmes de grandes dimensions. La décomposition consiste à diviser un problème en sous-problèmes plus petits qui peuvent être résolus séparément. Dans deux chapitres de ce travail, nous étudions la décomposabilité de certains problèmes de Programmation Quadratique Binaire avec des contraintes linéaires par le biais d’une approche basée sur des méthodes basées sur les données. Nous étudions la structure des données relatives aux coûts quadratiques des Programmes Quadratiques Binaires et exploitons les modèles spécifiques liés au type de problème pour reformuler et convexifier les problèmes, et utiliser la décomposition pour les résoudre. La Programmation Quadratique Binaire est une classe de problèmes Optimisation Combinatoire avec des variables binaires et des fonctions objectifs quadratiques. Dans la première étude de la thèse, nous étudions la généralisation de la “reformulation en étoile” introduite pour le Problème d’Arbre Quadratique Adjacent Minimal dans la littérature pour d’autres problèmes de Programmation Quadratique Binaire simplement adjacents. Nous considérons deux problèmes de cette classe, le Problème d’Assignation Adjacent Semi Quadratique et le problème de Suivi d’Objets Multiples en vision artificielle pour démontrer l’efficacité de la reformulation en étoile. La deuxième étude de cette thèse est consacré à la proposition d’un cadre unifié combinant la reformulation en étoile et une approche de division des coûts pour reformuler les problèmes de Programmation Quadratique Binaire généraux. Dans cette approche, nous exploitons la structure du coût quadratique basée sur les coûts adjacents et les coûts non adjacents et fournissons une reformulation. Ainsi, nous tirons parti de la structure en étoile de la nouvelle reformulation pour développer un algorithme de Génération de Colonnes basé sur la décomposition. La composante quadratique du problème est traitée dans le problème principal de Génération de Colonnes et dans ses sous-problèmes. Dans nos expérimentations, nous évaluons les performances de la méthodologie sur différentes applications avec différentes structures quadratiques. La reformulation en étoile et la Génération de Colonnes sont plus performants que GUROBI en termes de borne duale et de temps de calcul dans presque tous les cas de problèmes de Programmation Quadratique Binaire adjacents. En outre, même une simple mise en oeuvre du cadre de fractionnement des coûts donne des résultats encourageants pour le Problème d’Assignation Semi Quadratique en tant qu’étude de cas, en particulier pour les instances avec des matrices quadratiques plus éparses. Dans le troisième essai, une approche basée sur les données est utilisée pour personnaliser les contraintes des modèles de Programmation Linéaire en Nombres Entiers Mixtes classiques afin de produire une solution qui est probablement réalisable en pratique sur la base des contraintes apprises à partir des solutions précédemment mises en oeuvre. Les décideurs de différents secteurs utilisent des logiciels d’optimisation pour la planification et la prise de décision. Cependant, dans de nombreuses applications réelles, ils personnalisent les solutions fournies par le logiciel sur la base de certaines règles et préférences opérationnelles internes implicites. Pour s’assurer que de telles considérations et contraintes cachées peuvent être systématiquement prises en compte sans nécessiter de connaissances explicites obtenues auprès d’experts humains, il est possible d’exploiter des méthodes basées sur les données pour intégrer des contraintes latérales dans des Programmes Linéaires en Nombres Entiers Mixtes classiques. Plutôt que de s’appuyer sur un simple modèle de régression linéaire proposé dans la littérature, nous étendons le cadre en incorporant la régression linéaire régularisée et les arbres de décision dans le modèle d’optimisation. Pour motiver la méthode, nous discutons de différentes combinaisons de règles dans le problème du sac à dos linéaire et binaire. En outre, nous présentons une approche pour traiter les cas programmation linéaire en nombres entiers mixtes 0-1 en intégrant un arbre de classification au lieu d’une régression linéaire. Nous abordons également des règles opérationnelles plus difficiles et utilisons le cadre dans une application pratique, le Problème de Roulement des Infirmières. Les solutions optimales obtenues par la méthode suggèrent que l’approche proposée peut apprendre les ajustements à partir des données et être plus efficace que les travaux antérieurs dans ce domaine dans des environnements complexes. MOTS-CLÉS : programmation quadratique binaire, optimisation combinatoire, génération de colonnes, problème de semi-affectation, problème de suivi d’objets multiples, personnalisation des contraintes, méthodes basées sur les données, programmation linéaire en nombres entiers mixtes, arbre de décision.

Abstract

Recently there has been a surge to benefit from data-driven methods in the field of optimization. Generally, constructing mathematical models for a system involves obtaining information from the system to model it. On the one hand, the emergence of big data motivates utilizing data-driven methods to find the latent patterns of the data, estimate the parameters, and build optimization models. On the other hand, since data availability leads to more sophisticated optimization models, it needs to develop data-driven methods to tackle the complexity of solving these optimization problems. Some of the studies in this field leverage data-driven techniques to appraise the parameters of the optimization problems to detect the underlying patterns automatically. They attempt to explore the structure of the cost matrix or constraint matrix and to find patterns in a specific class of problems. Using machine learning to address instances of an optimization problem directly is another application of data-driven methods in optimization. Solving optimization models through machine learning approaches and incorporating the optimization problem into the training step are some examples in this field. In this dissertation, we take advantage of data-driven techniques to study and develop solution methods to tackle some hard-to-solve optimization problems. Decomposition methods have been used in the optimization literature for many years as an alternative to address large-scale problems. Decomposition revolves around breaking a problem into smaller subproblems that are separately solvable. In two chapters of this work, we study the decomposability of some Binary Quadratic Programming (BQP) problems with linear constraints through a data-driven approach. We investigate the structure of the quadratic cost data of the BQPs and leverage the specific patterns related to the problem type to reformulate and convexify the problems, and use decomposition to solve them. BQP is a class of Combinatorial Optimization (CO) problems with binary variables and quadratic objective functions. In the first essay of the dissertation, we investigate the generalizability of the star-reformulation introduced for the Adjacent-only Quadratic Minimum Spanning Tree Problem (AQMSTP) in the literature for other adjacent-only BQP problems. We consider two problems of this class, the Adjacent-only Quadratic Semi-Assignment Problem (AQSAP) and the Multiple Object Tracking (MOT) problem in computer vision to demonstrate the efficiency of the star-based framework. The second essay of this dissertation is dedicated to suggesting a unified framework combining the star-reformulation and a cost-splitting approach to reformulate general BQP problems. In this approach, we exploit the structure of the quadratic cost based on the adjacent and nonadjacent costs and provide a reformulation. Hence, we leverage the star-based structure of the new reformulation to develop a decomposition-based Column Generation (CG) algorithm. The quadratic component of the problem is dealt with in the CG master problem and its subproblem. Our computational experiments evaluate the methodology’s performance on different applications with different quadratic structures. The star-reformulation and CG outperform GUROBI in terms of both dual bound and computational time in almost all instances of the adjacent-only BQP problems. Moreover, even a simple implementation of the cost-splitting framework demonstrates encouraging outcomes for Quadratic Semi-Assignment Problem (QSAP) as a case study, particularly for instances with sparser quadratic matrices. In the third essay, a data-driven approach is utilized to customize the constraints of classical Mixed Integer Linear Programming (MILP) models to produce a solution that is likely practically feasible based on the constraints learned from previously implemented solutions. Decision-makers in different industries use optimization software for planning and decisionmaking. However, in many real applications, they customize the solutions provided by the software based on some implicit internal operational rules and preferences. To ensure that such considerations and hidden constraints can be systematically considered without requiring explicit knowledge from human experts, one can leverage data-driven methods to embed side constraints in known classical MILPs. Rather than relying on a simple linear regression model proposed in the literature, we extend the framework by incorporating regularized linear regression and decision trees in the optimization model. To motivate the method, we discuss different combinations of rule settings in the linear and binary knapsack problem. Moreover, we demonstrate how we handle 0-1 MILP cases by embedding a classification tree instead of linear regression. We also address more challenging operational rules and employ the framework in a more realistic application, the Nurse Rostering Problem. The optimal solutions obtained by the method suggest that the proposed approach could learn the adjustments from the data and perform more effectively compared to the previous work in this area in complex settings. KEYWORDS: {binary quadratic programming, combinatorial optimization, column generation, semi-assignment problem, multiple object tracking problem, constraint customization, data-driven methods, mixed integer linear programming, decision tree}