bluuebunny/crossref_metadata_2025_split huggingface dataset:
Solving Piecewise-Linear Programs: Experiments with a Simplex Approach
Authors: Fourer Robert , Marsten Roy E. 
Published: October 2008

We report tests of CPLP, a piecewise-linear simplex implementation based on the XMP subroutine library. Using test problems of various shapes and origins, we judge CPLP against a comparable linear bounded-variable simplex code that is applied to equivalent linear programs. Our evidence indicates that CPLP is typically 2 to 3 times faster in solving the test problems that are most significantly piecewise-linear; previously predicted advantages of the piecewise-linear simplex approach are observed to occur, though with different combinations of advantages being relevant in different cases. The savings achieved by CPLP appear likely to extend, moreover, to the costs involved in formulating, generating and analyzing piecewise-linear programs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Solving Large Sparse Nonlinear Programs Using GRG
Authors: Smith Stuart , Lasdon Leon 
Published: October 2008

We describe a feasibility-retaining GRG algorithm for large sparse nonlinear programs of general form. Its FORTRAN implementation, LSGRG, is enhanced by heuristics which aid in basis selection, combatting degeneracy, dynamic tolerance adjustment, and predicting Newton failures. Key roles are also played by efficient procedures for basis inversion and by both pure and limited memory BFGS methods for computing the search direction. The design goal for LSGRG is maximum reliability with at least acceptable speed. Extensive computational tests on both FORTRAN and GAMS models indicate that LSGRG is promising in this regard. Comparisons are presented with GRG2, a sparsity oriented SQP code, and MINOS, indicating that LSGRG is a useful complement to MINOS in a multi-solver NLP environment. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Exploiting Special Structure in Primal Dual Interior Point Methods
Authors: Hurd James K. , Murphy Frederic H. 
Published: October 2008

This paper examines special sparsity structures in linear programs that can accelerate calculations in the primal dual method. Our results extend previous research by quantifying more precisely conditions for retaining sparsity during iterations. Special structures that meet these conditions include simple upper bounds, variable upper bounds, and chained upper bounds. We describe an implementation and illustrate the benefits for the uncapacitated facility location problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Scheduling Checks and Saves
Authors: Boguslavsky Leonid B. , Coffman Edward G. , Gilbert Edgar N. , Kreinin Alexander Y. 
Published: October 2008

A job is to be run on a machine subject to random failures. Failures are not self-evident. They must be detected by explicit tests, or checks. Checks detect failures to avoid wasting time working with a defective machine. After each successful check one has the option of saving the work just completed. Then, when failures occur, only the work done since the last save must be repeated. Effective use of checks and saves requires a compromise, since these procedures are themselves time-consuming. Scheduling saves alone, when failures are evident as soon as they occur, is often called checkpointing. The novelty of the model studied here stems from not assuming that failures are self-evident. This compounds the usual checkpointing problem by requiring schedules of failure checks as well as saves. This paper gives schedules of checks and saves that minimize the expected total time required to complete a given job. The most general failure mechanism considered is a renewal process. The Poisson process receives special emphasis, as it leads to the simplest results. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Review
Authors: Vohra Rakesh V. 
Published: October 2008

Review of F.S. Hillier and G.J. Lieberman (1990) Introduction to Mathematical Programming, 5th Edition, and Introduction to Stochastic Models in Operations Research, 5th Edition, McGraw-Hill Publishing Company, Hightstown, NJ. Reviewed by Rakesh V. Vohra, Faculty of Management Sciences, Ohio State University, Columbus, Ohio 43210, USA. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem
Authors: Lodwick Weldon A. 
Published: October 2008

Methods to uncover redundancies, infeasibilities and bound structures on variables for nonlinear constraint sets are developed. It is these methods that comprise the preprocessing that is derived here. Bilinear constraint sets ate used to illustrate the methods. Thus, special emphasis is given to bilinearities and a nonlinear programming model in which bilinearities arise naturally, a generic petroleum refinery model and its associated pooling problem. The usefulness of the approaches developed herein include their applications to preoptimization/postoptimization analyses of nonlinear programming problems and the generation of starting values for nonlinear programming optimizers. Numerical examples are given that use existing optimization packages in conjunction with a computer-aided analysis system, and point to the practical implementability of the methods derived. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Generalized Networks: Parallel Algorithms and an Empirical Analysis
Authors: Clark Robert H. , Kennington Jeffery L. , Meyer Robert R. , Ramamurti Muthukrishnan 
Published: October 2008

The objective of this research was to develop and empirically test new simplex-based parallel algorithms for the generalized network optimization problem. One of these algorithms is essentially a “data parallel” method in which each processor executes identical code on a portion of the data. (However, since the data sets are not necessarily disjoint, “locks” are used to ensure exclusive access.) A second algorithm exhibits “control parallelism,” using different processors to simultaneously execute the different subtasks of the simplex method. “Locks” are not needed in this second approach, but, instead, at the beginning of each pivot, an “audit” of the proposed entering arc is performed in order to ensure correctness of the method. These parallel algorithms were implemented on the Sequent Symmetry multiprocessor, empirically tested on a variety of problems produced by two random problem generators, and compared with two leading state-of-the-art serial codes. Good speedups were obtained relative to the serial codes, and the relative performance of the two parallel methods was found to be dependent on connectedness properties of the optimal solutions of the test problems. The largest test problem, a generalized transportation problem having 30,000 nodes and 1.2 million arcs was optimized in approximately 11 minutes by our parallel code, displaying a speedup of 13 on 15 processors. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Optimal Algorithm for the Orienteering Tour Problem
Authors: Ramesh R. , Yoon Yong-Seok , Karwan Mark H. 
Published: October 2008

Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangean relaxation are studied, and several implementation features to improve the performance of the algorithm are presented. Detailed computational results for problems having up to 150 control points are presented. The results show that the proposed approach is viable for solving problems of medium to large size. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Massively Parallel Algorithms for Singly Constrained Convex Programs
Authors: Nielsen Soren S. , Zenios Stavros A. 
Published: October 2008

We develop four iterative algorithms for the solution of separable, convex nonlinear optimization problems with a single linear constraint and bounded variables. The design of the algorithms makes them suitable for implementation on massively parallel computers of the SIMD (i.e., Single Instruction, Multiple Data) class. The algorithms are specialized for the solution of network problems whereby the linear constraint reflects conservation of flow. Details of implementations on a Connection Machine CM-2 are reported. The numerical results indicate that all algorithms are very effective, and can solve very large problems. Three of the algorithms are also very efficient when implemented on the massively parallel system. Interestingly, the most effective algorithm (in number of steps required to solve the test problems) is the least efficient (in solution time) when implemented in parallel. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Jackknifing under a Budget Constraint
Authors: Glynn Peter W. , Heidelberger Philip 
Published: October 2008

In this paper, we consider the problem of estimating a parameter α that can be expressed as a nonlinear function of sample means. We develop a jackknife estimator for α that is appropriate to computational settings in which the total computer budget to be used is constrained. Despite the fact that the jackknifed observations are not i.i.d., we are able to show that our jackknife estimator reduces bias without increasing asymptotic variance. This makes the estimator particularly suitable for small sample applications. Because a special case of this estimator problem is that of estimating a ratio of two means, the results in this paper are partinent to regenerative steady-state simulations. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Dynamic Three-Dimensional Linear Programming
Authors: Eppstein David 
Published: October 2008

We perform linear programming optimizations on the intersection of k polyhedra in R3, represented by their outer recursive decompositions, in expected time O(k log k log n + √k log k log3 n). We use this result to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, we describe an improved solution to the planar 2-center problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms
Authors: Arkin Esther M. , Kedem Klara , Mitchell Joseph S. B. , Sprinzak Josef , Werman Michael 
Published: October 2008

We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint “noise regions.” We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity) and noise regions (circles, squares, polygons). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Fast Algorithms for Geometric Traveling Salesman Problems
Authors: Bentley Jon Jouis 
Published: October 2008

This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt). Experiments indicate that most of the algorithms run in O(N log N) time on uniform data sets, and many run almost as fast on very nonuniform data. The program that implements the algorithms is able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours. The algorithms and program apply to many distance metrics and dimensions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Voronoi Partition of a Network and Its Implications in Location Theory
Authors: Hakimi S. Louis , Labbé Martine Labbé , Schmeichel Edward 
Published: October 2008

Given a network N(V, E) and a set of points Xp = {x1, …, xp} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x1), …, T(xp). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting Xp so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Optimal Bisection of a Polygon
Authors: Koutsoupias Elias , Papadimitriou Christos H. , Sideri Martha 
Published: October 2008

We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any ratio. In contrast, we give a dynamic programming algorithm which finds a subdivision into two parts with total perimeter at most that of the optimum bisection, such that the two parts have areas within ε of each other; the time is polynomial in the number of sides of the polygon, and 1/ε. When the polygon is convex, or if the parts are required to be connected, then the exact problem can be solved in quadratic time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Dimensional Analysis in Mathematical Modeling Systems: A Simple Numerical Method
Authors: Bhargava Hemant K. 
Published: October 2008

This paper develops a numerical method for dimensional analysis, which has previously been treated as a problem requiring symbolic mathematics techniques. The numerical method obeys the laws of dimensional arithmetic. This is achieved by specifying an encoding of units of measurement as prime numbers, and manipulating the resulting expressions numerically. The unique factorization theorem is applied to show that this method makes trivial the problems of dimensional simplification and verification of dimensional equivalency, which are central issues in dimensional arithmetic. The solution has applications in mathematical modeling systems, chiefly in the model validation and model solution phases. The paper also describes a first-order logic language, Ldim, which can be used in such systems to represent and manipulate dimensional information. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Measuring Congestion for Dynamic Task Allocation in Distributed Simulation
Authors: Shanker Murali S. , Kelton W. David , Padman Rema 
Published: October 2008

An important factor affecting the performance of distributed simulations running on parallel-processing computers is the allocation of logical processes to the available physical processors. An inefficient allocation can result in excessive communication times and unfavorable load conditions. This leads to long run times, possibly giving performance worse than that with a uniprocessor sequential event-list implementation. But the efficiency of any allocation strategy is dependent on the metric, or measure, it uses to characterize the load in the distributed system. This paper presents a simple and intuitive way of measuring and reallocating the load when the objective is to minimize simulation run time. The metric, based on estimating measures of message utilization at each processor, has been used in an adaptive scheme for load allocation, and experiments on an iPSC/2 Hypercube indicate that it successfully characterizes the load for purposes of reducing simulation run time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Selecting Parameters of Phase Distributions: Combining Nonlinear Programming, Heuristics, and Erlang Distributions
Authors: Johnson Mary A. 
Published: October 2008

Because of their denseness and tractability, phase (PH) distributions are widely used in probabilistic modeling. However, full exploitation of the favorable properties of PH distributions requires the ability to specify PH-distribution parameters to obtain adequate distribution approximations. We combine nonlinear-programming techniques and heuristics to select mixtures of Erlang distributions (a subset of the PH family) to approximate non-PH distributions. Heuristics are used to select the number of Erlang distributions mixed and the order of each mixed Erlang distribution, both of which have an important effect on the range of distribution properties that can be attained. Heuristics are also used for assigning initial values and bounds to the mixing probabilities and the means of the mixed Erlang distributions. Then nonlinear-programming methods are used to determine final values of these continuous parameters. Using a variety of criteria, we show that good fits can often be obtained with a moderate amount of computation and user interaction. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Alternating Step Method for Monotropic Programming on the Connection Machine CM-2
Authors: Eckstein Jonathan 
Published: October 2008

The alternating step method is a massively parallel alternating direction method for monotropic programming, that is, convex programming with a separable objective function and linear constraints. This paper specializes the alternating step method to generalized network problems with positive semi-definite quadratic arc costs, and describes its implementation on a massively parallel computer, the Connection Machine CM-2. Extensive computational tests reveal that while the method is disappointingly slow for most problems with purely linear cost functions, it is competitive with dual relaxation methods on many problems having positive definite objectives. Furthermore, the algorithm continues to perform well even if a minority of arcs are given purely linear costs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
ALPO: Another Linear Program Optimizer
Authors: Vanderbei Robert J. 
Published: October 2008

This paper describes an implementation of the one-phase primal-dual path-following algorithm for solving linear programming problems. The design is intended to be simple, portable and robust. These design goals are achieved without sacrificing state-of-the-art performance. We give a rather complete description of the algorithm and the implementation. Computational results obtained for the NETLIB suite of problems run on a Silicon Graphics workstation are also presented. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Shortening Future-Event Lists
Authors: Fox Bennett L. 
Published: October 2008

For discrete-event simulations with many exponential variates but not necessarily continuous-time Markov chains, we shorten the future-event list. No matter how many underlying exponential variates are present in principle, at any time, at most one exponential variate is on the future-event list. We point out how to find quickly the corresponding event so that overall computational complexity of the work to generate transitions is reduced. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Production Scheduling System
Authors: Nussbaum Miguel , Parra Eduardo A. 
Published: October 2008

A knowledge-based scheduling system is described for a real case study. The problem is solved for a plant with multipurpose machines and job-shop batch characteristics. Given the available machines, the list of production orders, the products' due-dates and process description for each product, the system sequences machines for all required products, using an heuristic approach based on the information of the status of the plant and the characteristics of the orders. This work describes in detail several concepts defined in this project. A qualitative analysis of the advantages and disadvantages of these ideas is given, and empirical results are exhibited using real data from the plant. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Separable Quadratic Programming via a Primal-Dual Interior Point Method and its Use in a Sequential Procedure
Authors: Carpenter Tamra J. , Lustig Irvin J. , Mulvey John M. , Shanno David F. 
Published: October 2008

This paper extends a primal-dual interior point procedure for linear programs to the case of convex separable quadratic objectives. Included are efficient procedures for: attaining primal and dual feasibility, variable upper bounding, and free variables. A sequential procedure that invokes the quadratic solver is proposed and implemented for solving linearly constrained convex separable nonlinear programs. Computational results are provided for several large test cases from stochastic programming. The proposed methods compare favorably with MINOS, especially for the larger examples. The nonlinear programs range in size up to 8,700 constraints and 22,000 variables. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
State-of-the-Art Survey—Constrained Nonlinear 0–1 Programming
Authors: Hansen Pierre , Jaumard Brigitte , Mathon Vincent 
Published: October 2008

We consider nonlinear programs in 0–1 variables with nonlinear constraints and survey the main approaches to their solution: (i) linearization; (ii) algebraic methods; (iii) enumerative methods and (iv) cutting-plane methods. We also present an extensive computational comparison of algorithms of all four categories. Enumerative methods appear to be the most promising. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.