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
- Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems.
The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately.
In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
arXiv Detail & Related papers (2024-07-24T12:00:30Z) - Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization [6.713974813995327]
We present MEMENTO, an RL approach that leverages memory to improve the adaptation of neural solvers at time.
We validate its effectiveness on benchmark problems, in particular Traveling Salesman and Capacitated Vehicle Routing.
arXiv Detail & Related papers (2024-06-24T08:18:19Z) - An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
An efficient probabilistic selection based constrained multi-objective EA is proposed, referred to as PSCMOEA.
It comprises novel elements such as (a) an adaptive search bound identification scheme based on the feasibility and convergence status of evaluated solutions.
Numerical experiments are conducted on an extensive range of challenging constrained problems using low evaluation budgets to simulate ECMOPs.
arXiv Detail & Related papers (2024-05-22T02:32:58Z) - Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric.
We propose a single framework built on their equivalence in learning scenarios.
Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
arXiv Detail & Related papers (2024-05-09T12:52:22Z) - End-to-End Learning for Fair Multiobjective Optimization Under
Uncertainty [55.04219793298687]
The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality.
This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives.
It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
arXiv Detail & Related papers (2024-02-12T16:33:35Z) - Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and
Optimization [59.386153202037086]
Predict-Then- framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving.
This approach can be inefficient and requires handcrafted, problem-specific rules for backpropagation through the optimization step.
This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by predictive models.
arXiv Detail & Related papers (2023-11-22T01:32:06Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver.
This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
arXiv Detail & Related papers (2023-01-28T01:50:42Z) - Uncertainty-Aware Search Framework for Multi-Objective Bayesian
Optimization [40.40632890861706]
We consider the problem of multi-objective (MO) blackbox optimization using expensive function evaluations.
We propose a novel uncertainty-aware search framework referred to as USeMO to efficiently select the sequence of inputs for evaluation.
arXiv Detail & Related papers (2022-04-12T16:50:48Z) - Optimistic variants of single-objective bilevel optimization for
evolutionary algorithms [6.788217433800101]
A partial partial evolutionary approach has been proposed to solve the benchmark problems and have outstanding results.
A new variant has also been proposed to the commonly used convergence approaches, i.e. optimistic and pessimistic.
The experimental results demonstrate the algorithm converges differently to optimum solutions with the optimistic variants.
arXiv Detail & Related papers (2020-08-22T23:12:07Z) - Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and
Open Challenges [0.0]
Research on new optimization algorithms is often funded based on the motivation that such algorithms might improve the capabilities to deal with real-world and industrially relevant challenges.
A large number of test problems and benchmark suites have been developed and used for comparative assessments of algorithms.
arXiv Detail & Related papers (2020-07-01T15:09:40Z)
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.