Rethinking and Benchmarking Predict-then-Optimize Paradigm for Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2311.07633v2
• Date: Sun, 19 Nov 2023 05:36:04 GMT
• Title: Rethinking and Benchmarking Predict-then-Optimize Paradigm for Combinatorial Optimization Problems
• Authors: Haoyu Geng, Hang Ruan, Runzhong Wang, Yang Li, Yang Wang, Lei Chen, Junchi Yan
• Abstract summary: Many web applications rely on solving optimization problems, such as energy cost-aware scheduling, budget allocation on web advertising, and graph matching on social networks. We consider the performance of prediction and decision-making in a unified system. We provide a comprehensive categorization of current approaches and integrate existing experimental scenarios.
• Score: 62.25108152764568
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Numerous web applications rely on solving combinatorial optimization problems, such as energy cost-aware scheduling, budget allocation on web advertising, and graph matching on social networks. However, many optimization problems involve unknown coefficients, and improper predictions of these factors may lead to inferior decisions which may cause energy wastage, inefficient resource allocation, inappropriate matching in social networks, etc. Such a research topic is referred to as "Predict-Then-Optimize (PTO)" which considers the performance of prediction and decision-making in a unified system. A noteworthy recent development is the end-to-end methods by directly optimizing the ultimate decision quality which claims to yield better results in contrast to the traditional two-stage approach. However, the evaluation benchmarks in this field are fragmented and the effectiveness of various models in different scenarios remains unclear, hindering the comprehensive assessment and fast deployment of these methods. To address these issues, we provide a comprehensive categorization of current approaches and integrate existing experimental scenarios to establish a unified benchmark, elucidating the circumstances under which end-to-end training yields improvements, as well as the contexts in which it performs ineffectively. We also introduce a new dataset for the industrial combinatorial advertising problem for inclusive finance to open-source. We hope the rethinking and benchmarking of PTO could facilitate more convenient evaluation and deployment, and inspire further improvements both in the academy and industry within this field.

Related papers

• A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization [4.703514158152835]
  Bilevel has recently attracted significant attention in machine learning due to its wide range of applications and advanced hierarchical optimization capabilities.<n>We propose a plug-and-play framework named BO for developing and analyzing bilevel optimization methods.
  arXiv  Detail & Related papers  (2025-05-02T13:26:43Z)
• A Survey of Direct Preference Optimization [103.59317151002693]
  Large Language Models (LLMs) have demonstrated unprecedented generative capabilities. Their alignment with human values remains critical for ensuring helpful and harmless deployments. Direct Preference Optimization (DPO) has recently gained prominence as a streamlined alternative.
  arXiv  Detail & Related papers  (2025-03-12T08:45:15Z)
• Preference Optimization via Contrastive Divergence: Your Reward Model is Secretly an NLL Estimator [32.05337749590184]
  We develop a novel PO framework that provides theoretical guidance to effectively sample dispreferred completions. We then select contrastive divergence (CD) as sampling strategy, and propose a novel MC-PO algorithm. OnMC-PO outperforms existing SOTA baselines, and OnMC-PO leads to further improvement.
  arXiv  Detail & Related papers  (2025-02-06T23:45:08Z)
• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• Bidirectional Looking with A Novel Double Exponential Moving Average to Adaptive and Non-adaptive Momentum Optimizers [109.52244418498974]
  We propose a novel textscAdmeta (textbfADouble exponential textbfMov averagtextbfE textbfAdaptive and non-adaptive momentum) framework. We provide two implementations, textscAdmetaR and textscAdmetaS, the former based on RAdam and the latter based on SGDM.
  arXiv  Detail & Related papers  (2023-07-02T18:16:06Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Robust expected improvement for Bayesian optimization [1.8130068086063336]
  We propose a surrogate modeling and active learning technique called robust expected improvement (REI) that ports adversarial methodology into the BO/GP framework. We illustrate and draw comparisons to several competitors on benchmark synthetic exercises and real problems of varying complexity.
  arXiv  Detail & Related papers  (2023-02-16T22:34:28Z)
• Designing MacPherson Suspension Architectures using Bayesian Optimization [21.295015276123962]
  Testing for compliance is performed first by computer simulation using a discipline model. Designs passing this simulation are then considered for physical prototyping. We show that the proposed approach is general, scalable, and efficient.
  arXiv  Detail & Related papers  (2022-06-17T21:50:25Z)
• SimPO: Simultaneous Prediction and Optimization [3.181417685380586]
  We propose a formulation for the Simultaneous Prediction and Optimization (SimPO) framework. This framework introduces the use of a joint weighted loss of a decision-driven predictive ML model and an optimization objective function.
  arXiv  Detail & Related papers  (2022-03-31T20:01:36Z)
• The Perils of Learning Before Optimizing [16.97597806975415]
  We show how prediction models can be learned end-to-end by differentiating through the optimization task. We show that the performance gap between a two-stage and end-to-end approach is closely related to the emphprice of correlation concept in optimization.
  arXiv  Detail & Related papers  (2021-06-18T20:43:47Z)
• Application-Driven Learning: A Closed-Loop Prediction and Optimization Approach Applied to Dynamic Reserves and Demand Forecasting [41.94295877935867]
  We present application-driven learning, a new closed-loop framework in which the processes of forecasting and decision-making are merged and co-optimized. We show that the proposed methodology is scalable and yields consistently better performance than the standard open-loop approach.
  arXiv  Detail & Related papers  (2021-02-26T02:43:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.