Machine learning and combinatorial methods for discrete optimization problems

Combinatorial optimization is a central field of discrete mathematics, concerned with finding optimal solutions to problems over combinatorial structures such as graphs or set systems. However, while classical combinatorial optimization assumes complete knowledge of all problem parameters, real-world applications often include uncertainty. Among the most important problems in this field are parallel machine scheduling problems and network flow problems, which have attracted sustained research in operations research and computer science for over half a century. In this thesis, we develop and implement algorithms for variants of these two important classes of problems. Scheduling problems, with their elegant and often minimalistic formulations make them ideal test environment for algorithm development, while they remain highly relevant to real-world domains such as manufacturing, communications, and healthcare. In most practical settings, uncertainty is the rule rather than the exception. With the rise of the digital era, stochastic information can often be inferred from the abundance of available data. This motivates the study of stochastic scheduling on parallel machines in the first part of this thesis. First, we consider one of the most important real-world applications: elective surgery planning in hospitals with shared operating rooms for both elective and emergency patients. The problem is divided into two phases: offline and online. In the offline phase, elective patients are selected, assigned to operating blocks, and given tentative start times. The online phase includes inserting emergency surgeries as they arrive and may postpone or cancel elective ones. The objective is to minimize expected total costs related to patient assignment, waiting times, surgery cancellations, and resource overtime and idle time. We model the offline phase as a two-stage stochastic program and approximate second-stage costs using a convex piecewise linear surrogate model. This results in a mixed-integer program which can be solved very quickly even for large instances. For the online phase, we propose a greedy policy. Simulations show that our approach can reduce expected costs by up to 30% compared to heuristic methods. In recent years, there has been growing interest from both the research community and industry in applying machine learning to scheduling problems. Motivated by this trend, we next apply a machine learning method to the stochastic scheduling problem in an unrelated parallel machine environment. The overall goal is to find a scheduling policy that minimizes the expected value of a cost function combining three classic objectives: weighted job tardiness, weighted machine tardiness, and makespan. We use supervised learning to train a neural network on instances solved to optimality via dynamic programming. Different representations of the stochastic information are explored during the training. The results show that the neural network policy outperforms state-of-the-art heuristics, achieving expected costs within about 1% of the true optimal policy. Additionally, the learned policy generalizes well to instances with different job duration distributions and larger problem sizes. Networks are an integral part of modern life, forming the backbone of the countless systems on which we rely daily. Network flow models cover a wide range of real-world applications; however, in many cases, splitting a commodity across multiple paths can often degrade service quality, increase operational complexity, or even be impractical. This gives rise to the need to study the unsplittable flow problem. The second part of this thesis will focus on unsplittable flow problems in digraphs. We begin with the integer and unsplittable multiflow problem in series-parallel digraphs. An unsplittable multiflow routes the demand for each commodity along a single path from its source to its sink node. As one of our main results, we prove that any multiflow in a series-parallel digraph can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. For the special case of series-parallel digraphs, this confirms a long-standing conjecture by Goemans and a stronger one by Skutella, even for general multiflows where commodities have different source and sink nodes. We also show strong integrality results for multiflows on series-parallel digraphs, showing their computation can be reduced to a simple single-commodity flow problem. We next study a variant of the unsplittable multiflow problem, namely the single-source unsplittable flow problem in general digraphs, where the demand of each commodity must be routed along a single path from a common source node to its respective sink node. We present an alternative algorithm to the one introduced by Goemans, based on the concept of residual networks. This algorithm also serves as the foundation for a heuristic method aimed at solving a more challenging variant of the problem, recently proposed by Skutella, which requires simultaneously satisfying both upper and lower bounds on arc flow values. We evaluate the heuristic on various sets of randomly generated instances. The results show that our method performs well across all sets, successfully solving most instances.

Author dc:creator

• Majthoub Almoghrabi, Mohammed

Advisor dc:contributor.advisor

• Skutella, Martin

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc/4.0/

Language dc:language.iso

en

Identifier URI

https://doi.org/10.14279/depositonce-24997

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/26169