-
作者：Fernandez, E; Garfinkel, R; Arbiol, R
作者单位：Universitat Politecnica de Catalunya; University of Connecticut
摘要：The Cartographic Institute of Catalonia (ICC) produces commercial aerial photographic maps of locations in Europe and South America. These maps are often so large that it is necessary to produce one map from two or more photographs, which are combined two at a time in a process called mosaicking. The objective is to make the final map appear to be the product of a single photograph by producing a seam that is invisible even to an expert cartographer. The problem and a variation are modeled via...
-
作者：Walker, B; Sanso, B
作者单位：Universite de Montreal; Polytechnique Montreal
摘要：Managing redundant information is becoming an important issue in today's increasingly large distributed computer networks. As total redundancy is extremely costly to achieve, it has been proposed to keep perfectly updated information only at the servers, while keeping old copies of that information on local computers. For such copies to be useful, a maximum lifetime length is assigned to them. Before the lifetime has elapsed, the local devices must be stashed with a new updated copy. The probl...
-
作者：Barnhart, C; Johnson, EL; Nemhauser, GL; Savelsbergh, MWP; Vance, PH
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch-and-bound algorith...
-
作者：Gendreau, M; Hertz, A; Laporte, G; Stan, M
作者单位：Universite de Montreal; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite de Montreal; HEC Montreal
摘要：This article describes a generalized insertion heuristic for the Traveling Salesman Problem with Time Windows in which the objective is the minimization of travel times. The algorithm gradually builds a route by inserting at each step a vertex in its neighbourhood on the current route, and performing a local reoptimization. This is done while checking the feasibility of the remaining part of the route. Backtracking is sometimes necessary. Once a feasible route has been determined, an attempt i...
-
作者：Garbe, R; Glazebrook, KD
作者单位：Newcastle University - UK
摘要：We consider a range of controlled stochastic systems satisfying conservation laws together with a reducibility property that says that appropriate laws continue to hold when access to the system is restricted to a subset of all possible demand (job, customer) types. We show that for linear objectives, the optimum system-wide performance is a nondecreasing submodular (or supermodular) function of the subset chosen and that these properties are inherited from the geometry of the performance spac...
-
作者：Foster, DP; Vohra, RV
作者单位：University of Pennsylvania; University System of Ohio; Ohio State University
摘要：In this paper we describe four axioms that uniquely characterize the class of locations in tree networks that are obtained by minimizing an additively separable, nonnegative, nondecreasing, differentiable, and strictly convex function of distances. This result is analogous to results that have been obtained in the theory of bargaining, social choice, and fair resource allocation.
-
作者：Bixby, RE; Lee, EK
作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
摘要：A branch-and-cut IP solver is developed for a class of structured Oil integer programs arising from a truck dispatching scheduling problem. This problem involves a special class of knapsack equality constraints. Families of facets for the polytopes associated with individual knapsack constraints are identified. In addition, a notion of conflict graph is utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts b...
-
作者：Murphy, FH; Mudrageda, MV
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Temple University
摘要：In this paper we present the theoretical foundations for one of the methods used to achieve convergence in the National Energy Modeling System (NEMS). NEMS is a large model with several component models that are built and operated by different branches in the organization and is an example of a system without a hierarchical structure that cannot be solved by traditional equation solving methods. Some of the component models use linear programs to construct supply and demand curves. The discont...
-
作者：Scheller-Wolf, A; Sigman, K
作者单位：Carnegie Mellon University; Columbia University
摘要：We settle a conjecture concerning necessary conditions for finite mean steady-state customer delay at the second node of a tandem queue, using as an example a stable tandem queue with mutually independent i.i.d. interarrival and service times. We assume that the service times have infinite variance at the first node, finite variance at the second node, and smaller mean at the first node than at the second node. We show that this causes infinite mean stationary delay at the second node. Thus, i...
-
作者：Norkin, VI; Ermoliev, YM; Ruszczynski, A
作者单位：International Institute for Applied Systems Analysis (IIASA)
摘要：The optimal allocation of indivisible resources is formalized as a stochastic optimization problem involving discrete decision variables. A general stochastic search procedure is proposed, which develops the concept of the branch-and-bound method. The main idea is to process large collections of possible solutions and to devote more attention to the most promising groups. By gathering more information to reduce the uncertainty and by narrowing the search area, the optimal solution can be found...
