-
作者：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...
-
作者：Adida, E; Perakis, G
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In this paper, we present a robust optimization formulation for dealing with demand uncertainty in a dynamic pricing and inventory control problem for a make-to-stock manufacturing system. We consider a multi-product capacitated, dynamic setting. We introduce a demand-based fluid model where the demand is a linear function of the price, the inventory cost is linear, the production cost is an increasing strictly convex function of the production rate and all coefficients are time-dependent. A k...
-
作者：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...
-
作者：Rockafellar, R. Tyrrell; Uryasev, Stan; Zabarankin, Michael
作者单位：University of Washington; University of Washington Seattle; State University System of Florida; University of Florida; Stevens Institute of Technology
摘要：Optimality conditions are derived for problems of minimizing a general measure of deviation of a random variable, with special attention to situations where the random variable could be the rate of return from a portfolio of financial instruments. General measures of deviation go beyond standard deviation in satisfying axioms that do not demand symmetry between ups and downs. The optimality conditions are applied to characterize the generalized ``master funds'' which elsewhere have been develo...
-
作者：Kaul, Hemanshu; Jacobson, Sheldon H.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. This paper presents new global optima results for the NK model by developing tools for handling dependency in the cases where K grows with N; this generalizes the previous work that focused on the analysis of the (independent) case K=N-1. A dependency graph is defined and studied to handle dependencies among underlying random variables in the NK m...
-
作者：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...
