-
作者：Engineer, Faramroze G.; Furman, Kevin C.; Nemhauser, George L.; Savelsbergh, Martin W. P.; Song, Jin-Hwa
作者单位：University of Newcastle; Exxon Mobil Corporation; University System of Georgia; Georgia Institute of Technology
摘要：A branch-price-and-cut algorithm is developed for a complex maritime inventory-routing problem with varying storage capacities and production/consumption rates at facilities. The resulting mixed-integer pricing problem is solved exactly and efficiently using a dynamic program that exploits certain extremal characteristics of the pricing problem. The formulation is tightened by using the problem's boundary conditions in preprocessing and to restrict the set of columns that are produced by the p...
-
作者：Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA; Carnegie Mellon University
摘要：We consider the vehicle routing problem with stochastic demands (VRPSD). We give randomized approximation algorithms achieving approximation guarantees of 1 + alpha for split-delivery VRPSD, and 2 + alpha for unsplit-delivery VRPSD; here alpha is the best approximation guarantee for the traveling salesman problem. These bounds match the best known for even the respective deterministic problems [Altinkemer, K., B. Gavish. 1987. Heuristics for unequal weight delivery problems with a fixed error ...
-
作者：Kaplan, Edward H.
作者单位：Yale University
摘要：This paper is the archival record of the INFORMS Philip McCord Morse Lecture delivered in 2010. It considers applications of operations research to intelligence problems in national security and counterterrorism. The phrase intelligence operations research can be interpreted in two different ways: as intelligence operations research, meaning studies to characterize and improve the operations of intelligence agencies themselves, and as intelligence operations research, meaning the application o...
-
作者：Ghiyasvand, Mehdi; Orlin, James B.
作者单位：Bu Ali Sina University; Massachusetts Institute of Technology (MIT)
摘要：We consider the Arrow-Debreu market with linear utilities in which there is a set G of divisible goods and a set B of buyers. Each buyer starts with an initial endowment of goods. The buyer's utility function is a linearly separable function of the goods that the buyer purchases. We develop a simple and efficient algorithm for determining an approximate market equilibrium. Our algorithm finds an E-approximate solution in O(n/epsilon(vertical bar B vertical bar vertical bar G vertical bar)) tim...
-
作者：Feldman, Michal; Tamir, Tami
作者单位：Hebrew University of Jerusalem; Hebrew University of Jerusalem; Reichman University
摘要：We study strategic resource allocation settings, where jobs correspond to self-interested players who choose resources with the objective of minimizing their individual cost. Our framework departs from the existing game-theoretic models mainly in assuming conflicting congestion effects, but also in assuming an unlimited supply of resources. In our model, a job's cost is composed of both its resource's load (which increases with congestion) and its share in the resource's activation cost (which...
-
作者：Levin, Yuri; Nediak, Mikhail; Topaloglu, Huseyin
作者单位：Queens University - Canada; Cornell University
摘要：We consider a problem faced by an airline that operates a number of parallel flights to transport cargo between a particular origin to destination pair. The airline can sell its cargo capacity either through allotment contracts or on the spot market, where customers exhibit choice behavior between different flights. The goal is to simultaneously select allotment contracts among available bids and find a booking control policy for the spot market to maximize the sum of the profit from the allot...
-
作者：Candogan, Ozan; Bimpikis, Kostas; Ozdaglar, Asuman
作者单位：Massachusetts Institute of Technology (MIT); Stanford University
摘要：We study the optimal pricing strategies of a monopolist selling a divisible good (service) to consumers who are embedded in a social network. A key feature of our model is that consumers experience a (positive) local network effect. In particular, each consumer's usage level depends directly on the usage of her neighbors in the social network structure. Thus, the monopolist's optimal pricing strategy may involve offering discounts to certain agents who have a central position in the underlying...
-
作者：Begen, Mehmet A.; Levi, Retsef; Queyranne, Maurice
作者单位：Western University (University of Western Ontario); Massachusetts Institute of Technology (MIT); University of British Columbia
摘要：We consider the problem of appointment scheduling with discrete random durations but under the more realistic assumption that the duration probability distributions are not known and only a set of independent samples is available, e.g., historical data. For a given sequence of appointments (jobs, tasks), the goal is to determine the planned starting time of each appointment such that the expected total underage and overage costs due to the mismatch between allocated and realized durations is m...
-
作者：Bode, Claudia; Irnich, Stefan
作者单位：Johannes Gutenberg University of Mainz
摘要：This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks...
-
作者：Smith, James E.; Ulu, Canan
作者单位：Duke University; University of Texas System; University of Texas Austin
摘要：In this paper we study the impact of uncertainty about future innovations in quality and costs on consumers' technology adoption decisions. We model the uncertainty in the technology's quality and costs as a Markov process and consider three models of the adoption decision. The first model assumes that consumers do a simple net present value (NPV) analysis that compares the NPV of adopting to that of not adopting, without considering the possibility of waiting. The second model is a stochastic...
