论文速递 | Operations Research 7月文章合集

在这里插入图片描述

编者按：

在本系列文章中，我们梳理了运筹学顶刊Operations Research7月份发布的14篇文章的基本信息，旨在帮助读者快速洞察行业最新动态。

文章1

题目
Dynamic Allocation of Reusable Resources: Logarithmic Regret in Overloaded Networks
可复用资源的动态分配:过载网络中的对数遗憾
作者
Xinchang Xie, Itai Gurvich, Simge Küçükyavuz
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.0429
发布时间
2024/7/5
摘要
This study addresses the challenge of dynamically allocating reusable resources to customers of various types within overloaded networks. The system comprises multiple pools of resources, each with a finite capacity, and customers who request service occupy one unit from each resource pool for a random duration. Upon completion, the resources are returned for future allocation. The objective is to maximize the long-term average reward while adhering to resource constraints.
The authors propose a threshold policy that leverages a corrected headcount process, which aligns with the linear programming (LP) relaxation of the problem and serves as an upper bound for policy performance. This policy is shown to achieve logarithmic regret in the high-volume, many-customer, and many-resource-units scenario, meaning that the performance loss relative to the LP upper bound is proportional to the logarithm of the total arrival volume.
The paper further demonstrates that no policy can attain sub-logarithmic regret in overloaded networks, establishing logarithmic regret as the best attainable performance. The proposed policy’s effectiveness is supported by simulations, which illustrate its practical utility in various network configurations.

本研究解决了在过载网络中将可复用资源动态分配给不同类型客户的挑战。系统包括多个资源池，每个资源池的容量有限，客户请求服务时会占用每个资源池的一个单位，持续随机时间。服务完成后，资源将被返还以供未来分配。目标是在遵守资源限制的同时最大化长期平均收益。
作者提出了一种阈值策略，利用校正的人力资源过程，与问题的线性规划（LP）松弛一致，并作为策略性能的上限。在高交易量、多客户和多资源单元的情况下，该策略显示出对数遗憾，即相对于LP上限的性能损失与总到达量的对数成正比。
本文进一步证明，在过载网络中，没有任何策略能够实现亚对数遗憾，确立了对数遗憾作为最佳可达到性能。通过模拟验证了所提策略的有效性，展示了其在各种网络配置中的实用性。

文章2

题目
Optimal No-Regret Learning in Repeated First-Price Auctions
重复首价拍卖中的最优无悔学习
作者
Yanjun Han, Tsachy Weissman, Zhengyuan Zhou
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2020.0282
发布时间
2024/7/8
摘要
This paper investigates the problem of online learning in repeated first-price auctions, where a bidder, observing only the winning bid after each auction, must learn to bid adaptively in order to maximize cumulative payoff. The bidder is subjected to censored feedback, meaning that if she wins, she cannot see the highest bid from other bidders, which are assumed to be independently and identically distributed (iid) from an unknown distribution. The authors develop the first learning algorithm that achieves a near-optimal O(√T) regret bound by leveraging the specific feedback structure and payoff function of first-price auctions.
The paper introduces a novel framework termed as partially ordered contextual bandits, which combines graph feedback across bids, cross learning across contexts (private values), and a partial order over contexts. This framework is applied to first-price auctions, revealing a separation between stochastic and adversarial contexts. Under stochastic contexts, a regret nearly independent of action/context sizes is achievable, while this is not possible under adversarial contexts. The authors propose two algorithms: one for stochastic private values with an $O(\sqrt{T}log2.5 T)$ regret, and another for adversarial private values with an $O(\sqrt{T}log3 T)$ regret, thus providing a complete learning strategy for first-price auctions.
The study contributes to the literature by providing optimal learning algorithms for first-price auctions and establishing the theoretical limits of regret under different contexts. It also discusses extensions and open problems, such as the impact of reversed one-sided feedback and the impossibility result under non-iid highest outbid (HOB) scenarios.

本文研究了重复首价拍卖中的在线学习问题，其中一个竞拍者仅在每次拍卖结束时观察到获胜的出价，必须学习如何适应性地出价以最大化其累积收益。竞拍者面临的反馈是有审查的，即如果她赢了，她无法看到其他竞拍者的最高出价，这些出价被假设为来自未知分布的独立同分布（iid）。作者开发了首个学习算法，通过利用首价拍卖的具体反馈结构和收益函数，实现了接近最优的O(√T)遗憾界限。
论文引入了一种新的框架，称为部分有序的上下文老虎机，它结合了跨出价的图反馈、跨上下文（私人价值）的交叉学习和上下文的部分顺序。该框架应用于首价拍卖，揭示了随机和对抗性情境之间的分离。在随机情境下，可以实现与行动/上下文大小几乎无关的遗憾，而在对抗性情境下这是不可能的。作者提出了两种算法：一种用于随机私人价值，遗憾为 $O(\sqrt{T}log2.5 T)$ ；另一种用于对抗性私人价值，遗憾为 $O(\sqrt{T}log3 T)$ ，从而为首价拍卖提供了完整的学习策略。
研究通过为首价拍卖提供最优学习算法，并在不同情境下建立遗憾的理论极限，为文献做出了贡献。同时，论文还讨论了扩展和开放问题，例如反向单边反馈的影响以及非iid最高出价（HOB）情境下的不可能性结果。

文章3

题目
Business Model Choice for Heavy Equipment Manufacturers
重型设备制造商的商业模式选择
作者
Philippe Blaettchen, Niyazi Taneri, Sameer Hasija
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0656
发布时间
2024/7/11
摘要
The paper explores the impact of technological advances on the business models of heavy equipment manufacturers, focusing on the shift from traditional ownership-based models to access-based models such as servicization and peer-to-peer sharing. The authors develop a game-theoretic model to determine the optimal business model choice, considering factors like after-sales services, equipment characteristics, usage environments, and fuel prices.
The study reveals that the profitability and environmental performance of business models are influenced by the cost of ownership, maintenance, and the potential for pooling demand through access-based models. The authors find that traditional sales and after-sales services (SA), servicization (SV), and sharing platforms (SP) can all be optimal under different conditions. For instance, servicization is preferred when production costs are low, while sharing becomes more relevant as fuel costs increase and with the advent of electrification.
The paper also introduces a novel framework for analyzing the environmental impact of business models, showing that all models can potentially create win-win situations for manufacturers and the environment. The authors conclude that the choice of business model should be based on a holistic view that incorporates economic and environmental considerations, and they call for further research into the broader environmental analysis of business models.

本文探讨了技术进步对重型设备制造商商业模式的影响，重点研究了从传统的基于所有权的模式向基于使用权的模式（如服务化和点对点共享）的转变。作者开发了一个博弈论模型，用以确定最优的商业模式选择，考虑了售后服务、设备特性、使用环境和燃油价格等因素。
研究揭示了商业模式的盈利能力和环境性能受到所有权成本、维护成本以及通过使用权模式聚合需求的成本的影响。研究发现，在不同条件下，传统的销售和售后服务（SA）、服务化（SV）和共享平台（SP）都可以是最优的。例如，当生产成本低时，倾向于选择服务化，而随着燃油成本的增加和电气化的到来，选择共享变得更有价值。
论文还引入了一个分析商业模式环境影响的新框架，表明所有模式都有可能为制造商和环境创造双赢的局面。作者总结说，商业模式的选择应基于一个整体视角，这包括经济和环境考量，并呼吁对商业模式的环境分析进行进一步研究。

文章4

题目
Risk-Adaptive Local Decision Rules
风险适应局部决策规则
作者
Johannes O. Royset, Miguel A. Lejeune
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0564
发布时间
2024/7/15
摘要
This paper presents a framework for constructing local decision rules tailored for parameterized mixed-binary optimization problems. These decision rules are designed to provide near-optimal solutions across a spectrum of parameter values without assuming linearity, convexity, or smoothness of the underlying problem. The approach is grounded in solving risk-adaptive training problems that leverage continuous and potentially nonlinear mappings. Both asymptotic and nonasymptotic analyses are conducted to demonstrate the local near-optimality of the proposed decision rules. The framework also addresses practical considerations such as inexact function evaluations, solution tolerances, regularization, and solver-friendly model reformulations. Additionally, it enables sensitivity and stability analysis for a wide range of parameterized optimization problems.
The authors develop a decomposition algorithm to solve the resulting training problems and validate its effectiveness through a nonlinear binary optimization model derived from search theory. The decision rules are formulated to be consistent with the optimal decision for a given parameter vector and are adaptable to the level of conservativeness required by the analyst, using risk measures. The paper also explores the use of different risk measures, including expected value, worst-case, quantiles, and superquantiles, to adjust the decision rules’ conservativeness.

本文提出了一种针对参数化混合二进制优化问题的局部决策规则构建框架。这些决策规则旨在为一系列参数值提供接近最优的解决方案，且不依赖于问题的基础线性、凸性或平滑性。该方法基于解决风险自适应的训练问题，利用连续且可能是非线性的映射。通过渐近和非渐近分析，证明了所提出的决策规则在局部上的近似最优性。该框架还考虑了实际问题，如不精确的函数评估、训练问题中的解容忍度、正则化以及对求解器友好的模型重构。此外，它还能对广泛的参数化优化问题进行灵敏度和稳定性分析。
作者开发了一种分解算法来解决由此产生的训练问题，并通过搜索理论中得出的非线性二进制优化模型验证了其有效性。决策规则被制定为与给定参数向量的最优决策一致，并且可以根据分析师所需的保守程度使用风险度量进行调整。本文还探讨了使用不同的风险度量，包括期望值、最坏情况、分位数和超分位数，来调整决策规则的保守程度。

文章5

题目
A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization
Wasserstein分布鲁棒优化的简明对偶证明
作者
Luhao Zhang, Jincheng Yang, Rui Gao
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0135
发布时间
2024/7/15
摘要
This paper presents a novel and concise proof of the general duality theorem for Wasserstein distributionally robust optimization (WDRO). The proof is applicable to any Kantorovich transport cost, measurable loss function, and nominal probability distribution. It is based on an interchangeability principle that is inherent in existing duality results, and leverages one-dimensional convex analysis. The paper also establishes the conditions under which the interchangeability principle holds, linking it to measurable projection and weak measurable selection conditions. The authors demonstrate the broad applicability of their approach through rigorous treatments of duality in distributionally robust Markov decision processes and multistage stochastic programming, as well as extensions to infinity-Wasserstein DRO, risk-averse optimization, and the globalized distributionally robust counterpart.

本文提出了Wasserstein分布鲁棒优化（WDRO）的通用对偶定理的新颖且简洁的证明。该证明适用于任何Kantorovich传输成本、可测量损失函数和名义概率分布。它基于现有对偶结果中固有的可交换性原则，并利用一维凸分析。本文还建立了可交换性原则成立的条件，将其与可测量投影和弱可测量选择条件联系起来。作者通过在分布稳健马尔可夫决策过程和多阶段随机规划中的对偶处理，以及对无穷Wasserstein DRO、风险厌恶优化和全局化分布鲁棒对偶的扩展，展示了他们方法的广泛适用性。

文章6

题目
Improving Blockchain Consistency Bound by Assigning Weights to Random Blocks
通过为随机区块分配权重来提高区块链一致性
作者
Qing Zhang, Xueping Gong, Huizhong Li, Hao Wu, Jiheng Zhang
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.0463
发布时间
2024/7/15
摘要
Blockchain technology, underpinned by the Nakamoto consensus protocol, has demonstrated its potential in applications such as cryptocurrencies. However, it grapples with scalability issues due to the inherent trade-off between block production speed and system security against adversarial attacks. This paper introduces a novel method named Ironclad that enhances blockchain consistency by assigning varying weights to randomly selected blocks. The method is applied to the original Nakamoto protocol, and through rigorous analysis, it is proven to significantly improve the consistency bound without compromising security, even when the proportion of malicious mining power remains the same.
The Ironclad method introduces the concept of weight, assigning a weight of 1 to regular blocks and a higher weight θ > 1 to iron blocks. The weight of a chain is the sum of all block weights within it. This method requires minimal changes to the Nakamoto protocol, as it simply shifts the criterion from following the longest chain to the heaviest chain. The paper provides a detailed analysis of the method’s efficacy, demonstrating improved chain quality, confirmation time, and other consensus properties through both theoretical proofs and numerical experiments.
The authors also offer guidelines for selecting the parameters θ and q, which define the weight and randomness of iron blocks, respectively. The selection is based on optimizing the tolerance to adversarial mining power and balancing confirmation time. The paper concludes with a discussion on the potential extension of Ironclad to other Nakamoto-based protocols, showcasing its broad applicability in enhancing blockchain scalability and security.

基于Nakamoto共识协议的区块链技术在加密货币等应用中展现出潜力。然而，由于区块生产速度与抵御敌意攻击的系统安全性之间存在的内在权衡，它面临着可扩展性问题。本文提出了一种名为Ironclad的新颖方法，通过为随机选择的区块分配不同权重来增强区块链的一致性。该方法应用于原始的Nakamoto协议，并通过严格分析证明，在不降低安全性的前提下，显著提高了一致性界限，即使恶意挖矿力量的比例保持不变。
Ironclad方法引入了权重概念，将普通区块的权重设为1，将铁区块（iron blocks）的权重设为更高的θ > 1。一个链的权重是其上所有区块（铁区块或普通区块）权重的总和。这种方法对Nakamoto协议的改动很小，只是将跟随最长链的标准转变为跟随最重链。本文详细分析了该方法的有效性，通过理论和数值实验证明了链质量、确认时间和其他共识属性的改进。
作者还提供了选择参数θ和q的指导原则，这些参数分别定义了铁区块的权重和随机性。选择基于优化对恶意挖矿力量的容忍度和平衡确认时间。文章最后讨论了将Ironclad扩展到其他基于Nakamoto的协议的潜力，展示了其在提高区块链可扩展性和安全性方面的广泛应用。

文章7

题目
Technical Note—Near-Optimal Bayesian Online Assortment of Reusable Resources
技术笔记-可复用资源的近最优贝叶斯在线分类
作者
Yiding Feng, Rad Niazadeh, Amin Saberi
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2020.0687
发布时间
2024/7/15
摘要
This paper addresses the problem of revenue maximization in the online assortment of reusable resources, motivated by applications in e-commerce rental services. The authors propose competitive online algorithms that perform near-optimally against the optimum online policy within a Bayesian setting. The algorithms are designed to handle a stream of arriving consumers with heterogeneous types and rental durations, each drawn independently from known distributions.
The main result is a near-optimal algorithm that achieves a competitive ratio of $1-min\{\frac{1}{2},\epsilon^*(c_{min})\}$ , where $\epsilon^*(x)=O(\frac{log{x}}{x})$ and $c_{min}$ is the minimum initial inventory. The algorithm relies on an expected Linear Programming (LP) benchmark, solving the LP and simulating the solution through randomized rounding. A key challenge is ensuring inventory feasibility in a computationally efficient manner, which is addressed through discarding policies and post-processing assortment procedures.
The authors also present an improved near-optimal algorithm for the special case of non-reusable resources, leveraging prophet inequality techniques. Numerical simulations on synthetic data demonstrate the performance of the proposed algorithms, showing significant improvements over existing policies in terms of expected revenue.

本文针对电子商务租赁服务中的应用，研究了在线可重复使用资源组合中的收益最大化问题。作者提出了在贝叶斯设置中与最优在线策略相竞争的在线算法。这些算法旨在处理具有不同类型和租赁期限的连续到达的消费者流，每种类型和租赁期限都是从已知分布中独立抽取的。
主要结果是提出了一个近最优算法，其竞争比达到了 $1-min\{\frac{1}{2},\epsilon^*(c_{min})\}$ 的水平，其中 $\epsilon^*(x)=O(\frac{log{x}}{x})$ ， $c_{min}$ 是最小初始库存。该算法依赖于预期线性规划（LP）基准，通过解决LP并通过随机舍入模拟解决方案。一个关键挑战是以计算效率高的方式确保库存的可行性，这通过丢弃策略和后处理组合程序来解决。
作者还针对非可复用资源的特殊情况提出了改进的近最优算法，利用了先知不等式技术。在合成数据上的数值模拟展示了所提算法的性能，与现有策略相比，在预期收益方面有显著提高。

文章8

题目
Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios
带场景的两阶段随机车辆路径定价难度问题
作者
Matheus J. Ota, Ricardo Fukasawa
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0569
发布时间
2024/7/16
摘要
This paper delves into the Vehicle Routing Problem with Stochastic Demands (VRPSD), which extends the traditional vehicle routing problem by treating customer demands as random variables. The VRPSD has been predominantly addressed with set-partitioning formulations in state-of-the-art algorithms, necessitating efficient pricing problem routines. However, these methods often assume no correlation between demand variables, an oversimplification inconsistent with real-world scenarios where correlations are common. The paper focuses on the VRPSD with demands outlined by scenarios, demonstrating that the pricing problem remains strongly NP-hard under any route relaxation and any recourse cost approximation that meets mild assumptions. This finding underscores the challenge of developing efficient column-generation algorithms for the VRPSD, especially when demands adhere to an empirical probability distribution of scenarios.
The paper begins with an introduction to VRPSD and its significance in operations research, followed by a literature review. It then defines the VRPSD with scenarios and discusses the set partitioning formulations used in exact algorithms. The authors present the definitions of recourse cost functions and the VRPSD pricing problem, leading to the proof of their complexity results. The paper concludes with a discussion on the implications of the findings and potential future research directions.

本文深入研究了考虑客户需求量为随机变量的车辆路径问题（VRPSD），这一问题通过将客户需求量视为随机变量，扩展了传统的车辆路径问题。在现有的算法中，通常使用集合划分公式来解决VRPSD问题，这需要有效的定价问题例程。然而，这些方法通常假设需求变量之间没有相关性，这与现实世界中常见的情况不符，因为现实世界中经常存在相关性。本文专注于基于场景的VRPSD问题，证明了在任何路线松弛和满足一些温和假设的任何回收成本近似下，定价问题仍然是强NP难的。这一发现强调了为VRPSD开发高效列生成算法的挑战，特别是当需求遵循场景的经验概率分布时。
文章首先介绍了VRPSD及其在运筹学中的重要性，然后回顾了相关文献。接着，文章定义了基于场景的VRPSD，并讨论了精确算法中使用的集合划分公式。作者提出了回收成本函数和VRPSD定价问题的定义，随后展示了他们复杂性结果的证明。文章最后讨论了这些发现的影响和可能的未来研究方向。

文章9

题目
Asymptotic Scaling of Optimal Cost and Asymptotic Optimality of Base-Stock Policy in Several Multidimensional Inventory Systems
多维库存系统中最优成本的渐近缩放与基库存策略的渐近最优性
作者
Jinzhi Bu, Xiting Gong, Xiuli Chao
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.0488
发布时间
2024/7/17
摘要
This study examines the asymptotic behavior of optimal costs and the asymptotic optimality of base-stock policies in three classes of multi-dimensional inventory systems under long-run average cost. The systems considered include (i) periodic-review systems with lost sales and positive lead times under a non-stationary demand process, (ii) periodic-review systems for perishable products with partial backorders and a non-stationary demand process, and (iii) continuous-review systems with fixed lead times, Poisson demand processes, and lost sales. The state spaces of these systems are multi-dimensional, making the computation of their optimal control policies/costs challenging.
Given that the unit shortage penalty cost is typically much higher than the unit holding cost, the analysis is conducted in the regime of large unit penalty cost. The research establishes the asymptotic optimality of the best (modified) base-stock policy and derives an explicit form solution for the optimal cost rate in each system when the lead-time demand is unbounded. This solution is expressed in terms of a simple fractile solution of the lead-time demand distribution. Additionally, the asymptotic scaling of the optimal cost in the first two systems is characterized when the lead-time demand is bounded.
The study contributes to the literature by providing insights into the optimal cost for three classical yet complex inventory systems under the regime of large unit penalty costs. It extends the asymptotic optimality results of simple base-stock policies to systems with non-stationary demand processes and establishes the asymptotic optimality of simple base-stock policies for continuous-review lost-sales inventory systems with Poisson demands.

本研究考察了在长期平均成本下的三类多维库存系统的最优成本的渐近行为以及基库存策略的渐近最优性。考虑的系统包括(i)具有丢失销售和正提前期的周期性盘查系统，在非平稳需求过程中；(ii)针对易腐产品的周期性审查系统，具有部分积压和非平稳需求过程；(iii)具有固定领先时间、泊松需求过程和丢失销售的连续审查系统。这些系统的状态空间是多维的，使得它们的最优控制策略/成本的计算变得具有挑战性。
鉴于单位短缺罚金成本通常比单位持有成本高得多，研究在大单位罚金成本的范围内进行。研究确立了在领先时间需求无界时最佳（修改后的）基库存策略的渐近最优性，并为每个系统的最优成本率提供了显式形式的解决方案。该解决方案以领先时间需求分布的简单分位数解来表示。此外，当领先时间需求有界时，也对前两个系统中的最优成本的渐近缩放进行了表征。
该研究通过为三个经典但极其复杂的库存系统在大单位罚金成本的范围内提供最优成本的见解，为文献做出了贡献。它将简单基库存策略的渐近最优性结果扩展到了具有非平稳需求过程的系统，并且为泊松需求的连续审查丢失销售库存系统建立了简单基库存策略的渐近最优性结果。

文章10

题目
Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations
多秘书问题和具有连续估值的在线线性规划中的对数遗憾
作者
Robert L. Bray
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.0036
发布时间
2024/7/17
摘要
This paper investigates the behavior of shadow prices in a linear program (LP) that allocates an endowment of resources to customers as the number of customers approaches infinity. The study demonstrates that the shadow prices exhibit a concentration of measure, converge to a multivariate normal distribution under central limit theorem scaling, and have a variance decreasing at a rate of $\theta(\frac{1}{n})$ . Utilizing these findings, the author proves that the expected regret in the online linear program by Li and Ye (2022) is $\theta(\log{n})$ , irrespective of whether the customer variable distribution is known beforehand or learned during the process. This result refines Li and Ye’s upper bound from $O(\log n \log \log n)$ to $O(\log n)$ and extends Lueker’s (1998) $\Omega(\log n)$ lower bound to a multidimensional context. The author also provides a simplified analysis of the multisecretary problem by Arlotto and Gurvich (2019) using new techniques.

本文研究了随着客户数量趋向无穷大，在线线性规划（LP）中影子价格的行为，该规划将资源的捐赠分配给客户。研究表明，影子价格表现出集中度量，根据中心极限定理的缩放，收敛于多变量正态分布，并且其方差以 $\theta(\frac{1}{n})$ 的速率递减。利用这些发现，作者证明了在 Li 和 Ye (2022)的在线线性规划中，预期的遗憾是 $\theta(\log{n})$ ，无论是事先知道客户变量分布还是在此过程中学习分布。这一结果将 Li 和 Ye 的上界从 $O(\log n \log \log n)$ 细化为 $O(\log n)$ ，并将Lueker（1998）的 $\Omega(\log n)$ 下界扩展到多维情境。作者还使用新技术对Arlotto和Gurvich（2019）的多秘书问题进行了简化分析。

文章11

题目
Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation
非自适应随机分数分类与可解释的半空间评估
作者
Rohan Ghuge, Anupam Gupta, Viswanath Nagarajan
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0431
发布时间
2024/7/18
摘要
This paper addresses the problem of sequential testing in complex systems with multiple components, each having an independent probability of being “working.” The goal is to evaluate the system’s status, represented by a function $f$ of the components’ outcomes, at the minimum expected cost. The authors introduce a more general “score classification” function and present the first constant-factor approximation algorithm, improving upon previous logarithmic approximation ratios. Notably, their algorithm is non-adaptive, performing tests in a fixed order, and also extends to batched tests where multiple tests are conducted simultaneously incurring an extra setup cost. The paper also tackles the halfspace evaluation problem, providing an $O(d^2\log d)$ approximation algorithm for evaluating functions on $d$ halfspaces. Computational experiments demonstrate the practical performance of the algorithm, showing that for most instances, the cost is within 50% of an information-theoretic lower bound on the optimal value.

本文研究了具有多个组件的复杂系统的顺序测试问题，每个组件“工作”的独立概率不同。目标是以最低的预期成本评估系统状态，该状态由其组件结果的函数 $f$ 表示。作者引入了更一般的“分数分类”函数，并提出了首个常数因子近似算法，改进了之前的对数近似比率。值得注意的是，他们的算法是非自适应的，以固定顺序执行测试，并且也扩展到了批量测试，其中可以同时进行多个测试并产生额外的设置成本。本文还探讨了半空间评估问题，为在 $d$ 个半空间上评估函数提供了一个 $O(d^2\log d)$ 近似算法。计算实验表明了算法的实际性能，在大多数情况下，成本在最优值的信息论下界内的50%以内。

文章12

题目
Side-Constrained Dynamic Traffic Equilibria
带侧约束的动态交通平衡
作者
Lukas Graf, Tobias Harks
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2023.0577
发布时间
2024/7/19
摘要
This paper delves into the complexities of dynamic traffic assignment with side-constraints, challenging a key assertion in the existing literature about the existence of dynamic equilibria within the classical linear edge-delay model under volume constraints. The authors present a counterexample that demonstrates the feasible flow space is not necessarily convex, and the traditional infinite-dimensional variational inequalities are inadequate for defining general side-constrained dynamic equilibria.
To address these issues, they propose a novel framework for side-constrained dynamic equilibria, which hinges on the concept of feasible ε-deviations of flow particles in space and time. This framework is then used to explore the characterization of equilibria through quasi-variational and variational inequalities under certain assumptions. The paper also establishes the first existence results for side-constrained dynamic equilibria in the non-convex setting of volume-constraints.
The authors’ contribution is multifaceted, including the introduction of a behavioral equilibrium concept through a noncooperative game that models the space of feasible deviations given a dynamic flow. They define several equilibrium concepts, including dynamic extensions of Larsson-Patriksson (LP), Bernstein-Smith (BS), and Marcotte-Nguyen-Schoeb (MNS) equilibria. The paper also provides necessary and sufficient conditions for equilibria to be characterized by associated quasi-variational inequalities or variational inequalities, and demonstrates the existence of equilibrium solutions under mild assumptions.
The paper concludes with an application of the augmented Lagrangian function approach to model volume constraints, showing the existence of dynamic LP and MNS equilibria under mild continuity assumptions. However, the authors note that this approach fails for stricter equilibrium concepts, such as the dynamic BS equilibrium, where flows for the unconstrained model with penalties do not converge to a strong dynamic BS equilibrium.

本文研究了带有侧约束的动态交通分配问题，并对现有文献中关于在经典线性边延迟模型下体积约束动态平衡存在性的关键论断提出了挑战。作者提出了一个反例，证明可行流量空间通常不一定是凸的，传统的无限维变分不等式也不适用于定义一般的带侧约束动态平衡。
为解决这些问题，他们提出了一个新的带侧约束动态平衡框架，该框架基于空间和时间中流量粒子可行ε偏差的概念。然后，该框架被用来在一定假设下，通过准变分和变分不等式来探索平衡的特征。本文还为体积约束的非凸设置中的带侧约束动态平衡建立了首项存在性结果。
作者的贡献是多方面的，包括通过非合作博弈引入行为平衡概念，该博弈模型了给定动态流量的可行偏差空间。他们定义了几种平衡概念，包括Larsson-Patriksson (LP)、Bernstein-Smith (BS) 和 Marcotte-Nguyen-Schoeb (MNS) 平衡的动态扩展。本文还提供了平衡可以通过相关的准变分不等式或变分不等式来表征的必要和充分条件，并在温和假设下证明了平衡解的存在。
文章最后通过应用增广拉格朗日函数方法来模拟体积约束，展示了在温和连续性假设下动态LP和MNS平衡的存在性。然而，作者指出这种方法对于更严格的平衡概念，如动态BS平衡，是失败的，在这种情况下，无约束模型中的流量带有惩罚项，并不收敛到一个强动态BS平衡。

文章13

题目
Strong Optimal Classification Trees
强最优分类树
作者
Sina Aghaei, Andrés Gómez, Phebe Vayanos
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2021.0034
发布时间
2024/7/31
摘要
Decision trees are widely used in various applications due to their interpretability and effectiveness. However, the problem of learning optimal binary classification trees is known to be NP-hard, and traditional methods often rely on heuristics, which do not guarantee optimal solutions. In this paper, we propose a novel mixed-integer optimization (MIO) formulation for learning optimal binary classification trees with univariate splits. Our approach leverages the power of MIO to its full extent by introducing a flow-based MIO model that can handle side constraints, enabling the design of interpretable and fair decision trees. We demonstrate that our formulation has a stronger linear optimization relaxation, which results in faster convergence and smaller optimality gaps compared to existing methods.
Our model exploits the decomposable structure of the problem and the max-flow/min-cut duality to develop a Benders’ decomposition method, which significantly speeds up the computation. We also propose a tailored procedure for solving each decomposed subproblem, generating facet-defining constraints for the main problem. Extensive computational experiments on standard benchmark datasets show that our proposed approaches are significantly faster, up to 29 times, and improve out-of-sample performance by up to 8% compared to state-of-the-art MIO-based techniques.

由于其可解释性和有效性，决策树在各种应用中得到了广泛应用。然而，学习最优二元分类树的问题已知是NP-hard，传统方法通常依赖于启发式方法，这些方法不能保证最优解。在本文中，我们提出了一种新的混合整数优化（MIO）公式，用于学习具有单变量分割的最优二元分类树。我们的方法充分利用了MIO的力量，通过引入一个基于流量的MIO模型，可以处理边约束，从而设计出可解释和公平的决策树。我们证明了我们的形式化方法具有更强的线性优化松弛，这导致与现有方法相比，收敛速度更快，最优性差距更小。
我们的模型利用了问题可分解结构和最大流/最小割对偶性，开发了一种Benders分解方法，显著加快了计算速度。我们还提出了一个定制的过程来解决每个分解的子问题，为主要内容生成了定义面约束。在标准基准数据集上的广泛计算实验表明，我们提出的方法在速度上显著更快，比现有的最先进的基于MIO的技术快29倍，并将样本外性能提高了高达8%。

文章14

题目
Information Relaxation and a Duality-Driven Algorithm for Stochastic Dynamic Programs
信息松弛与随机动态规划的对偶驱动算法
作者
Nan Chen, Xiang Ma, Yanchu Liu, Wei Yu
原文链接
https://pubsonline.informs.org/doi/abs/10.1287/opre.2020.0464
发布时间
2024/7/31
摘要
This paper introduces a novel duality-driven iterative approach that utilizes information relaxation to enhance confidence interval estimates for the true value in finite-horizon stochastic dynamic programming (SDP) problems. The proposed method demonstrates a monotonic convergence of dual value estimates to the actual value function within a finite number of dual iterations. Addressing the dimensionality curse prevalent in SDP applications, the authors also present a regression-based Monte Carlo algorithm facilitating practical implementation. This innovative approach is not only capable of evaluating heuristic policies but also possesses the potential to refine them when a significant duality gap is identified. The paper provides a convergence rate analysis for the Monte Carlo method, focusing on the impact of basis functions and sampled states. The efficacy of the method is exemplified through its application to an optimal order execution problem under market friction and an inventory management problem with lost sales and lead time. The results indicate that the proposed method can markedly improve upon existing heuristics, yielding new policies with robust performance guarantees.

本文提出了一种新颖的对偶驱动迭代方法，该方法利用信息放松来增强有限视界随机动态规划（SDP）问题真实值的置信区间估计。所提出的方法展示了在有限次对偶迭代内，对偶值估计的单调收敛到实际值函数。针对SDP应用中普遍存在的维数诅咒问题，作者还提出了一种基于回归的蒙特卡洛算法，以便于实际实施。这种创新方法不仅能够评估启发式策略，而且在发现对偶差距显著时，还具有改进这些策略的潜力。文中对蒙特卡洛方法的收敛速度进行了分析，重点关注了基函数和采样状态的影响。通过将其应用于存在市场摩擦的最优订单执行问题以及存在丢失销售和领先时间的库存管理问题，证明了该方法的有效性。结果表明，所提出的方法能够显著改进现有的启发式策略，产生具有可靠性能保证的新策略。