-
作者：Faenza, Yuri; Zhang, Xuan
作者单位：Columbia University
摘要：Gale and Shapley's stable assignment problem has been extensively studied, applied, and extended. In the context of school choice, mechanisms often aim at finding an assignment that is more favorable to students. We investigate two extensions introduced in this framework-legal assignments and the efficiency adjusted deferred acceptance mechanism (EADAM) algorithm-through the lens of the classic theory of stable matchings. In any instance, the set L of legal assignments is known to contain all ...
-
作者：Vera, Alberto; Banerjee, Siddhartha; Samaranayake, Samitha
作者单位：Cornell University; Cornell University; Cornell University
摘要：Motivated by the needs of modern transportation service platforms, we study the problem of computing constrained shortest paths (CSP) at scale via preprocessing techniques. Our work makes two contributions in this regard: 1) We propose a scalable algorithm for CSP queries and show how its performance can be parametrized in terms of a new network primitive, the constrained highway dimension. This development extends recent work that established the highway dimension as the appropriate primitive...
-
作者：Ajayi, Temitayo; Thomas, Christopher; Schaefer, Andrew J.
作者单位：Rice University
摘要：For an integer programming model with fixed data, the linear programming relaxation gap is considered one of the most important measures of model quality. There is no consensus, however, on appropriate measures of model quality that account for data variation. In particular, when the right-hand side is not known exactly, one must assess a model based on its behavior over many right-hand sides. Gap functions are the linear programming relaxation gaps parametrized by the right-hand side. Despite...
-
作者：Wang, Jue
作者单位：Queens University - Canada
摘要：Sequential multiclass diagnosis, also known as multihypothesis testing, is a classical sequential decision problem with broad applications. However, the optimal solution remains, in general, unknown as the dynamic program suffers from the curse of dimensionality in the posterior belief space. We consider a class of practical problems in which the observation distributions associated with different classes are related through exponential tilting and show that the reachable beliefs could be rest...
-
作者：Cominetti, Roberto; Correa, Jose; Olver, Neil
作者单位：Universidad Adolfo Ibanez; Universidad de Chile; University of London; London School Economics & Political Science
摘要：A fluid queuing network constitutes one of the simplest models in which to study flow dynamics over a network. In this model we have a single source-sink pair, and each link has a per-time-unit capacity and a transit time. A dynamic equilibrium (or equilibrium flow over time) is a flow pattern over time such that no flow particle has incentives to unilaterally change its path. Although the model has been around for almost 50 years, only recently results regarding existence and characterization...
-
作者：Baron, Opher; Hu, Ming; Malekian, Azarakhsh
作者单位：University of Toronto
摘要：We study the revenue volatility of a monopolist selling a divisible good to consumers in the presence of local network externalities among consumers. The utility of consumers depends on their consumption level as well as those of their neighbors in a network through network externalities. In the eye of the seller, there exist uncertainties in the network externalities, which may be the result of unanticipated shocks or a lack of exact knowledge of the externalities. However, the seller has to ...
-
作者：Wu, Lingxiao; Adulyasak, Yossiri; Cordeau, Jean-Francois; Wang, Shuaian
作者单位：Universite de Montreal; Universite de Montreal; HEC Montreal; Hong Kong Polytechnic University
摘要：Berth allocation and pilotage planning are the two most important decisions made by a seaport for serving incoming vessels. Traditionally, the berth allocation problem and the pilotage planning problem are solved sequentially, leading to suboptimal or even infeasible solutions for vessel services. This paper investigates a vessel service planning problem (VSPP) in seaports that addresses berth allocation and pilotage planning in combination. We introduce a compact mixed-integer linear programm...
-
作者：Bonami, Pierre; Lodi, Andrea; Zarpellon, Giulia
作者单位：Universite de Montreal; Polytechnique Montreal; Vector Institute for Artificial Intelligence
摘要：With the aim of fully embedding learned predictions in the algorithmic design of a mixed-integer quadratic programming (MIQP) solver, we translate the algorithmic question of whether to linearize convex MIQPs into a classification task and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in...
-
作者：Wang, Zhaodong; Ouyang, Yanfeng; She, Ruifeng
作者单位：Netflix, Inc.; University of Illinois System; University of Illinois Urbana-Champaign
摘要：This paper presents methods to obtain analytical solutions to a class of continuous traffic equilibrium problems, where continuously distributed customers from a bounded two-dimensional service region seek service from one of several discretely located facilities via the least congested travel path. We show that under certain conditions, the traffic flux at equilibrium, which is governed by a set of partial differential equations, can be decomposed with respect to each facility and solved anal...
-
作者：Dahan, Mathieu; Sela, Lina; Amin, Saurabh
作者单位：University System of Georgia; Georgia Institute of Technology; University of Texas System; University of Texas Austin; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem (p) as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ...
