检索结果-内蒙古大学图书馆

A stochastic integer programming approach to solving a synchronous optical network ring design problem

NETWORKS 2004年第1期44卷 12-26页

作者： Smith, JC Schaefer, AJ Yen, JW Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15261 USA Univ Washington Seattle WA 98195 USA

We develop stochastic integer programming techniques tailored toward solving a Synchronous Optical Network (SONET) ring design problem with uncertain demands. Our approach is based on an L-shaped algorithm, whose (integer) master program prescribes a candidate network design, and whose (continuous) subproblems relay information regarding potential shortage penalty costs to the ring design decisions. This naive implementation performs very poorly due to two major problems: (1) the weakness of the master problem relaxations, and (2) the limited information passed to the master problem by the optimality cuts. Accordingly, we enforce certain necessary conditions regarding shortage penalty contributions to the objective function within the master problem, along with a corresponding set of valid inequalities that improves the solvability of the master problem. We also show how a nonlinear reformulation of the model can be used to capture an exponential number of optimality cuts generated by the linear model. We augment these techniques with a powerful upper-bounding heuristic to further accelerate the convergence of the algorithm, and demonstrate the effectiveness of our methodologies on a test bed of randomly generated stochastic SONET instances. (C) 2004 Wiley Periodicals, Inc.

关键词： stochastic integer programming L-shaped method decomposition SONET network design

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving real-time scheduling problems by stochastic integer programming

引用

COMPUTERS & CHEMICAL ENGINEERING 2004年第6-7期28卷 1087-1103页

作者： Sand, G Engell, S Univ Dortmund Proc Control Lab D-44221 Dortmund Germany

This contribution deals with scheduling problems of flexible chemical batch processes with a special emphasis on their real-time character. This implies not only the need for sufficiently short response times, but in particular the burden of in-complete knowledge about the future. To solve such problems, the application of two-stage stochastic integer programming techniques on moving horizons is proposed. They reflect the need for immediately applicable decisions and the potential of later recourse actions to cope with realized uncertainties. In addition to the classical expected value objective, simple measures of risk can be included. Motivated by an example process, some essential modeling prerequisites are discussed. As an important first step, the master scheduling problem is studied and a number of master scheduling models are presented. Large mixed-integer linear problems arise, which are well-suited for a dual decomposition approach. Numerical experiments with a problem-specific solution algorithm demonstrate the applicability of the method to real-world problems. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： batch scheduling uncertainty stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving real-time scheduling problems by stochastic integer programming

Modeling and solving real-time scheduling problems by stocha...

引用

International Conference on Foundations of Computer-Aided Process Operations

作者： Sand, G Engell, S Univ Dortmund Proc Control Lab D-44221 Dortmund Germany

关键词： batch scheduling uncertainty stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

A two-stage stochastic integer programming model for a thermal power system expansion

引用

International Transactions in Operational Research 2004年第3期11卷 243-257页

作者： Albornoz, Víctor M. Benario, Pablo Rojas, Manuel E. Departamento de Industrias Universidad Técnica Federico Santa María Chile Mega Red Ingenieros Ltds Santiago Chile

In this paper the obtaining of an optimum policy in the capacity expansion planning of a particular thermal-electric power system is proposed. Therefore, a two-stage stochastic integer programming is formulated. The model includes, through a finite group of scenarios, the existent uncertainty related to the future availability of the thermal plants currently under operation. The resultant model is solved numerically by the application of the L-shaped method, whose implementation and development were executed using the software AMPL, with CPLEX as a solver. The results reached are shown, which validate the use of the methodology adopted in this work. © 2004 Wiley Periodicals, Inc.

关键词： Capacity expansion Decomposition stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

A generic stochastic model for supply-and-return network design

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第2期34卷 417-442页

作者： Listes, Ovidiu Tilburg Univ NL-5000 LE Tilburg Netherlands Erasmus Univ Rotterdam Netherlands

This paper presents a generic stochastic model for the design of networks comprising both supply and return channels, organized in a closed loop system. Such situations are typical for manufacturing/re-manufacturing type of systems in reverse logistics. The model accounts for a number of alternative scenarios, which may be constructed based on critical levels of design parameters such as demand or returns. We describe a decomposition approach to this model, based on the branch-and-cut procedure known as the integer L-shaped method. Computational results in an illustrative numerical setting show a consistent performance efficiency of the method. Moreover, the stochaslic solution features a significant improvement in terms of average performance over the individual scenario solutions. A modeling and solution methodology as presented here can contribute to the efficient solution of network design models under uncertainty for reverse logistics. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： reverse logistics remanufacturing location uncertainty stochastic integer programming decomposition integer L-shaped

来源：评论

学校读者我要写书评

暂无评论

A hybrid evolutionary algorithm for solving two-stage stochastic integer programs in chemical batch scheduling

引用

COMPUTERS & CHEMICAL ENGINEERING 2007年第5-6期31卷 630-647页

作者： Till, Jochen Sand, Guido Urselmann, Maren Engell, Sebastian Univ Dortmund Proc Control Lab BCI AST D-44221 Dortmund Germany ABB Corp Res Ctr D-68526 Ladenburg Germany

This contribution deals with the solution of two-stage stochastic integer programs with discrete scenarios (2-SIPs) that arise in chemical batch scheduling under uncertainty. Since the number of integer variables in the second-stage increases linearly with the number of scenarios considered, the real world applications usually give rise to large scale deterministic equivalent mixed-integer linear programs (MILPs) which cannot be solved easily without incorporating decomposition methods or problem specific knowledge. In this paper a new hybrid algorithm is proposed to solve 2-SIPs based on stage decomposition: an evolutionary algorithm performs the search on the first-stage variables while the second-stage subproblems are solved by mixed-integer programming. The algorithm is tested for a real-world scheduling problem with uncertainties in the demands and in the production capacity. Numerical experiments have shown, that the new algorithm is robust and superior to state-of-the-art solvers if good solutions are needed in short CPU-times. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： stochastic integer programming evolutionary algorithms hybrid algorithms chemical batch scheduling uncertainty

来源：评论

学校读者我要写书评

暂无评论

stochastics in discrete logistics models:What can we do?

Stochastics in discrete logistics models:What can we do?

引用

IEEE International Conference on Industrial Engineering and Engineering Management

作者： Wallace, Stein W. Kaut, Michal Crainic, Teodor Gabriel Lium, Arnt-Gunnar Chinese Univ Hong Kong Molde Univ Coll Hong Kong Hong Kong Peoples R China Molde Univ Coll Molde Norway Univ Quebec Montreal PQ G1V 2M3 Canada SINTEF Trondheim Norway

ISBN: (纸本)9781424415281

A large number of logistics problems involve integer programming. Adding stochastics to such a problem seems computationally prohibitive. On the other hand, in most cases, stochastics is an integral part of the underlying problem. And more importantly, without adding stochastics explicitly, we may lose important aspects of the solution we are searching for. In this presentation we give a new approach to such problems, and apply the approach to service network design.

关键词： stochastic integer programming flexibility robustness options

来源：评论

学校读者我要写书评

暂无评论

A multi-stage stochastic integer programming approach for capacity expansion under uncertainty

引用

JOURNAL OF GLOBAL OPTIMIZATION 2003年第1期26卷 3-24页

作者： Ahmed, S King, A Parija, G Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA IBM Corp Thomas J Watson Res Ctr Math Sci Div Yorktown Hts NY 10598 USA

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.

关键词： capacity expansion stochastic integer programming reformulation heuristic branch & bound

来源：评论

学校读者我要写书评

暂无评论

Decomposition of test sets in stochastic integer programming

引用

MATHEMATICAL programming 2003年第2-3期94卷 323-341页

作者： Hemmecke, R Schultz, R Univ Calif Davis Dept Math Davis CA 95616 USA Univ Duisburg Gesamthsch Inst Math D-47048 Duisburg Germany

We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Finally, we report preliminary computational experience.

关键词： test sets stochastic integer programming decomposition methods

来源：评论

学校读者我要写书评

暂无评论

Enhancing a branch-and-bound algorithm for two-stage stochastic integer network design-based models

引用

MANAGEMENT SCIENCE 2006年第9期52卷 1450-1455页

作者： Andrade, Rafael Lisser, Abdel Maculan, Nelson Plateau, Gerard Univ Paris 11 Lab Rech Informat F-91405 Orsay France Univ Fed Rio de Janeiro COPPE Sistemas BR-21945970 Rio De Janeiro Brazil Univ Paris 13 LIPN Inst Galilee F-93430 Villetaneuse France

In this paper we present branch-and-bound (B&B) strategies for two-stage stochastic integer network design-based models with integrality constraints in the first-stage variables. These strategies are used within L-shaped decomposition-based B&B framework. We propose a valid inequality in order to improve B&B performance. We use this inequality to implement a multirooted B&B tree. A selective use of optimality cuts is explored in the B&B approach and we also propose a subgradient-based technique for branching on 0-1 feasible solutions. Finally, we present computational results for a fixed-charge network design problem with random demands.

关键词： stochastic integer programming network design under uncertainty B&B strategies

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：