These are the Department of Mathematical and Statistical Sciences Legacy Pages

ABSTRACT:

This will be our first meeting for Spring 2005. We will meet and brainstorm about optimization problems.

ABSTRACT:

Process systems engineering problems typically arise in the areas of modeling, control, and estimation. Various numerical optimization techniques are applied to these problems. The resulting mathematical programming problem is often nonconvex, either due to discrete decision variables and/or algebraic nonlinearity in the constraints or objective function. Deterministic methods for solution of nonconvex optimization problems must be considered in order to provide guarantees on the quality of the resulting solution, as well as rigorous bounds on intermediate solutions. A recent decomposition method for the deterministic solution of Mixed-Integer NonLinear Programming (MINLP) problems involving factorable, nonseparable, nonconvex constraints will be presented. Each major iteration requires global solution of a nonconvex programming problem using spatial branch-and-bound and solution of a Mixed Integer Linear Programming (MILP) problem. An alternative MINLP solution method will be presented. This method is based on formulation of a nonconvex lower bounding problem using piecewise linear outer approximations of the original convex function relaxations. Extensions of both methods to efficient parallel solution are available. Applications in the areas of model identification and online process control will be presented.

ABSTRACT:

Manufacturing has developed in to a highly competitive landscape with customers having more choices, demanding more product models and options, and offshore manufacturing driving down labor costs. As manufacturers have been looking for solutions to remain cost competitive and meet customer's changing demands, Lean manufacturing principles have become a core component of many corporate strategies. Lean manufacturing attempts to eliminate waste and increase the ability to respond to dynamic customer demand. Lean is utilized in demand management, production planning, factory floor production, material replenishment, and supply chain management. Each of these business functions has opportunities for the application of optimization theory based on Lean principles.

ABSTRACT:

Preface: (By Steve Billups) This semester's Math Clinic, which is sponsored by Raytheon, is focused on Satellite Mission Scheduling with Dynamic Tasking. During our investigation of the literature, we learned of the outstanding work of Laura Barbulescu, whose Ph.D. work is focused on oversubscribed scheduling problems. She has been invited to share her expertise in this special seminar, and will then be meeting with the students in the clinic to discuss the specifics of our problem.

Abstract:

Most research in solving real-world combinatorial optimization problems focuses on developing new algorithms and showing empirically that these algorithms perform better than previous attempts. Usually, the research fails to identify what makes an algorithm perform well or poorly.

This talk highlights results of my research on identifying key algorithm performance factors in the context of an oversubscribed real-world application, scheduling for the Air Force Satellite Control Network (AFSCN). I will focus on the factors that partially explain the performance of three algorithms: next descent local search, a genetic algorithm (GA) and Squeaky Wheel Optimization (SWO).

My results show that: 1) The search space is dominated by plateaus, favoring algorithms like the GA and SWO, which take large steps through the space, 2) The performance of local search can be significantly increased by using a randomized ordering of the neighbors instead of a structured ordering, and 3) Greedy initialization can greatly enhance the performance of the GA.

ABSTRACT:

Combinatorial optimization has evolved into its current state by the cumulative contributions and assessments of many researchers and practitioners. The legacy of these past experiences is a conventional wisdom embodied in certain tenets that guide current and future work. One such tenet that is particularly well entrenched in combinatorial optimization is the tenet of linearity, which stipulates that a linear model should be chosen in preference to a nonlinear model, provided that the relationships existing in the setting of interest can be reasonably represented in linear form.

Our work over the past few years, however, has identified several compelling exceptions to this revered tenet, exceptions that are both conceptually and computationally attractive. We discuss several such examples, and report computational experience comparing specific nonlinear models with their linear counterparts that disclose the surprising nature of our findings.

ABSTRACT:

NOTE unusual, off-schedule day

One approach to nonlinear control is through Dynamic Programming (DP). With DP, solution of the control problem reduces to solution of the corresponding Hamilton-Jacobi-Bellman (HJB) PDE. Various approaches have been taken to solution of the HJB PDE. The most common methods by far all fall into the class of finite element methods. These require that one generate a grid over some bounded region of the state-space. Unfortunately the number of grid points grows exponentially with state-space dimension, and so the computational cost grows exponentially with state-space dimension. This is referred to as the curse-of-dimensionality.

In recent years, a new class of numerical methods for first-order HJB PDEs has emerged. These methods exploit the max-plus linearity of the semigroup associated with such PDEs. They employ a max-plus basis function expansion of the solution, and the numerical methods obtain the coefficients in the basis expansion. These methods have proven to be quite fast for steady-state, H_infty-type, nonlinear control problems. However, the number of basis functions required still typically grows exponentially with space dimension. Consequently, one still has the curse-of-dimensionality.

We will discuss a new approach to certain nonlinear HJB PDEs which is not subject to the curse-of-dimensionality. In fact, the computational growth in state-space dimension is on the order of n^3. However, there is exponential computational growth in a certain measure of complexity of the Hamiltonian. Under this measure, the minimal complexity Hamiltonian is the linear/quadratic Hamiltonian -- corresponding to solution by a Riccati equation. If the Hamiltonian is given as a maximum of M linear/quadratic Hamiltonians, then one could say the complexity of the Hamiltonian is M.

ABSTRACT:

We give processor-allocation algorithms for minimizing the average number of communication hops between the processors assigned to a job on a tightly-coupled grid architecture. On systems such as the supercomputers at Sandia National Laboratories, parallel jobs are assigned a set of processors at the time they start. For security reasons, a single job has exclusive use of its processors and it cannot migrate. To obtain maximum throughput in a network-limited computing system, the processors allocated to a single job should be physically near each other. This placement reduces communication costs and avoids bandwidth contention caused by overlapping jobs.

We model allocating a single job on a partially-occupied grid computer as a special case of the following geometric clustering problem: given a set P of n points in Reals^d, find a subset S of k points with minimum average pairwise L_1 distance. We will present a natural algorithm that is a 7/4-approximation for 2D grids. For d-dimensional space, the approximation guarantee is 2-1/2d, which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d.

Finally, we report simulation results for large trace sets from supercomputers. We found that our simple approximation algorithm performs well when placing a single job, but other criteria are more appropriate when allocating a stream of jobs.

This is joint work with Michael Bender (SUNY Stony Brook), David Bunde (University of Illinois, Urbana), Erik Demaine (MIT), Sandor Fekete (Braunschweig University of Technology), Vitus Leung (Sandia National Laboratories), and Henk Meijer (Queen's University, Ontario).

ABSTRACT:

Traditional Genome annotation involves the enumeration of open reading frames and their functional assignment. Currently, there are on-going efforts to identify all the interactions between these components. The resulting map of interactions effectively represents a two-dimensional annotation. It takes the form of a stoichiometric matrix, if the interactions are described with chemical equations. The formulation and properties of this matrix are detailed and how it can be used as the basis for computing allowable phenotypic functions. The issues associated with the packing of the bacterial genome and the function of the interaction map in three-dimensions will also be discussed. Finally, we will go over the issue of genomes changing in space and time through adaptive evolution.

This is hosted by the Center for Computational Biology, but it is listed here because Dr. Palsson's research uses optimization as a principle methodolgy. Please refer colleagues to the flier at http://www-math.cudenver.edu/~hgreenbe/tmp/PalssonSeminarFlier.doc

ABSTRACT:

I shall present a series of related integer programming models for placing sensors in municipal water networks to detect contaminants that are maliciously or accidentally injected. After some background and problem definition, I describe multiple objectives and how we analyzed them. Then, I describe sources of uncertainty and a series of robust models, varying from very easy to NP-hard, that address some of the uncertainties. I introduce the use of backbone/consensus analysis, which is relatively new to IP, and which addresses an aspect of solution confidence. Finally, I introduce a new paradigm, which I call "Confidence Programming," which embodies key elements of MO, RO, and BC approaches.