检索结果-内蒙古大学图书馆

Generalization Bounds in the predict-then-optimize Framework

MATHEMATICS OF OPERATIONS RESEARCH 2023年第4期48卷 2043-2065页

作者： El Balghiti, Othman Elmachtoub, Adam N. Grigas, Paul Tewari, Ambuj Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Univ Michigan Dept Stat Ann Arbor MI 48109 USA

The predict-then-optimize framework is fundamental in many practical settings: predict the unknown parameters of an optimization problem and then solve the problem using the predicted values of the parameters. A natural loss function in this environment is to consider the cost of the decisions induced by the predicted parameters in contrast to the prediction error of the parameters. This loss function is referred to as the smart predict then-optimize (SPO) loss. In this work, we seek to provide bounds on how well the performance of a prediction model fit on training data generalizes out of sample in the context of the SPO loss. Because the SPO loss is nonconvex and non-Lipschitz, standard results for deriving generalization bounds do not apply. We first derive bounds based on the Natarajan dimension that, in the case of a polyhedral feasible region, scale at most logarithmically in the number of extreme points but, in the case of a general convex feasible region, have linear dependence on the decision dimension. By exploiting the structure of the SPO loss function and a key property of the feasible region, which we denote as the strength property, we can dramatically improve the dependence on the decision and feature dimensions. Our approach and analysis rely on placing a margin around problematic predictions that do not yield unique optimal solutions and then providing generalization bounds in the context of a modified margin SPO loss function that is Lipschitz continuous. Finally, we characterize the strength property and show that the modified SPO loss can be computed efficiently for both strongly convex bodies and polytopes with an explicit extreme point representation.

关键词： generalization bounds prescriptive analytics regression predict-then-optimize

来源：评论

学校读者我要写书评

暂无评论

CaVE: A Cone-Aligned Approach for Fast predict-then-optimize with Binary Linear Programs 1

引用

21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Tang, Bo Khalil, Elias B. Univ Toronto Dept Mech & Ind Engn SCALE AI Res Chair Data Driven Algorithms Modern Toronto ON Canada

ISBN: (数字)9783031605994

ISBN: (纸本)9783031606014;9783031605994

The end-to-end predict-then-optimize framework, also known as decision-focused learning, has gained popularity for its ability to integrate optimization into the training procedure of machine learning models that predict the unknown cost (objective function) coefficients of optimization problems from contextual instance information. Naturally, most of the problems of interest in this space can be cast as integer linear programs. In this work, we focus on binary linear programs (BLPs) and propose a new end-to-end training method to predict-then-optimize. Our method, Cone-aligned Vector Estimation (CaVE), aligns the predicted cost vectors with the normal cone corresponding to the true optimal solution of a training instance. When the predicted cost vector lies inside the cone, the optimal solution to the linear relaxation of the binary problem is optimal. This alignment not only produces decision-aware learning models, but also dramatically reduces training time as it circumvents the need to solve BLPs to compute a loss function with its gradients. Experiments across multiple datasets show that our method exhibits a favorable trade-off between training time and solution quality, particularly with large-scale optimization problems such as vehicle routing, a hard BLP that has yet to benefit from predict-then-optimize methods in the literature due to its difficulty.

关键词： Integer programming predict-then-optimize data-driven optimization machine learning

来源：评论

学校读者我要写书评

暂无评论

Characterizing and Improving the Robustness of predict-then-optimize Frameworks 14th

Characterizing and Improving the Robustness of Predict-Then-...

引用

14th International Conference on Decision and Game Theory for Security (GameSec)

作者： Johnson-Yu, Sonja Finocchiaro, Jessie Wang, Kai Vorobeychik, Yevgeniy Sinha, Arunesh Taneja, Aparna Tambe, Milind Harvard Univ Cambridge MA 02138 USA Ctr Res Computat & Soc Boston MA USA MIT Cambridge MA USA Google Res India Bangalore Karnataka India Washington Univ St Louis MO USA Rutgers State Univ Newark NJ USA

ISBN: (纸本)9783031506697;9783031506703

Optimization tasks situated in incomplete information settings are often preceded by a prediction problem to estimate the missing information;past work shows the traditional predict-then-optimize (PTO) framework can be improved by training a predictive model with respect to the optimization task through a PTO paradigm called decision-focused learning. Little is known, however, about the performance of traditional PTO and decision-focused learning when exposed to adversarial label drift. We provide modifications of traditional PTO and decision-focused learning that attempt to improve robustness by anticipating label drift. When the predictive model is perfectly expressive, we cast these learning problems as Stackelberg games. With these games, we provide a necessary condition for when anticipating label drift can improve the performance of a PTO algorithm: if performance can be improved, then the downstream optimization objective must be asymmetric. We then bound the loss of decision quality in the presence of adversarial label drift to show there may exist a strict gap between the performance of the two algorithms. We verify our theoretical findings empirically in two asymmetric and two symmetric settings. These experimental results demonstrate that robustified decision-focused learning is generally more robust to adversarial label drift than both robust and traditional PTO.

关键词： predict-then-optimize adversarial label drift decision-focused learning

来源：评论

学校读者我要写书评

暂无评论

Enhancing Resource Assignment Efficiency in Service Industry: A predict-then-optimize Approach with XGBoost

引用

Procedia Computer Science 2025年 253卷 644-653页

作者： Mehran Nasseri Taha Falatouri Patrick Brandtner Farzaneh Darbanian Sina Mirshahi University of Applied Sciences Upper Austria Logistikum Josef Ressel Centre for Predictive Value Network Intelligence Department of Informatics and Artificial Intelligence Faculty of Applied Informatics Tomas Bata University in Zlin Czech Republic

This paper addresses the critical aspect of resource planning in a service context through an integrated predictive and prescriptive approach. Utilizing real-world data from a company providing repair and maintenance services, we demonstrate the use of an XGBoost model to forecast ad-hoc service demands and subsequently optimize resource assignment using a mathematical model. Our findings show that the prediction evaluation metrics significantly improve, highlighting the superiority of complex machine learning models over baseline models such as Linear Regression. Furthermore, the integration of the prediction into the decision-making process resulted in a 26.4% lower decision error compared to the baseline model. Our research also found that the deviations in prediction and optimal objective function values are not aligned. While the average error for MAE % in prediction is 22.2%, the error for the optimal objective function is much lower, reducing to 5.3%. However, although true for our case, this might not be generalizable. Furthermore, when comparing the baseline model with these results, it is also shown that an improvement in prediction accuracy also improves decision making error. Our results indicate that a combined predict-then-optimize approach outperforms the existing methods in both predictive and prescriptive performance, demonstrating its applicability in real-world scenarios.

关键词： Resource planning predictive analytics optimization XGBoost predict-then-optimize

来源：评论

学校读者我要写书评

暂无评论

Prescriptive analytics for freeway traffic state estimation by multi-source data fusion

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2025年 198卷

作者： Huang, Di Zhang, Jinyu Liu, Zhiyuan Liu, Ronghui Southeast Univ Sch Transportat Nanjing Peoples R China Univ Leeds Inst Transport Studies Leeds England

In the context of freeway traffic state estimation, this study introduces prescriptive analytics-also known as "predict-then-optimize"-for integrating data from Electronic Toll Collection (ETC) systems and traffic sensors. Traditional single-method data fusion techniques are constrained by inherent limitations. For instance, optimization-based methods are generally predicated on prior assumptions that may induce systematic biases, whereas machine learning approaches are frequently criticized for their lack of interpretability and their inability to elucidate underlying traffic mechanisms. To address these limitations, a novel "retrieval and matching" algorithm is proposed that integrates machine learning with optimization. First, the concept of the "state gene" is introduced to encapsulate traffic structural knowledge representing frequently occurring traffic patterns. In the retrieval phase, a heterogeneous graph conventional network is employed to predict potential state genes for a given scenario. In the matching phase, the predicted state genes are utilized to minimize the discrepancy with the current traffic state. This integration not only enhances the interpretability of the estimation process but also endows the optimization component with reverse inference capability through the incorporation of machine learning. Validation using real-world data from the G92 Freeway in Zhejiang, China, demonstrates high accuracy, yielding Mean Absolute Percentage Errors (MAPE) of 1.12-1.65 % during peak periods and 1.28-1.67 % during off-peak periods.

关键词： Traffic state estimation Data fusion Prescriptive analytics predict-then-optimize State genes

来源：评论

学校读者我要写书评

暂无评论

Optimizing mobility resource allocation in multiple MaaS subscription frameworks: a group method of data handling-driven self-adaptive harmony search algorithm

引用

ANNALS OF OPERATIONS RESEARCH 2024年 1-29页

作者： Xi, Haoning Wang, Yan Shao, Zhiqi Zhang, Xiang Waller, Travis Univ Newcastle Newcastle Business Sch Newcastle NSW Australia Univ Sydney Discipline Int Business Sydney NSW Australia Univ Sydney Discipline Business Analyt Sydney NSW Australia Dalian Maritime Univ Coll Transportat Engn Dalian Peoples R China Tech Univ Dresden Fac Transport & Traff Sci Dresden Germany

Mobility as a Service (MaaS) transforms urban transportation from car ownership to subscription-based models. A key factor for the success of MaaS is accurately predicting users' Willingness to Pay (WTP) for various subscription packages, enhancing their adoption and satisfaction. This paper employs a "smart predict-then-optimize" framework, where the weekly, annual, and monthly MaaS subscription models are formulated as online, offline, and hybrid online-offline mobility resource allocation problems, respectively. We develop a group method of data handling (GMDH)-driven self-adaptive harmony search (SAHS) algorithm to solve the proposed mobility resource allocation problems effectively. Initially, GMDH-type neural networks predict users' WTP using their historical travel data, such as travel distance and service time, and socio-demographic characteristics, including inconvenience tolerance and travel delay budget;then these predicted WTP values are fed into the weekly, annual, and monthly mobility resource allocation problems, respectively. Comprehensive numerical experiments based on a simulated dataset demonstrate the robust prediction performance of the GMDH neural network across weekly, monthly, and annual subscription models, as well as the effectiveness of the GMDH-driven SAHS algorithm in managing resource allocation for these models. Our numerical findings highlight that the monthly subscription model strikes an optimal balance, combining the flexibility of the weekly model with the strategic depth of the annual model. This study proposes three distinct MaaS subscription models and a data-driven metaheuristic algorithm to customize MaaS offerings to user needs.

关键词： Mobility-as-a-service (MaaS) Group method of data handling (GMDH) Self-adaptive harmony search (SAHS) Resource allocation predict-then-optimize

来源：评论

学校读者我要写书评

暂无评论

Learning Fair Ranking Policies via Differentiable Optimization of Ordered Weighted Averages 24

Learning Fair Ranking Policies via Differentiable Optimizati...

引用

6th ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT)

作者： Dinh, My H. Kotary, James Fioretto, Ferdinando Univ Virginia Charlottesville VA 22901 USA

ISBN: (纸本)9798400704505

Learning to Rank (LTR) is one of the most widely used machine learning applications. It is a key component in platforms with profound societal impacts, including job search, healthcare information retrieval, and social media content feeds. Conventional LTR models have been shown to produce biases results, stimulating a discourse on how to address the disparities introduced by ranking systems that solely prioritize user relevance. However, while several models of fair learning to rank have been proposed, they suffer from deficiencies either in accuracy or efficiency, thus limiting their applicability to real-world ranking platforms. This paper shows how efficiently-solvable fair ranking models, based on the optimization of Ordered Weighted Average (OWA) functions, can be integrated into the training loop of an LTR model to achieve favorable balances between fairness, user utility, and runtime efficiency. In particular, this paper is the first to show how to backpropagate through constrained optimizations of OWA objectives, enabling their use in integrated prediction and decision models.

关键词： predict-then-optimize Learning To Rank Algorithmic Fairness

来源：评论

学校读者我要写书评

暂无评论

Efficient Public Health Intervention Planning Using Decomposition-Based Decision-focused Learning 24

Efficient Public Health Intervention Planning Using Decompos...

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Sanket Shah Arun Suggala Milind Tambe Aparna Taneja Harvard University Cambridge MA USA Google Research India Bangalore India Google Research Cambridge MA USA

ISBN: (纸本)9798400704864

The declining participation of beneficiaries over time is a key concern in public health programs. A popular strategy for improving retention is to have health workers 'intervene' on beneficiaries at risk of dropping out. However, the availability and time of these health workers are limited resources. As a result, there has been a line of research on optimizing these limited intervention resources using Restless Multi-Armed Bandits (RMABs). The key technical barrier to using this framework in practice lies in the need to estimate the beneficiaries' RMAB parameters from historical data. Recent research has shown that Decision-Focused Learning (DFL), which focuses on maximizing the beneficiaries' adherence rather than predictive accuracy, improves the performance of intervention targeting using RMABs. Unfortunately, these gains come at a high computational cost because of the need to solve and evaluate the RMAB in each DFL training step. In this paper, we provide a principled way to exploit the structure of RMABs to speed up intervention planning by cleverly decoupling the planning for different beneficiaries. We use real-world data from an Indian NGO, ARMMAN, to show that our approach is up to two orders of magnitude faster than the state-of-the-art approach while also yielding superior model performance. This would enable the NGO to scale up deployments using DFL to potentially millions of mothers, ultimately advancing progress toward UNSDG 3.1.

关键词： ai for social good decision-focused learning optimization predict-then-optimize public health restless multi-armed bandits

来源：评论

学校读者我要写书评

暂无评论

Modeling Robustness in Decision-Focused Learning as a Stackelberg Game 23

Modeling Robustness in Decision-Focused Learning as a Stacke...

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Sonja Johnson-Yu Kai Wang Jessie Finocchiaro Aparna Taneja Milind Tambe Harvard University Cambridge MA USA Harvard University & Google Research Cambridge MA USA Google Research Gurgaon India

ISBN: (纸本)9781450394321

predict-then-optimize is a common paradigm for optimization tasks situated in incomplete informational settings, in which an agent estimates missing parameters and then optimizes over these predicted parameters. One proposed improvement to this predict-then-optimize framework is decision-focused learning, which establishes an end-to-end learning pipeline, allowing a predictive model to be tailored to the particular optimization task. The behavior of this predict-then-optimize framework in the presence of noise, however, is not well-understood. This is problematic because many data collection and annotation systems are inherently noisy, and the introduction of such noise could lead to poor downstream optimization. In this work, we aim to present results on robustness to label noise in decision-focused learning and traditional predict-then-optimize tasks using a Stackelberg game as the underlying framework of explanation. Our results suggest that playing the Stackelberg game in anticipation of label noise yields robustness in the predict-then-optimize framework at large, and that the optimal decision-focused learning Stackelberg solution continues to outperform the optimal traditional predict-then-optimize Stackelberg solution.

关键词： robust optimization adversarial attack and defense predict-then-optimize

来源：评论

学校读者我要写书评

暂无评论

Integrating prediction with optimization: Models and applications in transportation management

引用

Multimodal Transportation 2022年第3期1卷

作者： Ran Yan Shuaian Wang Department of Logistics and Maritime Studies The Hong Kong Polytechnic University Hung Hom Kowloon Hong Kong China

prediction and optimization are the foundation of many real-world analytics problems in various disciplines. As both can be challenging, they are usually treated sequentially in existing studies, where the prediction problem is dealt with in the first stage, followed by the optimization problem in the second stage, which is called the predict-then-optimize paradigm. Specifically, the unknown parameters in the optimization problem are first predicted by the prediction model and are then input to the optimization model to generate the optimal decisions. However, prediction models in the first stage are intended to minimize the prediction error, while ignoring the structure and property of the downstream optimization problem and how the predictions will be used. Consequently, suboptimal decisions might be generated. This editorial piece discusses current popular frameworks to integrate prediction with optimization, namely the smart “predict, then optimize” framework and the predictive prescription framework with examples in the transportation area provided. The article ends with proposing several promising research directions for future research.

关键词： prediction optimization predict-then-optimize smart “predict-then-optimize” predictive prescription

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：