In this paper, we propose a successive approximation heuristic which solves large stochastic mixed-integerprogramming problem with complete fixed recourse. We refer to this method as the Scenario Updating Method, sin...
详细信息
In this paper, we propose a successive approximation heuristic which solves large stochastic mixed-integerprogramming problem with complete fixed recourse. We refer to this method as the Scenario Updating Method, since it solves the problem by considering only a subset of scenarios which is updated at each iteration. Only those scenarios which imply a significant change in the objective function are added. The algorithm is terminated when no such scenarios are available to enter in the current scenario subtree. Several rules to select scenarios are discussed. Bounds on heuristic solutions are computed by relaxing some of the non-anticipativity constraints. The proposed procedure is tested on a multistage stochastic batch-sizing problem. (c) 2004 Published by Elsevier B.V.
The purpose of this paper is to investigate branch and bound strategies and the comparison of branch and cut with pure branch and bound approaches on high speed telecommunication network design under uncertainty. We m...
详细信息
The purpose of this paper is to investigate branch and bound strategies and the comparison of branch and cut with pure branch and bound approaches on high speed telecommunication network design under uncertainty. We model the problem as a two-stage stochastic program with discrete first-stage (investment) variables. Two formulations of the problem are used. The first one with general integer investment variables and the second one, a variant of the first model, with 0-1 investment variables. We present computational results for three solution approaches: the integer L-shaped (Benders) decomposition, a branch and bound framework and a disjunctive cutting plane method.
This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a n...
详细信息
This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.
Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a...
详细信息
Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochasticprogramming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.
stochastic integer programming problems under probabilistic constraints are considered. Deterministic equivalent formulations of the original problem are obtained by using p -efficient points of the distribution funct...
详细信息
stochastic integer programming problems under probabilistic constraints are considered. Deterministic equivalent formulations of the original problem are obtained by using p -efficient points of the distribution function of the right hand side vector. A branch and bound solution method is proposed based on a partial enumeration of the set of these points. The numerical experience with the probabilistic lot-sizing problem shows the potential of the solution approach and the efficiency of the algorithms implemented.
We consider the problem of scheduling daily hydro-electricity generation in a river valley. Each generating station in this river valley has a number of turbines which incur fixed charges on startup and have a generat...
详细信息
We consider the problem of scheduling daily hydro-electricity generation in a river valley. Each generating station in this river valley has a number of turbines which incur fixed charges on startup and have a generation efficiency which varies nonlinearly with flow. With appropriate approximations the problem of determining what turbine units to commit in each half hour of the day can be formulated as a large mixed-integer linear programming problem. In practice the generation required from this group of stations in each half hour is often different from that forecast. We investigate the impact of this uncertainty on the unit commitment by using an optimization-based heuristic to give an approximate solution to the stochastic problem. (C) 2000 Elsevier Science B.V. All rights reserved.
We consider a mixed 0-1 integerprogramming problem with dual block-angular structure arising in two-stage stochasticprogramming. A relaxation is proposed such that the problem is decomposed into subproblems each cor...
详细信息
We consider a mixed 0-1 integerprogramming problem with dual block-angular structure arising in two-stage stochasticprogramming. A relaxation is proposed such that the problem is decomposed into subproblems each corresponding to the outcomes of the random variable. The convex hull of feasible solutions for the re laxation is characterized using results from disjunctive programming and it is shown how Lift-and-Project cuts can be generated for one subproblem and made valid far different outcomes. (C) 1997 Elsevier Science B.V.
暂无评论