-
作者：Cottle, RW
作者单位：Stanford University
摘要：Mathematical programming owes much to George B. Dantzig who passed away on May 13, 2005 at the age of 90. This article is a tribute to this legendary pioneer and a very brief review of his extensive and enduring contributions to our field.
-
作者：Van der Laan, G.; Talman, D. A. J. J.; Yang, Z.
作者单位：Vrije Universiteit Amsterdam; Tinbergen Institute; Vrije Universiteit Amsterdam; Tilburg University; Tilburg University; Yokohama National University
摘要：In this paper we present two theorems on the existence of a discrete zero point of a function from the n-dimensional integer lattice Z(n) to the n-dimensional Euclidean space R-n. The theorems differ in their boundary conditions. For both theorems we give a proof using a combinatorial lemma and present a constructive proof based on a simplicial algorithm that finds a discrete zero point within a finite number of steps.
-
作者：Ravi, R.; Sinha, Amitabh
作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan
摘要：We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios. The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its determini...
-
作者：Dash, S; Günlük, O
作者单位：International Business Machines (IBM); IBM USA
摘要：In this paper we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities two-step MIR inequalities as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice. The two-step MIR inequalities define facets of the master cyclic group polyhedron of Gomory (1969). In addition, they dominate the strong fractional cuts of Letchford and Lod...
-
作者：Bertsimas, Dimitris; Caramanis, Constantine
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Using recent progress on moment problems, and their connections with semidefinite optimization, we present in this paper a new methodology based on semidefinite optimization, to obtain a hierarchy of upper and lower bounds on linear functionals defined on solutions of linear partial differential equations. We apply the proposed method to examples of PDEs in one and two dimensions, with very encouraging results. We pay particular attention to a PDE with oblique derivative conditions, commonly a...
-
作者：Anitescu, M
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：We present a time-stepping method to simulate rigid multibody dynamics with inelastic collision, contact, and friction. The method progresses with fixed time step without backtracking for collision and solves at every step a strictly convex quadratic program. We prove that a solution sequence of the method converges to the solution of a measure differential inclusion. We present numerical results for a few examples, and we illustrate the difference between the results from our scheme and previ...
-
作者：Bienstock, D; Zuckerberg, M
作者单位：Columbia University
摘要：Consider a 0/1 integer program min{c(T) x : Ax >= b, x epsilon {0, 1}(n)} where A is nonnegative. We show that if the number of minimal covers of Ax >= b is polynomially bounded, then for any epsilon > 0 and any fixed q, there is a polynomially large lift-and-project relaxation whose value is at least (1 - epsilon) times the value of the rank <= q relaxation. A special case of this result is that given by set-covering problems, or, generally, problems where the coefficients in A and b are boun...
-
作者：Guan, YP; Ahmed, S; Nemhauser, GL; Miller, AJ
作者单位：University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison
摘要：This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l, S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l, S) inequalities to a general class of valid inequalities, called the ( Q, S-Q) inequalities, and we establish necessary and sufficient conditions which guarantee that the ( Q, S-Q) inequalities ...
-
作者：Cheung, KKH; Cunningham, WH; Tang, L
作者单位：Carleton University; University of Waterloo; Hong Kong Monetary Authority (HKMA)
摘要：Given an undirected graph G = (V, E) and three specified terminal nodes t(1), t(2), t(3), a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c(e) is specified for each e. E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is NP-hard, and in fact, is max-SNP-hard. An approximation algorithm having performance guarantee 7/6 has recently been given by Calinescu, Karloff, and Rabani. It is based o...
-
作者：Song, W; Zang, R
作者单位：Harbin Normal University; Chinese University of Hong Kong
摘要：This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP) of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the strong conical hull intersection property, and that the collection of closed convex sets {C-1, . . . ,C-n} is bounded linearl...
