Journal of Research of
the
National Institute of
Standards and Technology
| Volume 111 | Number 2 | March-April 2006 |
|
David E. Gilsinn, Editor
Dedication
An Examination of New Paradigms for Spline Approximations
1275 kb
Lavery splines are examined in the univariate
and bivariate cases. In both
instances relaxation based algorithms for
approximate calculation of Lavery splines
are proposed. Following previous work
Gilsinn, et al. [7] addressing the bivariate
case, a rotationally invariant functional is
assumed. The version of bivariate splines
proposed in this paper also aims at irregularly
spaced data and uses Hseih-Clough-Tocher elements based on the triangulated
irregular network (TIN) concept. In this
paper, the univariate case, however, is
investigated in greater detail so as to further
the understanding of the bivariate
case.
bivariate splines; curve fitting;
Delaunay triangulation; Gauss-Seidel
iteration; Hsieh-Clough-Tocher elements;
irregular data; Lavery splines; non-oscillatory
splines; point clouds; surface fitting;
thin beam; thin plate; triangulated irregular
networks
Integer Representation of Decimal Numbers for Exact Computations
151 kb
Isotonic regression is the problem of fitting data to order constraints. This problem can be solved numerically in an efficient way by successive projections onto order simplex constraints. An algorithm for solving the isotonic regression using successive projections onto order simplex constraints was originally suggested and analyzed by Grotzinger and Witzgall. This algorithm has been employed repeatedly in a wide variety of applications. In this paper we briefly discuss the isotonic regression problem and its solution by the Grotzinger-Witzgall method. We demonstrate that this algorithm can be appropriately modified to run on a parallel computer with substantial speed-up. Finally we illustrate how it can be used to pre-process mass spectral data for automatic high throughput analysis.
isotonic regression; optimization; projection; simplex
One-Center Location With Block and Euclidean Distance
579 kb
A geometrical analysis is made of the dual
simplex algorithm applied to a linear programming
formulation of the one-center
location problem in IR2 using block distance.
A geometric rule is given, and
shown to be equivalent to the minimum
ratio rule of the simplex algorithm, for
updating the dual basis. The geometric
analysis is applied to the Euclidean distance
one-center problem and yields an
alternative updating procedure for the dual
algorithm.
block distance; fundamental
directions; linear program; one-center
location problem; polar directions; polyhedral
distance.
Optimal Facility-Location
123 kb
Dr. Christoph Witzgall, the honoree of this Symposium, can count among his many contributions to applied mathematics and mathematical operations research a body of widely-recognized work on the optimal location of facilities. The present paper offers to non-specialists a sketch of that field and its evolution, with emphasis on areas most closely related to Witzgall’s research at NBS/NIST.
mail sorting; mesometric facility; metric space; obnoxious facility; optimization
Optimization Models for Scheduling of Jobs
593 kb
This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for processing at the facility; the starting times, durations, and work station assignments for these jobs are assumed to be known. We are interested in how best to schedule a number of new jobs that the facility will be processing in the near future. We first develop a mixed integer quadratic programming model (MIQP) for this problem. Since the exact solution of this MIQP formulation is time consuming, we develop a heuristic procedure, based on existing bin packing techniques. This heuristic is further enhanced by application of certain local optimality conditions.
aircraft; bin packing; heuristic; integer programming; maintenance; optimization; scheduling.
Fast Algorithims for Structured Least Squares and Total Least Squares Problems
539 kb
We consider the problem of solving least
squares problems involving a matrix M
of small displacement rank with respect
to two matrices Z1 and Z2. We develop
formulas for the generators of the matrix
M HM in terms of the generators of M and
show that the Cholesky factorization of
the matrix M HM can be computed quickly
if Z1 is close to unitary and Z2 is triangular
and nilpotent. These conditions are
satisfied for several classes of matrices,
including Toeplitz, block Toeplitz, Hankel,
and block Hankel, and for matrices whose
blocks have such structure. Fast Cholesky
factorization enables fast solution of least
squares problems, total least squares
problems, and regularized total least
squares problems involving these classes of matrices.
block Toeplitz matrix;
displacement rank; errors in variables
method; image deblurring; structured total
least squares; Tikhonov regularization;
total least squares
Projections Onto Order Simplexes and Isotonic Regression
515 kb
Isotonic regression is the problem of fitting data to order constraints. This problem can be solved numerically in an efficient way by successive projections onto order simplex constraints. An algorithm for solving the isotonic regression using successive projections onto order simplex constraints was originally suggested and analyzed by Grotzinger and Witzgall. This algorithm has been employed repeatedly in a wide variety of applications. In this paper we briefly discuss the isotonic regression problem and its solution by the Grotzinger-Witzgall method. We demonstrate that this algorithm can be appropriately modified to run on a parallel computer with substantial speed-up. Finally we illustrate how it can be used to pre-process mass spectral data for automatic high throughput analysis.
isotonic regression; optimization; projection; simplex
Three Rings of Polyhedral Simple Functions
107 kb
We survey three ways to multiply elements of the additive subgroup of the group of real-valued functions on Rd which is generated by the indicator functions of polyhedra. In the resulting commutative rings, identities often correspond to useful techniques of decomposition of polyhedra. We are led immediately to various interesting topics, including Ehrhart polynomials, mixed volumes, Gram’s relation, and transversal characteristics.
convex polyhedra; Ehrhart polynomials; Gram’s relation; mixed volumes; transversal characteristic; valuation
Analysis of Interior-Point Paths
159 kb
Infeasible-interior-point paths are the main tools in interior-point methods for solving many kinds of optimization problems. These paths are usually parametrized by a penalty-parameter r ↓ 0 and further parameters describing their off-centrality and infeasiblilty. Starting with an early result of C. Witzgall et al. [12] in linear programming, this paper gives an overview on results concerning the existence of these paths, their analyticity and the limiting behavior of their derivatives as r ↓ 0, and this also for degenerate problems in the areas of linear programming, linear complementarity problems, and semidefinte programming.
infeasible interior-point paths; linear complementarity problems; linear programs; semidefinite linear complementarity problems; semidefinite linear programs
Evaluation of Aerodynamic Drag and Torque for External Tanks in Low Earth Orbit
1499 kb
A numerical procedure is described in
which the aerodynamic drag and torque
in low Earth orbit are calculated for a
prototype Space Shuttle external tank
and its components, the “LO2” and “LH2”
tanks, carrying liquid oxygen and
hydrogen, respectively, for any given
angle of attack. Calculations assume the
hypersonic limit of free molecular flow
theory. Each shell of revolution is assumed
to be described by a series of parametric
equations for their respective contours.
It is discretized into circular cross sections
perpendicular to the axis of revolution,
which yield a series of ellipses when
projected according to the given angle
of attack. The drag profile, that is, the
projection of the entire shell is approximated
by the convex envelope of those
ellipses. The area of the drag profile, that
is, the drag area, and its center of area
moment, that is, the drag center, are then
calculated and permit determination of the
drag vector and the eccentricity vector
from the center of gravity of the shell to
the drag center. The aerodynamic torque
is obtained as the cross product of those
vectors. The tanks are assumed to be either
evacuated or pressurized with a uniform
internal gas distribution: dynamic shifting
of the tank center of mass due to residual
propellant sloshing is not considered.
aerodynamic drag;
aerodynamic eccentricity; aerodynamic
torque; free molecular flow theory; low
Earth orbit; shell of revolution; space
shuttle external tank
A Column-Generation and Branch-and-Cut Approach to the Bandwidth-Packing Problem
908 kb
The telecommunications problem of
assigning calls with point to point demand
to a capacitated network where each call
can be assigned to at most one path has
been called the Bandwidth-Packing
Problem. For a given network, with
specified arc costs and arc capacities, one
wishes to route calls (defined by a starting
and ending point) through the network to
maximize the profit from the calls routed.
Each such call is single path routed and
not all calls will be routed. We propose a
branch-and-cut methodology coupled with
column generation to optimally solve such
problems. We examine the alternative
approaches in the literature and explain
how this new method takes the best of
all components of methods suggested
previously. The method we suggest
is new in that it includes a linear
programming-based heuristic for obtaining
good lower bounds, uses lifted minimal
covers that take into account specialordered
set constraints, and dynamically
choose among three alternative branching
strategies. In addition, whenever a new
column is generated, it is lifted into all
existing cuts. We also discuss the need
to generate all tied optimal linear
optimization solutions if one wishes to
assure that the solution obtained is
optimal. Our computational results
provide solutions to problems previously
unsolvable.
capacitated networks; column
generation; combinatorial optimization;
cutting planes; facet-defining cuts;
heuristics; integer programming; network
planning; telecommunications networks;
zero-one optimization
NIST Journal of Research Home Page
|
Date Created:
May 11, 2006 |
