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.     

Existence and stability of large scale nonlinear oscillations in suspension bridges

A nonlinear model of a suspension bridge is considered in which large-scale, stable oscillatory motions can be produced by constant loading and a small-scale, external oscillatory force. Loud's implicit-function theoretic method for determining existence and stability of periodic solutions or nonlinear differential equations is extended to a case of a non-differentiable nonlinearity.Author partially supported by NSF under Grant DMS 8318204 and AFOSR Grant 85-0330.Author partially supported by NSF under Grant DMS 9519882.Author partially supported by NSF under Grant DMS 8519776.     

Symmetries of excessive measures of Markov processes

Research supported in part by AFOSR 85-0330 and NSF DMS 8318204     

Inter- or intramolecular electron transfer between triruthenium clusters: we’ll cross that bridge when we come to it

The purpose of this review is to examine the fundamental differences between intermolecular self-exchange vs. intramolecular ET in mixed-valence complexes based on similar triruthenium structural units. The role of orbital overlap between ancillary ligands of the electron donor and acceptor are considered in self-exchange reactions which are found to be strongly adiabatic and again in bridged mixed-valence systems. The method of infrared (IR) reflectance spectroelectrochemistry for the determination of extremely fast (10¹¹–10¹³ s^?1) ET rate constants is reviewed as a tool to provide quantitative information about the time scales of localization and delocalization. The role of internal vibrations of the bridging ligand in strongly delocalized mixed-valence ions is investigated by resonance Raman and IR spectroscopies. The role of solvent dipolar relaxation times in determining the rates of ultrafast intramolecular ET reactions is reviewed in the context of inorganic mixed-valence chemistry. Finally, the concept of Robin–Day Class II/III “borderline” complexes is considered, and a concise definition of the localized to delocalized transition is provided in terms of the relative contributions of external solvent and internal complex ion vibrational modes to ET.     

The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms

We identify new solvable cases of the travelling salesman problem (TSP) by an indirect analysis that has useful consequences. First, we develop new procedures for the TSP that require only linear time to execute and yield TSP tours that are better than an exponential number of alternative tours. We then identify special subgraphs, easily generated, so that our method yields these outcomes for every instance of these subgraphs. Finally, when the associated costs satisfy prescribed conditions, we show the solutions produced by these algorithms are optimal and thus we have new solvable cases of the TSP. Besides possible practical applications to problems that may exhibit these cost conditions, our algorithms may also be applied as subroutines within more complex metaheuristics. Our methods extend in a natural way to bottleneck TSP formulations, and their underlying results raise new theoretical questions about the analysis of heuristics for hard combinatorial problems.     

Solving the maximum edge weight clique problem via unconstrained quadratic programming

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.     

A Fritz John optimality condition using the approximate subdifferential

A Fritz John type first-order optimality condition is derived for infinite-dimensional programming problems involving the approximate subdifferential. A discussion of the important properties of the approximate subdifferential for locally Lipschitz functions is included. In addition, an upper semicontinuity condition is obtained for an approximate subdifferential multifunction related to the class of locally compactly Lipschitzian mappings.The authors would like to thank two anonymous referees for their detailed comments which have significantly improved the presentation of this paper. In particular, they thank the first referee for pointing out a number of important references on the approximate subdifferential and the second referee for various corrections and for bringing an important recent reference (Ref. 17) to their attention.     

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.     

The heat of fusion of polybutene-1

Through x-ray diffraction, the changes in the unit-cell parameters of crystal forms I and II of polybutene-1 were followed from room temperature to the melting point. These data were combined with the results of other measurements to computer the heats and entropies of fusion by use of the Clapeyron equation.