Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis

In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the expected integer recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest improvements to reduce the number of function evaluations needed.     

A Finite Algorithm for Global Minimization of Separable Concave Programs

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes.     

Solving Nonlinear Programming Problems with Noisy Function Values and Noisy Gradients

An efficient algorithm for solving nonlinear programs with noisy equality constraints is introduced and analyzed. The unknown exact constraints are replaced by surrogates based on the bundle idea, a well-known strategy from nonsmooth optimization. This concept allows us to perform a fast computation of the surrogates by solving simple quadratic optimization problems, control the memory needed by the algorithm, and prove the differentiability properties of the surrogate functions. The latter aspect allows us to invoke a sequential quadratic programming method. The overall algorithm is of the quasi-Newton type. Besides convergence theorems, qualification results are given and numerical test runs are discussed.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Affine scaling algorithm fails for semidefinite programming

In this paper, we introduce an affine scaling algorithm for semidefinite programming (SDP), and give an example of a semidefinite program such that the affine scaling algorithm converges to a non-optimal point. Both our program and its dual have interior feasible solutions and unique optimal solutions which satisfy strict complementarity, and they are non-degenerate everywhere.     

关于E-凸函数及E-凸规划几个错误结论的修正

本文研究Youness在1999年建立的有关E凸函数和E规划的结论.利用E凸函数和E凸规划的基本性质和优化分析技术,获得了有关E凸函数E凸规划的几个错误结论的修正..     

An integer goal programming model for hazardous waste treatment and disposal

The improper handling and disposal of hazardous wastes cause threats to human health and the environment. One reason for the improper handling and disposal of these wastes is that not much consideration is usually given to the logistical aspects of hazardous waste systems. In this paper an integer goal programming model is developed that takes into consideration the multiple goals and needs of many groups involved in managing and planning hazardous waste systems. The model can easily be implemented and can be used to address many of the issues related to facility location, recycling, treatment, and disposal of hazardous wastes.     

An Interval-Parameter Fuzzy Approach for Multiobjective Linear Programming Under Uncertainty

An interval-parameter fuzzy linear programming method (IFMOLP) is proposed in this study for multiple objective decision-making under uncertainty. As a hybrid of interval-parameter and fuzzy methodologies, the IFMOLP incorporates interval-parameter linear programming and fuzzy multiobjective programming approaches to form an integrated optimization system. The method inherits advantages of interval-parameter programming, and allows uncertainties and decision-makers’ aspirations to be effectively communicated into its programming processes and resulting solutions. Membership functions for both objectives and constraints are formulated to reflect uncertainties in different system components and their interrelationships. An interactive solution procedure has been developed based on solution approaches of the interval-parameter and fuzzy programming techniques, plus necessary measures for handling the multiobjective feature. A didactic example is provided in the paper to illustrate the detailed solution process. Possibilities of further improvements by seeking Pareto optimum and incorporating flexible preference within constraints are also discussed.     

重力输水管道优化设计方法研究

针对重力输水管道设计中存在的问题，文章以管道造价最小为目标，应用动态规划，提出了一种新的重力输水管道优化设计方法，对输水管的当量管径、流量分配、连接管设置与可靠性校核计算等问题作了探讨。该方法可用于沿线有节点流量流出的并联输水管道优化设计，能明显节省投资，有良好的实用性