-
作者：Podinovski, Victor V.; Bouzdine-Chameeva, Tatiana
作者单位：University of Warwick
摘要：It is known that the incorporation of weight restrictions in models of data envelopment analysis may result in their infeasibility. In our paper we investigate this effect in detail. We show that the infeasibility is only one of several possible outcomes that point to a particular problem with weight restrictions. For example, the use of weight restrictions may also lead to zero or negative efficiency scores of some units. Removing problematic units from the data set does not necessarily remov...
-
作者：Ahmed, Shabbir; Papageorgiou, Dimitri J.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We consider two variants of a probabilistic set covering (PSC) problem. The first variant assumes that there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets so that each item is covered with a prespecified probability. The second variant seeks to maximize the minimum probability that a selected set can cover all items. To date, literature on this problem has focused on the special case in which uncertaintie...
-
作者：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...
-
作者：Hwang, Hark-Chin; Ahn, Hyun-Soo; Kaminsky, Philip
作者单位：Kyung Hee University; University of Michigan System; University of Michigan; University of California System; University of California Berkeley
摘要：We consider the multilevel lot-sizing problem with production capacities (MLSP-PC), in which production and transportation decisions are made for a serial supply chain with capacitated production and concave cost functions. Existing approaches to the multistage version of this problem are limited to nonspeculative cost functions-up to now, no algorithm for the multistage version of this model with general concave cost functions has been developed. In this paper, we develop the first polynomial...
-
作者：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...
-
作者：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.
-
作者：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...
-
作者：Chen, Xi; Ankenman, Bruce E.; Nelson, Barry L.
作者单位：Virginia Commonwealth University; Northwestern University
摘要：Stochastic kriging is a new metamodeling technique for effectively representing the mean response surface implied by a stochastic simulation; it takes into account both stochastic simulation noise and uncertainty about the underlying response surface of interest. We show theoretically, through some simplified models, that incorporating gradient estimators into stochastic kriging tends to significantly improve surface prediction. To address the issue of which type of gradient estimator to use, ...
