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 network-related nuclear power plant model with an intelligent branch-and-bound solution approach

This paper presents a network model with discrete requirements for a nuclear power plant. The model determines the batch size and timing for nuclear unit refueling and how much energy should be produced by nuclear and non-nuclear units for each time period to satisfy forecasted demand with minimum total operating costs over the planning horizon. Efficient modeling and solution strategies are developed which constitute a merger of operations research and artificial intelligence. A branch-and-bound solution approach is combined with a pattern recognition component, involving non-parametric discrimination analyses, to select branching variables and directions. By coupling this approach with network optimization techniques to exploit the underlying network structure of the problem, substantial improvements are obtained both in solution quality and solution efficiency.This research was supported in part by the Center for Business Decision Analysis, the Hugh Roy Cullen Centennial Chair in Business Administration, and the Office of Naval Research under contract N00014-87-K-0190. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. CENTER FOR BUSINESS DECISION ANALYSIS Darwin Klingman, Director The University of Texas at Austin Austin, TX 78712, U.S.A.     

A modeling/solution approach for optimal deployment of a weapons arsenal

This paper reports a real-world application of a large-scale assignment/allocation mixed-integer program for optimal deployment and targeting of missiles for the U.S. Strategic Air Command. We provide a NETFORM model that reduces the number of zero-one variables of a standard integer programming formulation by more than two orders of magnitude (by factors approaching 500) and a tailored NETFORM software system that solves problems involving 2,400 zero-one variables and 984,000 continuous variables to within 99.9% of optimality in less than one minute on an IBM 4381.This research was supported in part by the Center for Business Decision Analysis, the Hugh Roy cullen Centennial Chair in Business Administration, and the Office of Naval Research under Contract N00014-87-K-0190. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Preface to topics in data envelopment analysis

This paper serves as an introduction to a series of three papers which are directed to different aspects of DEA (Data Envelopment Analysis) as follows: (1) uses and extensions of window analyses' to study DEA efficiency measures with an illustrative applications to maintenance activities for U.S. Air Force fighter wings, (2) a comparison of DEA and regression approaches to identifying and estimating, sources of inefficiency by means of artificially generated data, and (3) an extension of ordinary (linear programming) sensitivity analyses to deal with special features that require attention in DEA. Background is supplied in this introductory paper with accompanying proofs and explanations to facilitate understanding of what DEA provides in the way of underpinning for the papers that follow. An attempt is made to bring readers abreast of recent progress in DEA research and uses. A synoptic history is presented along with brief references to related work, and problems requiring attention are also indicated and possible research approaches also suggested.This research was partly supported by the National Science Foundation and USARI Contract MDA 903-83-K0312, with the Center for Cybernetic Studies, the University of Texas at Austin. It was also partly supported by the IC² Institute at the University of Texas at Austin. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Extremal and game-theoretic characterizations of the probabilistic approach to income redistribution

In this paper, we cast the problem of income redistribution in two different ways, one as a nonlinear goal programming model and the other as a game theoretic model. These two approaches give characterizations for the probabilistic approach suggested by Intriligator for this problem. All three approaches reinforce the linear income redistribution plan as a desirable mechanism of income redistribution.This research was partly supported by ONR Contract No. N00014-82-K-0295 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas.     

Solving singularly constrained generalized network problems

The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring single upper bound constraints, containsm + 1 rows which may be ordered such that each column has at most two non-zero entries in the firstm rows. The paper describes efficient procedures for solving such problems and presents computational results which indicate that, on large problems, these procedures are at least twenty-five times more efficient than the state of the art LP systemapex-iii.This research was partly supported by ONR Contract N00014-76-C-0383 with Decision Analysis and Research Institute and by Project NR047-021, ONR Contracts N00014-75-C-0616 and N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Quasiconcavity and nondominated solutions in multiobjective programming

In the multiobjective programming literature, the concavity of the objectives is usually assumed to be a sufficient condition in seeking Pareto-optimal solutions. This paper investigates nondominated solutions associated with dominance cones via the assumption of the quasiconcavity of the objectives. Necessary as well as sufficient conditions for such quasiconcave multiobjective programming problems are obtained.The author is indebted to one of the referees for detailed constructive comments and suggestions. Thanks are also due to the late Professor Abraham Charnes, University of Texas at Austin, and Professor Zhimin Huang, Adelphi University.     

The role of duality in optimization problems involving entropy functionals with applications to information theory

We consider infinite-dimensional optimization problems involving entropy-type functionals in the objective function as well as as in the constraints. A duality theory is developed for such problems and applied to the reliability rate function problem in information theory.This research was supported by ONR Contracts N00014-81-C-0236 and N00014-82-K-0295 with the Center for Cybernetics Studies, University of Texas, Austin, Texas. The first author was partly supported by NSF.     

A simplified homogeneous and self-dual linear programming algorithm and its implementation

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.Research supported in part by NSF Grant DDM-9207347 and by an Iowa College of Business Administration Summer Grant.Part of this work was done while the author was on a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University, Ithaca, NY 14853, USA, supported in part by the Cornell Center for Applied Mathematics and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.     

Confidence structures in decision making

Decision making is defined in terms of four elements: the set of decisions, the set of outcomes for each decision, a set-valued criterion function, and the decision maker's value judgment for each outcome. Various confidence structures are defined, which give the decision maker's confidence of a given decision leading to a particular outcome. The relation of certain confidence structures to Bayesian decision making and to membership functions in fuzzy set theory is established. A number of schemes are discussed for arriving atbest decisions, and some new types of domination structures are introduced.This research was partly supported by Project No. NR-047-021, ONR Contract No. N-00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas, and by ONR Contract No. N-00014-69-A-0200-1012 with the University of California, Berkeley, California.     

A sparse sequential quadratic programming algorithm

Described here is the structure and theory for a sequential quadratic programming algorithm for solving sparse nonlinear optimization problems. Also provided are the details of a computer implementation of the algorithm along with test results. The algorithm maintains a sparse approximation to the Cholesky factor of the Hessian of the Lagrangian. The solution to the quadratic program generated at each step is obtained by solving a dual quadratic program using a projected conjugate gradient algorithm. An updating procedure is employed that does not destroy sparsity.     

Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

Layering strategies for creating exploitable structure in linear and integer programs

The strategy of subdividing optimization problems into layers by splitting variables into multiple copies has proved useful as a method for inducing exploitable structure in a variety of applications, particularly those involving embedded pure and generalized networks. A framework is proposed in this paper which leads to new relaxation and restriction methods for linear and integer programming based on our extension of this strategy. This framework underscores the use of constructions that lead to stronger relaxations and more flexible strategies than previous applications. Our results establish the equivalence of all layered Lagrangeans formed by parameterizing the equal value requirement of copied variables for different choices of the principal layers. It is further shown that these Lagrangeans dominate traditional Lagrangeans based on incorporating non-principal layers into the objective function. In addition a means for exploiting the layered Lagrangeans is provided by generating subgradients based on a simple averaging calculation. Finally, we show how this new layering strategy can be augmented by an integrated relaxation/restriction procedure, and indicate variations that can be employed to particular advantage in a parallel processing environment. Preliminary computational results on fifteen real world zero-one personnel assignment problems, comparing two layering approaches with five procedures previously found best for those problems, are encouraging. One of the layering strategies tested dominated all non-layering procedures in terms of both quality and solution time.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222 with the Center for Business Decision Analysis and by the US Department of Agriculture Contract 51-3142-4020 with Management Science Software Systems.     

Numerical experience with a polyhedral-norm CDT trust-region algorithm

In this paper, we study a modification of the Celis-Dennis-Tapia trust-region subproblem, which is obtained by replacing thel ₂-norm with a polyhedral norm. The polyhedral norm Celis-Dennis-Tapia (CDT) subproblem can be solved using a standard quadratic programming code.We include computational results which compare the performance of the polyhedral-norm CDT trust-region algorithm with the performance of existing codes. The numerical results validate the effectiveness of the approach. These results show that there is not much loss of robustness or speed and suggest that the polyhedral-norm CDT algorithm may be a viable alternative. The topic merits further investigation.The first author was supported in part by the REDI foundation and State of Texas Award, Contract 1059 as Visiting Member of the Center for Research on Parallel Computation, Rice University, Houston, Texas, He thanks Rice University for the congenial scientific atmosphere provided. The second author was supported in part by the National Science Foundation, Cooperative Agreement CCR-88-09615, Air Force Office of Scientific Research Grant 89-0363, and Department of Energy Contract DEFG05-86-ER25017.     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Characterization of optimality in convex programming without a constraint qualification

Necessary and sufficient conditions of optimality are given for convex programming problems with no constraint qualification. The optimality conditions are stated in terms of consistency or inconsistency of a family of systems of linear inequalities and cone relations.This research was supported by Project No. NR-047-021, ONR Contract No. N00014-67-A-0126-0009 with the Center for Cybernetics Studies, The University of Texas; by NSF Grant No. ENG-76-10260 at Northwestern University; and by the National Research Council of Canada.     

A computer graphics-based Decision Support System for multiple objective linear programming

In this paper we propose a computer-graphics based Decision Support System for multiple objective linear programming that builds on the VIG system (Visual Interactive Goal programming). The essential part of the VIG system is Pareto Race, a dynamic and visual approach for exploring the efficient frontier of a multiple objective linear programming problem. Our objective is to extend Pareto Race to large-scale multiple objective linear programming. The approach works with any efficient solutions that are in general not extreme point solutions. Interactive use of computer graphics plays a central role. The approach, the underlying theory, and an illustrative example are described.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

适应编程需要的一种动态规划模型解法

由计算机软件编程需要出发,对库存管理中的一种动态规划方法进行了讨论,推导出了统一规范表达的允许状态集合和允许决策集合,并由此给出了计算程序框图,为计算机处理类似问题提供了依据。