A smattering of some current research interests...
IDEA: Integrated Decomposition for Enterprise Analysis
The need to incorporate uncertainty within complex business environments has become increasingly clear. Many firms have invested a great deal of time and resources in developing models that can be used to assist with operational decision making. For example, airlines typically use complex models to assist with their air fleet assignments, crew scheduling, maintenance schedules, etc. In addition to these types of operational decisions, firms must undertake strategic, or long-term, decisions as well (such as when an airline determines what markets it will serve). In general, these strategic decisions impact operational decisions, although neither this impact nor the uncertainty associated with day-to-day operational decisions is typically captured within the enterprise's strategic decision model. This project involves an exploration of integrated models and solution methods for enterprise-based decision making under uncertainty.
An enterprise-based model is one that couples a variety of component problems that are associated with different entities within the enterprise. Of necessity these component problems, which typically reflect operational concerns, are finely detailed. Their individual solutions often require highly specialized computational approaches that challenge current computing resources. As a result, their direct incorporation within an enterprise-based model would likely lead to a model that greatly exceeds current computational capabilities. To remedy this situation, this project advocates the use of surrogate models of the component problems that reflect the uncertainty associated with the day-to-day operations, and are combined in a manner that permits guidance for the strategic decisions. A primary goal of this project is the development of solution methods for the resulting class of problems based on decomposition schemes that exploit the general structure of the enterprise model.
This project is funded by the National Science Foundation, Grant No. DMS 04-00085
Students involved: Anne Johnson, Lei Zhao
Manifold Identification and Estimation
Large data sets often have some type of structure hidden within them, just waiting to be uncovered. Examples of these include sequences of pictures of a particular object in various positions, trajectories of correlated sensor data, etc. Individual elements within this set of data may be of very high dimension, but functional relationships among data elements can permit representation of the data within a much smaller dimension. This smaller dimensional representation facilitates other "data mining" techniques, which can be more rapidly undertaken in smaller dimensions. For example, a set of points in Rn that define a line can be analyzed as a one-dimensional object, no matter how big n is, if we can uncover the linear relationship. Things really start to get interesting when we start to consider non-linear representations of lower dimensional surfaces in higher dimensional spaces!
In this project, we're exploring manifold estimation techniques based on Locally Linear Embedding (Roweis and Saul, Science vol. 290, 22 December 2000). Locally Linear Embedding is designed to approximate the manifold based solely on locally linear approximations of the surface. The local approximations are based on "neighboring" points. These neighbors are retained in the transformation to the lower dimensional representation. Issues such as neighboring point selection, "holes" in the data, errors in the data, etc. lead to wide variety of interesting research questions.
Student involved: Jenn Barzeele -- Jenn really deserves the credit for bringing research opportunities in this area to my attention!
Matrix Mining
Data Mining refers to a collection of techniques that can be used to discover relationships and/or patterns within large and complicated data sets. "Optimization" typically plays an important role in many data mining techniques. This project comes full circle, and considers the use of data mining techniques within the solution of difficult optimization problems.
Note that we can easily think of constraint matrices in linear and integer programming instances as "data." Are there patterns or relationships within this data that can be exploited to simplify the solution of these instances? This project investigates the use of clustering techniques to reduce the number of integer variables within an integer program. Preliminary empirical investigations suggest that in some circumstances, good solutions can be found rather quickly. The methods may be most appropriate for IPs that need to be solved repeatedly, such as one encounters in Stochastic Integer Programming. But of course, this raises plenty of questions ...
Students involved: none ... yet!