INFORMS 2021 Program Book

INFORMS Anaheim 2021

SC27

presence of noise or non-smoothness. The resulting Full-Low Evaluation method is globally convergent even in the non-smooth case and yields the appropriate rates in the smooth case for the unconstrained case. Results show that is efficient and robust across problems with different levels of smoothness and noise.

SC27 CC Room 206B In Person: Network Optimization: Network Games General Session Chair: Soham Das, Bryan, TX, 77801, United States 1 - Network Connectivity Game Darko Skorin-Kapov, Professor, R.B. Willumstad School of Business, Adelphi University, Garden City, NY, United States, Jadranka Skorin-Kapov We investigate the cost allocation strategy associated with the problem of providing service between all pairs of network nodes. There is a cost associated with each link and the communication between any pair of nodes can be delivered via paths connecting those nodes. A cost efficient solution which provides service for all node pairs is a (non-rooted) minimum cost spanning tree. The cost of such a solution should be distributed among users (node pairs) who might have conflicting interests. The objective of this paper is to formulate the above cost allocation problem as a cooperative game, to be referred to as a Network Connectivity (NC) game, and efficiently find some core cost allocations. 2 - Decentralized Fictitious Play in Near-potential Games with Time-varying Communication Networks Sarper Aydin, Texas A&M University, College Station, TX, United States, Sina Arefizadeh, Ceyhun Eksin We study the convergence properties of decentralized fictitious play (DFP) for the class of near-potential games where the incentives of agents are nearly aligned with a potential function. Agents share information only with their current neighbors in a sequence of time-varying networks, keep estimates of other agents’ empirical frequencies, and take actions to maximize their expected utility functions computed with respect to the estimated empirical frequencies. We show that empirical frequencies of actions converge to a set of strategies with potential function values that are larger than the potential function values obtained by approximate Nash equilibria of the closest potential game. 3 - Greedy Algorithms to Maximize Anti-coordination in Network Games Soham Das, Texas A&M University, College-station, TX, United States, Ceyhun Eksin In an anti-coordination network game, players are encouraged to differentiate their actions from their neighbors. Since, despite incentives, selfish agents may fail to do so, our goal is to eliminate all active coordination links by controlling a minimum set of players. We motivate the problem by an epidemic game where people (healthy and sick) decide to take the costly action, e.g. taking protective measures vs. free riding. The player selection problem is combinatorial with a submodular objective. Hence, we consider greedy algorithms that exploit behavior cascades on the network. Numerical experiments show that the greedy algorithms are near optimal and outperform centrality based heuristics. SC28 CC Room 207B In Person: Recent Advances in Nonconvex Optimization II General Session Chair: Lijun Ding, Cornell University, Ithaca, NY, 14850-2842, United States 1 - Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery Liwei Jiang, Cornell University, Ithaca, NY, United States We study the robust recovery of a low-rank matrix from grossly corrupted measurements, with no prior knowledge on the intrinsic rank. We employ a robust $\ell_1$ loss function and deal with the challenge of the unknown rank by using an overspecified factored representation of the matrix variable. We then solve the associated nonconvex nonsmooth problem using a subgradient method with diminishing step sizes. We show that under a regularity condition on the sensing matrices and corruption, which can be verified for Gaussian measurements under independent or adversary sparse corruptions, even with rank overspecified, the subgradient method converges to the exact low-rank solution at a sublinear rate. Moreover, our result is more general in the sense that it automatically speeds up to a linear rate once the factor rank matches the unknown rank. 2 - Full-low Evaluation Methods for Derivative-Free Optimization Oumaima Sohab, Lehigh University, Bethlehem, PA, United States We propose a new class of directional methods for Derivative-Free Optimization that considers two types of iterations. The first type is expensive in function evaluations but exhibits good performance in the smooth, non-noisy case. The second type is cheap in function evaluations, more appropriate under the

SC29 CC Room 207C In Person: Optimal Decision Making via Large Deviations Principles General Session Chair: Bart Paul Gerard Van Parys, MIT Sloan School of Management, Cambridge, MA, 02139, United States 1 - Optimal Data-driven Decision-making With Any Desired Out-of-sample Guarantees We study the problem of designing optimal approaches for stochastic optimization problems when only data is available. Most prior works construct estimators of the true unknown expectation using data and derive out-of-sample bounds to guarantee the quality of the estimator. We follow a different route. We formalize what are the desirable properties of estimators used for stochastic optimization problems and seek to find the “optimal” estimator verifying these properties. For any desired out-of-sample guarantee, we construct explicitly a Distributionally Robust (DR) estimator that is uniformly closer to the true cost than any other estimator verifying such guarantee, making it optimal. We exhibit three different regimes depending on the strength of the guarantee for which the optimal DR estimator has uncertainty set all probability simplex, KL ball and ellipsoid. 2 - Optimal Transport in the Face of Noisy Data Bart Paul Gerard Van Parys, MIT. Sloan School of Management, Cambridge, MA, 02139, United States Optimal transport distances are popular and theoretically well understood in the context of data-driven prediction. A flurry of recent work has popularized these distances for data-driven decision-making as well although their merits in this context are far less well understood. This in contrast to the more classical entropic distances which are known to enjoy optimal statistical properties.This begs the question when, if ever, optimal transport distances enjoy similar statistical guarantees. Optimal transport methods are shown here to enjoy optimal statistical guarantees for decision problems faced with noisy data. SC30 CC Room 207D In Person: Latest Developments in Scheduling and Supply Chain/Managing Complex Projects General Session Chair: Chenman Ellie Cheng, Seattle, WA, 98109, United States 1 - Tasking Scheduling Problems with Progress Control on Parallel Machines Weiya Zhong, Shanghai University, School of Management, Shanghai, 200444, China, Jia Cui In this talk, we introduce parallel-machine task scheduling problems with progress control. For each job, there are multiple milestones at which a penalty will occur if the completed amount of this job is below a given satisfactory level. The goal is to minimize the total penalty for all the jobs at their multiple milestones. If the processing of a job can be overlapped on different machines and the penalty functions are convex and decreasing, the problem can be solved in polynomial time. If the overlap for a job’s processing is not allowed, we prove that this problem is NP-hard and formulate an MP model for this problem. We propose a branch-and-price algorithm to solve the case when the penalty functions are linear decreasing. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. 2 - Scheduling Reviews in Stochastic Serial Projects Chenman Ellie Cheng, University of Washington, Seattle, WA, 98109, United States, Shi Chen, Theodore D. Klastorin We consider the problem of monitoring an ongoing stochastic project to determine if corrective actions are needed to minimize the expected total cost of the project (consisting of direct resource costs, indirect/overhead costs, review costs, and delay/penalty costs). We initially model this problem as a two stage serial project when task durations are exponential; a review occurs either at a predetermined time or when the first stage is completed. We show that merely scheduling a review can extend the expected makespan of a project and determine conditions for additional second stage compression. We also discuss extensions of this model to multiple stages and other task distributions. Mohammed Amine Bennouna, PhD Student, Operations Research Center, MIT, Cambridge, MA, United States, Bart Paul Gerard Van Parys

24