Methods for Combinatorial Optimization and Their Applications

Combinatorial optimization is a fundamental area of mathematical optimization, dealing with problems that involve discrete structures and have a wide range of applications. As problem complexity grows, advancements in computational power, theoretical research, and innovative algorithmic frameworks have driven significant progress. This thesis examines combinatorial optimization methods across four key areas: integrality gaps, neural network training, stochastic optimization in healthcare, and energy management system optimization. First, the metric Steiner Tree problem is studied to investigate the integrality gap of linear programming relaxations. Lower bounds on the integrality gap of the bidirected cut formulation are established for small instances, and heuristic algorithms are developed to identify instances with large gaps. Additionally, structural insights and conjectures regarding the integrality gap are proposed. Second, combinatorial optimization techniques are applied to train few–bit neural networks, such as binarized and integer–valued networks. A multi–objective ensemble approach is introduced, improving robustness and sparsity and showcasing the potential of solver–based methods in low–data scenarios. This method is applied to different multiclassification problems. Next, a two–phase approach is developed for surgical scheduling, addressing uncertainties in surgery durations and emergency arrivals. Finally, distributionally robust optimization is applied to optimal power flow problems, coupled with an analysis of Jabr–like relaxations. The contribution of this thesis consists of presenting several complex problems, using their study as applications of diverse combinatorial optimization methods, highlighting the field’s adaptability.