-
作者：Prokopyev, Oleg A.; Ralphs, Ted K.
作者单位：University of Zurich; Lehigh University
摘要：We consider the computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader's perspective. We show that, for any constant c > 0, the problem of finding a leader's solution that is within Euclidean distance c(n) of any locally optimal leader's solution, where n is the total number of variables, is NP-hard. Our derivations exploit techniques similar to those used for the analogous result for quadratic optimization problems (QPs). ...
-
作者：Qi, Meng; Grigas, Paul; Shen, Zuo-Jun (max)
作者单位：Cornell University; University of California System; University of California Berkeley; University of Hong Kong; University of Hong Kong
摘要：Many real-world optimization problems involve uncertain parameters with probability distributions that can be estimated using contextual feature information. In contrast to the standard approach of first estimating the distribution of uncertain parameters and then optimizing the objective based on the estimation, we propose an integrated conditional estimation-optimization (ICEO) framework that estimates the underlying conditional distribution of the random parameter while considering the stru...
-
作者：Zhao, Feiyang; Gurvich, Itai; Hasenbein, John J.
作者单位：University of Texas System; University of Texas Austin; Northwestern University
摘要：We revisit the global-relative to control policies-stability of multiclass queueing networks. In these, as is known, it is generally insufficient that the nominal utilization at each server is below 100%. Certain policies, although work conserving, may destabilize a network that satisfies the nominal-load conditions; additional conditions on the primitives are needed for global stability (stability under any work-conserving policy). The global-stability region was fully characterized for two-s...
-
作者：Fan, Weiwei; Li, Xuewen; Luo, Jun; Tsai, Shing Chih
作者单位：Tongji University; Shanghai Jiao Tong University; National Cheng Kung University
摘要：Ranking-and-selection (R&S) procedures, which seek to select the best system among a finite set of stochastic systems, often conduct a first-stage sampling to estimate the unknown variances of the systems. In this paper, we assume that system samples are normally distributed and demonstrate that the first-stage sample size n0 affects the performance of sequential R&S procedures in the manner beyond variance estimations. Specifically, we prove that the presence of n0 could reduce the achieved p...
-
作者：Garg, Nikhil; Gurnee, Wes; Rothschild, David; Shmoys, David B.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT); Microsoft
摘要：Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States-winnertake-all single-member districts-both enables substantial partisan gerrymandering and constrains fair redistricting, preventing proportional representation in legislatures. We study the design of multimember districts (MMDs), in which each district elects multiple representatives, potentially through a non-winner-take-all voting rule. We ...
-
作者：Che, Ethan; Dong, Jing; Tong, Xin T.
作者单位：Columbia University; National University of Singapore
摘要：Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data samples are independent and identically distributed (iid). However, applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The adaptively genera...
-
作者：Bu, Like; Dawande, Milind; Janakiraman, Ganesh
作者单位：University of Texas System; University of Texas Dallas
摘要：We study effective mechanisms for a manufacturer (buyer) to procure components of an assembly system under asymmetric information (including private costs and unobservable effort) and supply uncertainty. For each component, the buyer has access to an unreliable supplier whose production cost is private, input effort is unobservable, and production yield is uncertain. Further, both the buyer and the supplier have access to a more expensive but reliable supply source. The supplier also has acces...
-
作者：Tang, Yanhan (Savannah); Scheller-Wolf, Alan; Tayur, Sridhar; Perito, Emily R.; Roberts, John P.
作者单位：Southern Methodist University; Carnegie Mellon University; University of California System; University of California San Francisco
摘要：Split liver transplantation (SLT) is a procedure that potentially saves two lives using one liver, increasing the total benefit derived from the limited number of donated livers available. SLT may also improve equity by giving transplant candidates who are physically smaller (including children) increased access to liver transplants. However, SLT is rarely used in the United States. To help quantify the benefits of increased SLT utilization and provide decision support tools, we introduce a de...
-
作者：Chen, Xinyun; Hong, Guiyu; Liu, Yunan
作者单位：The Chinese University of Hong Kong, Shenzhen; Shanghai University of Finance & Economics; Amazon.com; North Carolina State University
摘要：We investigate an optimization problem in a queueing system where the service provider selects the optimal service fee p and service capacity & micro; to maximize the cumulative expected profit (the service revenue minus the capacity cost and delay penalty). The conventional predict-then-optimize (PTO) approach takes two steps: First, it estimates the model parameters (e.g., arrival rate and service-time distribution) from data; second, it optimizes a model taking these parameters as input. A ...
-
作者：Chen, Ningyuan; Li, Anran; Yang, Shuoguang
作者单位：University of Toronto; Chinese University of Hong Kong; Hong Kong University of Science & Technology
摘要：We consider the revenue maximization problem for an online retailer who plans to display in order a set of products differing in their prices and qualities. Consumers have attention spans, that is, the maximum number of products they are willing to view, and inspect the products sequentially before purchasing a product or leaving the platform empty-handed when the attention span gets exhausted. Our framework extends the wellknown cascade model in two directions: random attention spans of a rep...
