本文精选了运筹学国际顶刊《Operations Research》近期发表的论文，提供运筹学研究领域最新的学术动态。

Risk-Based Robust Statistical Learning by Stochastic Difference-of-Convex Value-Function Optimization

原刊和作者：

Operations Research Volume71 Issue2

Junyi Liu （Tsinghua University）

Jong-Shi Pang （University of Southern California）

Abstract

This paper proposes the use of a variant of the conditional value-at-risk (CVaR) risk measure, called the interval conditional value-at-risk (In-CVaR), for the treatment of outliers in statistical learning by excluding the risks associated with the left and right tails of the loss. The risk-based robust learning task is to minimize the In-CVaR risk measure of a random functional that is the composite of a piecewise affine loss function with a potentially nonsmooth difference-of-convex statistical learning model. With the optimization formula of CVaR, the objective function of the minimization problem is the difference of two convex functions each being the optimal objective value of a univariate convex stochastic program. An algorithm that combines sequential sampling and convexification is developed, and its subsequential almost-sure convergence to a critical point is established. Numerical experiments demonstrate the effectiveness of the In-CVaR–based estimator computed by the sampling-based algorithm for robust regression and classification. Overall, this research extends the traditional approaches for treating outliers by allowing nonsmooth and nonconvex statistical learning models, employing a population risk-based objective, and applying a sampling-based algorithm with the stationarity guarantee for solving the resulting nonconvex and nonsmooth stochastic program.

Link: https://doi.org/10.1287/opre.2021.2248

On System-Wide Safety Staffing of Large-Scale Parallel Server Networks

原刊和作者：

Operations Research Volume71 Issue2

Hassan Hmedi （The University of Texas at Austin）

Ari Arapostathis （The University of Texas at Austin）

Guodong Pang （Rice University）

Abstract

We introduce a “system-wide safety staffing” (SWSS) parameter for multiclass multipool networks of any tree topology, Markovian or non-Markovian, in the Halfin-Whitt regime. This parameter can be regarded as the optimal reallocation of the capacity fluctuations (positive or negative) of order when each server pool uses a square-root staffing rule. We provide an explicit form of the SWSS as a function of the system parameters, which is derived using a graph theoretic approach based on Gaussian elimination. For Markovian networks, we give an equivalent characterization of the SWSS parameter via the drift parameters of the limiting diffusion. We show that if the SWSS parameter is negative, the limiting diffusion and the diffusion-scaled queueing processes are transient under any Markov control and cannot have a stationary distribution when this parameter is zero. If it is positive, we show that the diffusion-scaled queueing processes are uniformly stabilizable; that is, there exists a scheduling policy under which the stationary distributions of the controlled processes are tight over the size of the network. In addition, there exists a control under which the limiting controlled diffusion is exponentially ergodic. Thus, we identified a necessary and sufficient condition for the uniform stabilizability of such networks in the Halfin-Whitt regime. We use a constant control resulting from the leaf elimination algorithm to stabilize the limiting controlled diffusion while a family of Markov scheduling policies that are easy to compute are used to stabilize the diffusion-scaled processes. Finally, we show that under these controls the processes are exponentially ergodic and the stationary distributions have exponential tails.

Link: https://doi.org/10.1287/opre.2021.2256

Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler

原刊和作者：

Operations Research Volume71 Issue2

Yorie Nakahira （Carnegie Mellon University）

Andres Ferragut （Universidad ORT Uruguay）

Adam Wierman （California Institute of Technology）

Abstract

Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, unpredictability and instability in service capacity often incur operational and infrastructural costs. In this paper, we seek to characterize optimal distributed algorithms that maximize the predictability, stability, or both when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes both the stationary mean and variance of the service capacity subject to strict demand and deadline requirements. For more general settings, we characterize the minimal-variance distributed policies with soft demand requirements, soft deadline requirements, or both. The performance of the optimal distributed policies is compared with that of the optimal centralized policy by deriving closed-form bounds and by testing centralized and distributed algorithms using real data from the Caltech electrical vehicle charging facility and many pieces of synthetic data from different arrival distributions. Moreover, we derive the Pareto-optimality condition for distributed policies that balance the variance and mean square of the service capacity. Finally, we discuss a scalable partially centralized algorithm that uses centralized information to boost performance and a method to deal with missing information on service requirements.

Link: https://doi.org/10.1287/opre.2021.2232

A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs

原刊和作者：

Operations Research Volume71 Issue2

Borzou Rostami （Wilfrid Laurier University）

Fausto Errico （Ecole de Technologie Superieure de Montreal）

Andrea Lodi （Canada Excellence Research Chair (CERC) in Data Science for Real-Time Decision Making）

Abstract

In this paper, we propose a general modeling and solving framework for a large class of binary quadratic programs subject to variable partitioning constraints. Problems in this class have a wide range of applications as many binary quadratic programs with linear constraints can be represented in this form. By exploiting the structure of the partitioning constraints, we propose mixed-integer nonlinear programming (MINLP) and mixed-integer linear programming (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength. Our solution methodology relies on a convex reformulation of the proposed MINLP and a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. To evaluate the robustness and efficiency of our solution method, we perform extensive computational experiments on various quadratic combinatorial optimization problems. The results show that our approach outperforms the state-of-the-art solver applied to different MILP reformulations of the corresponding problems.

Link: https://doi.org/10.1287/opre.2021.2241

A Strongly Polynomial Algorithm for Linear Exchange Markets

Operations Research Volume71 Issue2

Jugal Garg （University of Illinois at Urbana–Champaign）

László A. Végh （London School of Economic）

Abstract

We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly polynomial Duan–Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges—that is, pairs of agents and goods that must correspond to the best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges or, if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.

Link: https://doi.org/10.1287/opre.2021.2258