-
作者：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...
-
作者：Sherali, HD; Adams, WP; Driscoll, PJ
作者单位：Virginia Polytechnic Institute & State University; Clemson University; United States Department of Defense; United States Army; United States Military Academy
摘要：A new hierarchy of relaxations is presented that provides a unifying framework for constructing a spectrum of continuous relaxations spanning from the linear programming relaxation to the convex hull representation for linear mixed integer 0-1 problems. This hierarchy is an extension of the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1990, 1994a); and is particularly designed to exploit special structures. Specifically, inherent special structures are exploited by identif...
-
作者：Bertsimas, D; Patterson, SS
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Throughout the United States and Europe, demand for airport use has been increasing rapidly, while airport capacity has been stagnating. Over the last ten years the number of passengers has increased by more than 50 percent and is expected to continue increasing at this rate. Acute congestion in many major airports has been the unfortunate result. For U.S. airlines, the expected yearly cost of the resulting delays is currently estimated at $3 billion. In order to put this number in perspective...
