Data-driven combinatorial optimization
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
Combinatorial optimization problems, particularly those within the NP-hard and NP-complete classes, pose significant challenges due to their believed intractability in polynomial time. Traditional approaches, such as integer programming, which can be computationally expensive, and hand-crafted heuristics, which require substantial expert effort to approximate near-optimal solutions, overlook that often problem instances and their solutions stem from the same data distribution. In contrast, data-driven approaches exploit this insight and have demonstrated their effectiveness in tackling combinatorial optimization problems by leveraging previous observations to solve new problems arising from the same data distribution. This dissertation presents three novel contributions to the field of data-driven combinatorial optimization, addressing fairness and privacy in selection problems, proposing vision-based neural solvers, and introducing and solving a prototype problem called query-decision regression with task shift. ☐ The predict-then-optimize paradigm plays a crucial role in data-driven combinatorial optimization. This paradigm use learning methods to predict some middle values, then these predicted values are used to optimize an objective function. While social aspects and responsible AI considerations have been widely explored in the predictive models, their integration within the predict-then-optimize paradigm has been limited. ☐ One fundamental combinatorial optimization problem that can be effectively solved using the predict-then-optimize framework is the selection problem, where ensuring social aspects is of paramount importance. In this work, we adopt the selection problem as a representative example that can be addressed through predict-then-optimize and explore the integration of fairness and privacy into the setting. We propose novel algorithms for data-driven selection problem that effectively satisfy fairness and privacy constraints while maintaining high accuracy. Our approach achieves a trade-off between optimizing for efficiency and satisfying ethical considerations, with only a minimal compromise in performance. ☐ In the second work, we draw inspiration from the intrinsic visual perception of humans when solving simple combinatorial optimization problems on graphs. This prompts us to investigate whether computer vision techniques can be adapted to solve more complex graph optimization problems. Remarkably, we successfully tackle the Hamiltonian cycle problem by learning to make decisions based on graph visualizations, outperforming state-of-the-art matrix-based methods such as graph transformers. Building upon this success, we explore the emerging paradigm of decision-focused learning in data-driven combinatorial optimization. In contrast to the traditional predict-then-optimize approach, which treats prediction and optimization as separate steps, decision-focused learning integrates these two components into a unified end-to-end framework. Recognizing the proven success of decision-focused learning in real-world applications, we frame our vision-based neural solver within this paradigm. Interestingly, we discover that the common interpolation functions used in computer vision can serve as natural surrogate functions for having a differentiable end-to-end framework. This eliminates the need for meticulous design efforts typically required by existing methods in the decision-focused learning framework to achieve a differentiable end-to-end framework, highlighting the potential of our approach as a powerful tool in data-driven combinatorial optimization. To evaluate the effectiveness and performance of our vision-based neural solver, we conduct experiments on a diverse set of graph optimization tasks. The results consistently demonstrate the superiority of our approach, validating its ability to effectively solve complex graph optimization problems. ☐ Finally, we introduce a novel problem called query-decision regression with task shift (QRTS), which extends the concept of query-decision regression, a data-driven approach to solving combinatorial optimization problems. The objective of QRTS is to solve an optimization problem on a graph with unknown weights by leveraging information from a related optimization problem. ☐ To establish the theoretical foundation of QRTS, we provide formal proofs demonstrating its feasibility. This groundbreaking result opens up a new avenue for data-driven combinatorial optimization, as it suggests that we can translate the optimization results from one problem to another when they share the same unknown data distribution. ☐ To evaluate the practical applicability of our proposed method, we focus on two combinatorial optimization problems: the shortest path problem and the minimum spanning tree problem. Through extensive experiments, we gather compelling evidence that supports the feasibility of solving QRTS. ☐ Overall, this dissertation advances the field of data-driven combinatorial optimization by addressing critical and diverse challenges and introducing groundbreaking approaches. By incorporating fairness and privacy considerations, developing vision-based neural solvers, and exploring the feasibility of query-decision regression with task shift, this dissertation paves the way for more efficient, responsible, and adaptable directions in data-driven combinatorial optimization problems.
Description
Keywords
Combinatorial optimization, Computer vision, Decision-focused learning, Fairness, Privacy, Query-decision regression