-
作者：Trapp, Andrew C.; Prokopyev, Oleg A.; Schaefer, Andrew J.
作者单位：Worcester Polytechnic Institute; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We propose a level-set approach to characterize the value function of a pure linear integer program with inequality constraints. We study theoretical properties of our characterization and show how they can be exploited to optimize a class of stochastic integer programs through a value function reformulation. Specifically, we develop algorithmic approaches that solve two-stage multidimensional knapsack problems with random budgets, yielding encouraging computational results.
-
作者：Belov, Gleb; Rohling, Heide
作者单位：University of Duisburg Essen; Technische Universitat Dresden
摘要：We consider the feasibility problem OPP (orthogonal packing problem) in higher-dimensional orthogonal packing: given a set of d-dimensional (d >= 2) rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. The one-dimensional (1D) bar LP relaxation of OPP reduces the latter to a 1D cutting-stock problem where the packing of each stock bar represents a possible 1D stitch through an OPP layout. The dual multipliers of the LP pr...
-
作者：Wang, Chen; Bier, Vicki M.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We introduce a simple elicitation process where subject-matter experts provide only ordinal judgments of the attractiveness of potential targets, and the adversary utility of each target is assumed to involve multiple attributes. Probability distributions over the various attribute weights are then mathematically derived (using either probabilistic inversion or Bayesian density estimation). This elicitation process reduces the burden of time-consuming orientation and training in traditional me...
-
作者：Ghate, Archis; Smith, Robert L.
作者单位：University of Washington; University of Washington Seattle; University of Michigan System; University of Michigan
摘要：Nonstationary infinite-horizon Markov decision processes (MDPs) generalize the most well-studied class of sequential decision models in operations research, namely, that of stationary MDPs, by relaxing the restrictive assumption that problem data do not change over time. Linear programming (LP) has been very successful in obtaining structural insights and devising solution methods for stationary MDPs. However, an LP approach for nonstationary MDPs is currently missing. This is because the LP f...
-
作者：Li, Hongmin; Zhang, Hao; Fine, Charles H.
作者单位：Arizona State University; Arizona State University-Tempe; University of British Columbia; Massachusetts Institute of Technology (MIT)
摘要：This paper studies a repeated game between a manufacturer and two competing suppliers with imperfect monitoring. We present a principal-agent model for managing long-term supplier relationships using a unique form of measurement and incentive scheme. We measure a supplier's overall performance with a rating equivalent to its continuation Utility (the expected total discounted utility of its future payoffs), and incentivize supplier effort with larger allocations of future business. We obtain t...
-
作者：Ahn, Hyun-Soo; Lewis, Mark E.
作者单位：University of Michigan System; University of Michigan; Cornell University
摘要：We consider the question of how routing and allocation can be coordinated to meet the challenge of demand variability in a parallel queueing system serving two types of customers. A decision maker decides whether to keep customers at the station at which they arrived or to reroute them to the other station. At the same time, the decision maker has two servers and must decide where to allocate their effort. We analyze this joint decision-making scenario with both routing and station-dependent h...
-
作者：Alpern, Steve; Lidbetter, Thomas
作者单位：University of Warwick; University of London; London School Economics & Political Science
摘要：We show how to optimize the search for a hidden object, terrorist, or simply Hider, located at a point H according to a known or unknown distribution v on a rooted network Q. We modify the traditional pathwise search approach to a more general notion of expanding search. When the Hider is restricted to the nodes of Q, an expanding search S consists of an ordering (a(1), a(2), ... ) of the arcs of a spanning subtree such that the root node is in a(1) and every arc a(i) is adjacent to a previous...
-
作者：Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto; Clavo, Roberto Wolfler
作者单位：University of Bologna; University of Bologna; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP)
摘要：In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites. The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from t...
-
作者：Moreno-Centeno, Erick; Karp, Richard M.
作者单位：Texas A&M University System; Texas A&M University College Station; University of California System; University of California Berkeley
摘要：We develop a novel framework, the implicit hitting set approach, for solving a class of combinatorial optimization problems. The explicit hitting set problem is as follows: given a set U and a family S of subsets of U, find a minimum-cardinality set that intersects (hits) every set in S. In the implicit hitting set problem (IHSP), the family of subsets S is not explicitly listed (its size is, generally, exponential in terms of the size of U); instead, it is given via a polynomial-time oracle t...
-
作者：Bartolini, Enrico; Cordeau, Jean-Francois; Laporte, Gilbert
作者单位：Universite de Montreal; HEC Montreal; Universite de Montreal
摘要：We study an extension of the capacitated arc routing problem (CARP) called the capacitated arc routing problem with deadheading demand (CARPDD). This problem extends the classical capacitated arc routing problem by introducing an additional capacity consumption incurred by a vehicle deadheading an edge. It can be used, e.g., to model time or distance constrained arc routing problems. We show that the strongest CARP lower bounds can be weak when directly applied to the CARPDD, and we introduce ...
