A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.     

基于可信性理论的运输机会约束模型

基于可信性理论,将提出一类带有模糊参数的运输计划机会约束模型.然后,讨论可信性函数的逼近方法并且设计一个基于逼近方法、神经网络和遗传算法的启发式算法来求解这个模糊运输计划机会约束模型.最后,给出一个数值例子来表明所设计算法的实用性和有效性.     

Stochastic modelling of reservoir operations

The nature of hydrologic parameters in reservoir management models is uncertain. In mathematical programming models the uncertainties are dealt with either indirectly (sensitivity analysis of a deterministic model) or directly by applying a chance-constrained type of formulation or some of the stochastic programming techniques (LP and DP based models). Various approaches are reviewed in the paper. Moran's theory of storage is an alternative stochastic modelling approach to mathematical programming techniques. The basis of the approach and its application is presented. Reliability programming is a stochastic technique based on the chance-constrained approach, where the reliabilities of the chance constraints are considered as extra decision variables in the model. The problem of random event treatment in the reservoir management model formulation using reliability programming is addressed in this paper.     

A GRASP metaheuristic for the robust mapping and routing of dataflow process networks on manycore architectures

In this paper, we study the problem of joint placement and routing, both in the deterministic and stochastic cases, arising in the field of compilation of dataflow applications for manycore architectures. A GRASP algorithm is first proposed for solving the deterministic version and extended afterwards to treat the chance-constrained program with uncertainty affecting the weights of a dataflow process network. Extensive computational results, on representative synthetic benchmark and real data, illustrate the practical relevance of the approach, as well as the robustness of the obtained stochastic solutions.     

Selecting tolerances in chance-constrained programming: A multiple objective linear programming approach

An importance issue concerning the practical application of chance-constrained programming is the lack of a rational method for choosing risk levels or tolerances on the chance constraints. While there has also been much recent debate on the relationship, equivalence, usefulness, and other characteristics of chance-constrained programming relative to stochastic programming with recourse, this paper focuses on the problem of improving the selection of tolerances within the chance-constrained framework. An approach is presented, based on multiple objective linear programming, which allows the decision maker to be more involved in the tolerance selection process, but does not demand a priori decisions on appropriate tolerances. An example is presented which illustrates the approach.     

Solving chance-constrained combinatorial problems to optimality

The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear relaxation built. A branch-and-cut algorithm is described to solve chance-constrained combinatorial problems to optimality. Numerical tests validate the theoretical analysis and illustrate the practical efficiency of the proposed approach.     

随机环境下资金预算问题的机会约束整数规划模型

本文基于最新的机会约束规划理论,提出了两类随机环境下资金预算问题的整数规划模型,并且设计了一种基于随机模拟的遗传算法来计算给出的模型．为了例证算法的有效性,本文给出了两类模型的数值例子,并且对其中一个例子给出了不同的参数,测试遗传算法的有效性,数值例子及测试结果均显示,本文所设计的基于随机模拟的遗传算法对于解决本文提出的两类模型是有效的．     

A Stochastic Linear Programming Model for Corn Residue Production

This paper presents the results of a stochastic linear program for estimating the supply of corn residue for use as raw material in an ethanol plant. The model is based on the production capacity of an average Illinois farm, and considers the feasibility of three mutually exclusive residue harvesting alternatives-own baling, custom baling, and cob collection. Since the potential for residue use in animal feed may be even more promising, these results are directly useful for the feed industry. They also indicate the profitability of investing in residue harvesting equipment. From a methodological point of view, the paper contrasts the results of three OR approaches, a deterministic LP approach, a stochastic LP approach, and a chance-constrained approach. Because of the stochastic nature of the problem both Monte Carlo simulation and chance-constrained programming are found to be computationally viable, even though they differ in the way they incorporate risk information.     

Randomized Decisions in Chance-Constrained Programming

Bhattacharyya and Mukherjee have both considered a particular joint randomized decision problem in chance-constrained programming. This paper shows a general approach for solving a large class of similar problems.     

Approximations for chance-constrained programming problems

This paper proposes an approximation approach to the solution of chance-constrained stochastic programming problems. The results rely in a fundamental way on the theory of convergence of sequences of measurable multifunctions. Particular results are presented for stochastic linear programming problems.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

A comparison of chance-constrained DEA and stochastic frontier analysis: bank efficiency in Taiwan

We employed both chance-constrained data envelopment analysis (CCDEA) and stochastic frontier analysis (SFA) to measure the technical efficiency of 39 banks in Taiwan. Estimated results show that there are significant differences in efficiency scores between chance-constrained DEA and stochastic frontier production function. The advanced setting of the chance-constrained mechanism of DEA does not change the instinctive differences between DEA and SFA approaches. We further find that the ownership variable is still a significant variable to explain the technical efficiency in Taiwan, irrespective of whether a DEA, CCDEA or SFA approach is used.     

A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support

We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with finite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to find provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and integer programming techniques, to combine the results of these subproblems to yield strong valid inequalities. Computational results on a chance-constrained formulation of a resource planning problem inspired by a call center staffing application indicate the approach works significantly better than both an existing mixed-integer programming formulation and a simple decomposition approach that does not use strong valid inequalities. We also demonstrate how the approach can be used to efficiently solve for a sequence of risk levels, as would be done when solving for the efficient frontier of risk and cost.     

A chance-constrained portfolio selection model with risk constraints

The paper by Huang [Fuzzy chance-constrained portfolio selection, Applied Mathematics and Computation 177 (2006) 500-507] proposes a fuzzy chance-constrained portfolio selection model and presents a numerical example to illustrate the proposed model. In this note, we will show that Huang’s model produces optimal portfolio investing in only one security when candidate security returns are independent to each other no matter how many independent securities are in the market. The reason for concentrative solution is that Huang’s model does not consider the investment risk. To avoid concentrative investment, a risk constraint is added to the fuzzy chance-constrained portfolio selection model. In addition, we point out that the result of the numerical example is inaccurate.     

Level bundle methods for constrained convex optimization with various oracles

We propose restricted memory level bundle methods for minimizing constrained convex nonsmooth optimization problems whose objective and constraint functions are known through oracles (black-boxes) that might provide inexact information. Our approach is general and covers many instances of inexact oracles, such as upper, lower and on-demand accuracy oracles. We show that the proposed level bundle methods are convergent as long as the memory is restricted to at least four well chosen linearizations: two linearizations for the objective function, and two linearizations for the constraints. The proposed methods are particularly suitable for both joint chance-constrained problems and two-stage stochastic programs with risk measure constraints. The approach is assessed on realistic joint constrained energy problems, arising when dealing with robust cascaded-reservoir management.     

Strong guidance on mitigating the effects of uncertainties in the brass casting blending problem: a hybrid optimization approach

The scrap charge optimization problem in the brass casting process is a critical management concern that aims to reduce the charge while preventing specification violations. Uncertainties in scrap material compositions often cause violations in product standards. In this study, we have discussed the aleatory and epistemic uncertainties and modelled them by using probability and possibility distributions, respectively. Mathematical models including probabilistic and possibilistic parameters are generally solved by transforming one type of parameter into the other. However, the transformation processes have some handicaps such as knowledge losses or virtual information production. In this paper, we have proposed a new solution approach that needs no transformation process and so eliminates these handicaps. The proposed approach combines both chance-constrained stochastic programming and possibilistic programming. The solution of the numerical example has shown that the blending problem including probabilistic and possibilistic uncertainties can be successfully handled and solved by the proposed approach.     

Ensuring service levels in routing problems with time windows and stochastic travel times

In the stochastic variant of the vehicle routing problem with time windows, known as the SVRPTW, travel times are assumed to be stochastic. In our chance-constrained approach to the problem, restrictions are placed on the probability that individual time window constraints are violated, while the objective remains based on traditional routing costs. In this paper, we propose a way to offer this probability, or service level, for all customers. Our approach carefully considers how to compute the start-service time and arrival time distributions for each customer. These distributions are used to create a feasibility check that can be “plugged” into any algorithm for the VRPTW and thus be used to solve large problems fairly quickly. Our computational experiments show how the solutions change for some well-known data sets across different levels of customer service, two travel time distributions, and several parameter settings.     

Inexact joint-probabilistic chance-constrained programming with left-hand-side randomness: An application to solid waste management

In practical waste management systems, amounts of waste transported and treated are not always equal on a daily basis. To distinguish between these two kinds of amounts and reflect their random relationships effectively, an inexact joint-probabilistic left-hand-side chance-constrained programming (IJLCP) method was developed and applied to a municipal solid waste management problem under dual uncertainties. Dual uncertainties are defined as two kinds of uncertainties existing in the same programming model. Improving upon conventional right-hand-side chance-constrained programming, the IJLCP can not only reflect uncertainties presented in terms of interval parameters (unit transportation/treatment costs, capacities of waste treatment facilities, waste generation rates, waste transportation/treatment amounts and so on) and left-hand-side random variables (the relationship between waste transportation and treatment amounts), but also examine the reliability of satisfying (or risk of violating) the entire system constraints. A non-equivalent but sufficient linearization form of IJLCP for solving this type of problem was proposed and proved in a straightforward manner. The performance of IJLCP was analyzed under scenarios at joint and individual probabilities and compared with the corresponding internal-parameter programming model. The results indicated that the net system costs would both decrease with increasing joint probability levels and decrease slightly at different individual probabilities with the same joint probabilities. The two types of dual uncertainties were discussed as well.     

Stochastic ultimate load analysis:models and solution methods 1

The stochastic ultimate load analysis model used in the safety analysis of engineering structures can be treated as a special case of chance-constrained problems (CCP) which minimize a stochastic cost function subject to some probabilistic constraints. Some special cases (such as a deterministic cost function with probabilistic constraints or deterministic constraints with a random cost function) for ultimate load analysis have airady been investigated by various researchers. In this paper, a generai probabilistic approach to stochastic ultimate load analysis is given. In doing so, some approximation techniques are needed due to the fact that the problems at hand are too complicated to evaluate precisely. We propose two extensions of the SQP method in which the variables appear in the algorithms inexactly. These algorithms are shown to be globally convergent for all models and locally superlinearly convergent for some special cases     

A Chance-Constrained Integer Goal Programming Model for Capital Budgeting in the Production Area

The selection of capital projects in a production environment is complicated by the existence of multiple and conflicting goals. Typical production objectives for cost minimization often conflict with goals for quality, environmental standards, labor relations, etc. This problem of project selection is further complicated by the uncertainty inherent in product demand, the key factor in production management. This paper approaches these complications by employing an integer goal programming (to compensate for multiple conflicting objectives) with chance-constrained capabilities (to reflect uncertainty in product demand). The approach is demonstrated via an in-depth case example of a production problem.