-
作者：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...
-
作者：Erdogan, E; Iyengar, G
作者单位：Columbia University
摘要：In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set Q of the distributions is of the form Q = {Q : rho(p) (Q, Q(0)) <= beta}, where rho(p) denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according...
-
作者：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 ...
-
作者：Bastin, Fabian; Cirillo, Cinzia; Toint, Philippe L.
作者单位：University of Namur
摘要：Monte Carlo methods have extensively been used and studied in the area of stochastic programming. Their convergence properties typically consider global minimizers or first-order critical points of the sample average approximation (SAA) problems and minimizers of the true problem, and show that the former converge to the latter for increasing sample size. However, the assumption of global minimization essentially restricts the scope of these results to convex problems. We review and extend the...
-
作者：Chubanov, S; Kovalyov, MY; Pesch, E
作者单位：Belarusian State University; Universitat Siegen; National Academy of Sciences of Belarus (NASB); United Institute of Informatics Problems of the National Academy of Sciences of Belarus
摘要：We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error epsilon in time polynomial in the problem size and in 1/epsilon. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furtherm...
-
作者：Martin, A; Möller, M; Moritz, S
作者单位：Technical University of Darmstadt
摘要：A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mi...
-
作者：Blomvall, Joergen; Shapiro, Alexander
作者单位：Linkoping University; University System of Georgia; Georgia Institute of Technology
摘要：The vast size of real world stochastic programming instances requires sampling to make them practically solvable. In this paper we extend the understanding of how sampling affects the solution quality of multistage stochastic programming problems. We present a new heuristic for determining good feasible solutions for a multistage decision problem. For power and log-utility functions we address the question of how tree structures, number of stages, number of outcomes and number of assets affect...
-
作者：Cheon, Myun-Seok; Ahmed, Shabbir; Al-Khayyal, Faiz
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to redu...
-
作者：Goel, Vikas; Grossmann, Ignacio E.
作者单位：Carnegie Mellon University
摘要：We address a class of problems where decisions have to be optimized over a time horizon given that the future is uncertain and that the optimization decisions influence the time of information discovery for a subset of the uncertain parameters. The standard approach to formulate stochastic programs is based on the assumption that the stochastic process is independent of the optimization decisions, which is not true for the class of problems under consideration. We present a hybrid mixed-intege...
