-
作者：DeValve, Levi; Pekec, Sasa; Wei, Yehua
作者单位：University of Chicago; Duke University
摘要：Network design problems, such as flexibility design, are ubiquitous in modern marketplaces where firms constantly innovate new ways to match supply and demand. We develop a primal-dual based approach to analyze the flexibility design problem, and establish that the problem possesses a novel structural property. The property, which we call cover modularity, can be interpreted as an approximate form of submodularity in the sense that local changes in the objective function can be used to bound g...
-
作者：Rostami, Borzou; Errico, Fausto; Lodi, Andrea
作者单位：Wilfrid Laurier University; Universite de Montreal; Polytechnique Montreal; University of Quebec; Ecole de Technologie Superieure - Canada; Cornell University
摘要：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 mixedinteger linear programming (MILP) reformulations and show the rel...
-
作者：Salemi, Hosseinali; Davarnia, Danial
作者单位：Iowa State University
摘要：Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed-integer programs (MIPs), such as those appearing in energy applications, is lacking. More broadly, the question of which problem structures admit a DD representation is still open in the DD community. In this paper, we address this quest...
-
作者：Sinclair, Sean R.; Jain, Gauri; Banerjee, Siddhartha; Yu, Christina Lee
作者单位：Cornell University
摘要：We consider the problem of dividing limited resources to individuals arriving over T rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type (i.e., preferences over the different resources). A standard notion of fairness in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency. The former is an individual guarantee, requiring that each agent prefers the agent's own allocation over the allocation of any ot...
-
作者：Sturt, Bradley
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
摘要：Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. We introduce a new approach for solving computationally-demanding stochastic optimal stopping problems with known probability distributions. The approach uses simulation to construct a robust optimization problem that approximates the stochastic optimal stopping problem to any arbitrary accuracy; we then solve the robust optimization problem to ob...
-
作者：Jiang, Jiashuo; Wang, Shixin; Zhang, Jiawei
作者单位：Hong Kong University of Science & Technology; Chinese University of Hong Kong; New York University
摘要：Resource pooling is a fundamental concept that has many applications in operations management for reducing and hedging uncertainty. An important problem in resource pooling is to decide (1) the capacity level of pooled resources in anticipation of randomdemand ofmultiple customers and (2) how the capacity should be allocated to fulfill customer demands after demand realization. In this paper, we present a general framework to study this two-stage problem when customers require individual and p...
-
作者：Liu, Yue; Fang, Ethan X.; Lu, Junwei
作者单位：Harvard University; Duke University; Harvard University; Harvard T.H. Chan School of Public Health
摘要：We propose a novel combinatorial inference framework to conduct general uncertainty quantification in ranking problems. We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons' outcomes. Our proposedmethod aims to infer general ranking properties of the BTLmodel. The general ranking properties include the local properties such as if an item is preferred over anothe...
-
作者：Goyal, Vineet; Grand-Clement, Julien
作者单位：Columbia University
摘要：Markov decision processes (MDPs) are used to model stochastic systems in many applications. Several efficient algorithms to compute optimal policies have been studied in the literature, including value iteration (VI) and policy iteration. However, these do not scale well, especially when the discount factor for the infinite horizon discounted reward, lambda, gets close to one. In particular, the running time scales as O (1=(1 - lambda)) for these algorithms. In this paper, our goal is to desig...
-
作者：de Ruiter, Frans J. C. T.; Zhen, Jianzhe; den Hertog, Dick
作者单位：Wageningen University & Research; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Amsterdam
摘要：Adjustable robust minimization problems where the objective or constraints depend in a convex way on the adjustable variables are generally difficult to solve. In this paper, we reformulate the original adjustable robust nonlinear problem with a polyhedral uncertainty set into an equivalent adjustable robust linear problem, for which all existing approaches for adjustable robust linear problems can be used. The reformulation is obtained by first dualizing over the adjustable variables and then...
-
作者：Vojnovic, Milan; Yun, Se-Young; Zhou, Kaifang
作者单位：University of London; London School Economics & Political Science; Korea Advanced Institute of Science & Technology (KAIST)
摘要：The problem of assigning ranking scores to items based on observed comparison data (e.g., paired comparisons, choice, and full ranking outcomes) has been of continued interest in a wide range of applications, including information search, aggregation of social opinions, electronic commerce, online gaming platforms, and, more recently, evaluation of machine learning algorithms. The key problem is to compute ranking scores, which are of interest for quantifying the strength of skills, relevancie...
