Essays in Mixed-Integer Nonlinear Optimization for Matching Applications

Wiratchotisatian, Pitchaya

Etd

Essays in Mixed-Integer Nonlinear Optimization for Matching Applications

Public

Mixed-integer optimization (MIO) has seen widespread use in solving challenging decision problems due to its expressivity and ability to characterize constrained decisions under an objective function to be optimized. Advances in algorithmic development and computing over the past several decades have seen profound increases in the potential of commercial optimization solvers. Even so, many real-world problems are nonconvex and nonlinear and representing vexing challenges to be tackled using MIO solvers. The focus of this dissertation is on combining MIO and associated techniques together with machine learning to tackle difficult assignment and matching problems. First, we study the maximum a-posteriori (MAP) estimation problem for the Gaussian mixture model using mixed-integer nonlinear optimization. In this work, we linearize the nonlinear objective function components using both McCormick relaxations and piecewise linear approximations, which can represent the nonlinearities to within any degree of accuracy. We then seek to accelerate solving this NP-hard optimization problem through a custom Branch and Bound (B\&B) algorithm considering multiple branching strategies. Specifically, the branching process of each node represents the fixing of data point(s) based on its integrality. We examine the computational efficiency of our methods, as well as the quality of the generated solutions, and compare with standard machine learning methods for solving the MAP problem. Second, we propose a decision support system for IT services to ensure that the right tickets get to the right technicians, resulting in improved use of resources. The system embeds machine learning techniques to classify incoming tickets according to service categories, and subsequently uses mixed-integer optimization to assign tickets to technicians based on the service category, available technician capacity, and their skill sets. Computational performance on real-sized data sets reveal that our methods can efficiently assign tickets to technicians. Third, we study many-to-one matching problems with incomplete preference lists and ties using integer optimization. We study the classical concepts of stability in many-to-one matchings from unique vantage points and so introduce new stability representations, and create algorithms to enhance the computational performance of the forms we introduce. Because there are multiple objective of interest, we lexicographically construct a master objective function that combines each objective component in a strict ordering. Moreover, we study the creation of cohorts to ensure balanced teams according to desirable attributes at project centers. We conduct comprehensive experiments on both simulated data and real data from the WPI student-to-project-center matching process to study the computational performance of our proposed methods and compare them with the extant literature. The final work in this dissertation explores the solution of a class of integer optimization problems with polynomial objective functions (polynomial integer nonlinear optimization, or PINLO) that is featured in the third work. We introduce a theoretical reformulation that can linearize polynomial functions of separable and bounded integer variables of any degree, and compare it with an alternative reformulation. Computational experiments reveal that our integer linear optimization (ILO) reformulation is computationally tractable for solving large PINLO problems via Gurobi (up to 10,000 constraints and 20,000 variables). This is much larger than current leading commercial global optimization solvers such as BARON, thereby demonstrating its promise for use in real-world applications of integer linear optimization with a polynomial objective function.

Creator