Integrating modeling,algorithm design,and computational implementation to solve a large-scale nonlinear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis*, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

A successive quadratic programming algorithm with global and superlinear convergence properties

This paper presents a successive quadratic programming algorithm for solving general nonlinear programming problems. In order to avoid the Maratos effect, direction-finding subproblems are derived by modifying the second-order approximations to both objective and constraint functions of the problem. We prove that the algorithm possesses global and superlinear convergence properties.This work was supported in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

利用最小调整法求解特殊的二维0-1规划

具有特殊约束的二维0-1规划的实际应用广泛,在解法中多是应用传统算法,或是在它基础上进行改进,但是此类解法计算繁琐不易推广.针对这种情形,本文引入最小调整法处理此类问题,并将其与传统算法进行对比,充分展示了该方法的优越性,呈现出灵活、方便、简单、易行的特点.通过举例验证了方法的有效性.     

飞行员数量的宏观估计与调控模型

本文提出一种估计与调控飞行员宏观数量的方法.文章给出了当航空兵的兵力规模保持稳定、只考虑飞行员年龄分布的情况下,战斗部队飞行员和航校教员总数量与每年的补充量、淘汰率、服役年限之间的函数关系;给出了当航空兵的兵力规模需要变更时,尽快达到变更目标的数学规划模型,模型考虑了每年的补充量、淘汰率、服役年限以及航校学制、规模和效率之间的关系.     

Supply chain optimization of petroleum organization under uncertainty in market demands and prices

A multi-period stochastic planning model has been developed and implemented for a supply chain network of a petroleum organization operating in an oil producing country under uncertain market conditions. The proposed supply chain network consists of all activities related to crude oil production, processing and distribution. Uncertainties were introduced in market demands and prices. A deterministic optimization model was first developed and tested. The impact of uncertainty on the supply chain was studied by performing a sensitivity analysis in which ±20% deviations were introduced in market demands and prices of different commodities. A stochastic formulation was then proposed, which is based on the two-stage problem with finite number of realizations. The proposed stochastic programming approach proved to be quite effective in developing resilient production plans in light of high degree of uncertainty in market conditions. The anticipated production plans have a considerably lower expected value of perfect information (EVPI). The main conclusion of this study is that for an oil producing country with oil processing capabilities, the impact of economic uncertainties may be tolerated by an appropriate balance between crude exports and processing capacities.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Advanced basis construction in linear programming

This paper considers basis construction in a linear program when the number of activities with basic status is not equal to the number of rows in the particular scenario. This arises when starting with an ‘advanced basis’, obtained from a solution to another scenario. The goal here is to provide a triangular-seeking algorithm that takes advantage of structural properties during the construction of a basis agenda. For completeness, some facts, which are known but have not been published, are given about choosing an advanced basis and about spikes.     

Numerical examples of the behavior of REQP on nonlinear programming problems involving linear dependence among the constraint normals

This report illustrates, by means of numerical examples, the behavior of the constrained minimization algorithm REQP in situations where the active constraint normals are not linearly independent. The examples are intended to demonstrate that the presence of the penalty parameter in the equations for calculating the Lagrange multiplier estimates enables a useful search direction to be computed. This is shown to be true, whether the dependence among the constraint normals occurs at the solution or in some other region.     

动态规划的表格结构(Ⅱ)——关于网络中第一类最短路问题

本文讨论阶段数不确定、有限的情形。首先提出了三个有关代数结构的算法定理,使熟知的 Ford 算法,Gauss-Seidel 算法,Yen 第一、第二算法都是它们的特例。由于我们提出了 Yen 第三、第四算法,使得无回路网络中的问题,以及正网络中的 Dijkstra 算法的论证联成一线。而且,它们都可在前文(Ⅰ)所提出的表格上作数值计算。     

Relaxation techniques for strictly convex network problems

Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments — aimed at the improved efficiency of the algorithm — are presented.This research was supported in part by National Science Foundation Grant No. DCR-8401098-A01.