Department of Systems Engineering & Engineering Management

Except for a few ideal situations, an optimal control usually pursues two often conflicting objectives: To drive the system toward a desired state, and to perform active learning to reduce the systems uncertainty. The dual roles of an optimal control, optimization and estimation, in general situations, cannot be separated. This coupling between optimization and estimation makes an analytical form of optimal control, in most situations, unattainable. The research goal is to develop some embedding schemes in order to achieve optimal control laws with an active learning property for certain classes of dual control problems.

Due to their wide applicability and versatile modelling power, stochastic programming problems have received a lot of attention in many communities. In particular, there has been substantial recent interest in developing efficient sampling-based algorithms for two-stage and multistage stochastic programming problems. The goal of this project is twofold. First, we are interested in developing efficient sampling-based algorithms for multistage risk-averse stochastic combinatorial optimization problems. Second, we will explore other sampling procedures besides the usual Sample Average Approximation method and to establish their rates of convergence.

The research goal is to develop sufficient conditions to identify hidden convex minimization problems. A nonconvex minimization problem is called a hidden convex minimization problem if there exists an equivalent transformation such that the transformed minimization problem is convex. Sufficient conditions that are independent of transformations can be derived for identifying such class of seemingly nonconvex minimization problems that are equivalent to convex minimization problems. A global optimality can be thus achieved for this class of hidden convex optimization problems by using local search methods.

Mathematical optimization plays a major role in engineering, among many other fields of application. The main challenge in optimization is to solve large-size models in real time. That calls for thorough research to enhance the optimization methods that we use. One breakthrough in this respect is the creation of the interior point method. This is an active field with exciting new results.

Internet traffic analysis, emphasizing dependence, heavy-tail distributions, and rare events. Dynamic resource management (e.g., scheduling, caching, load balancing, flow control), to achieve optimal resource utilization and quality of service.

Existing research in the capacitated lot sizing problem (CLSP) often assumes setup time to be negligible. Although there have been efforts to reduce setup times, it is not possible to reduce them to near zero in many industries. Hence, excluding setup times from CLSP models is not practical, especially when setup times are significant and production capacity is tightly constrained. In this research, this limitation will be addressed. General models considering alternate production options will be developed. In particular the inclusion of setup times will be investigated. Further the structure of the problem will be studied and solution algorithms based on the underlying structure will be developed. An extensive computational study will be carried out.

Modeling, analysis, and algorithms for a class of new scheduling problems where a big job must occupy a full machine, while a small job may share a machine with some other jobs at the same time. Applications to berth allocation in container terminals are also investigated.

The research goal is to develop equivalent transformations for generating a saddle point for nonconvex optimization problems. A saddle point condition is a sufficient condition for optimality. A saddle point can be generated in an equivalent representation space for nonconvex optimization problems that do not have a saddle point in their original settings. Certain equivalent transformations may convexify the perturbation function and a zero duality gap can be thus achieved. This investigation would lead to some efficient dual search algorithms that ensure the global optimality for a class of nonconvex optimization problems.

The research goal is to establish convergent duality theory and to develop efficient solution algorithms for large-scale nonlinear integer programming problems. The fundamental target underlying our theoretical development is to eliminate duality gap in the classical Lagrangian dual formulation. We have developed nonlinear Lagrangian theory that has yielded several new dual formulations with asymptotic zero duality gap. The key concept is the construction of a nonlinear support for a nonconvex piecewise-constant perturbation function. Our numerical implementation of a duality-gap reduction process relies on some novel cutting procedures. Performing objective-level cut, objective contour cut or domain cut reshapes the perturbation function, thus exposing eventually an optimal solution to the convex hull of a revised perturbation function and guaranteeing a zero duality gap for a convergent Lagrangian method. Applications include nonlinear knapsack problems, constrained redundancy optimization in reliability networks, and optimal control problems with integer constraints.

Suppose a manufacturer has received a number of orders (jobs) from his customers, which should be completed by their respective due dates. Most of the facilities needed to process the jobs are available in the manufacturer's own factory. However, for some reasons, certain parts of the jobs must be outsourced to a third party who possesses the machines needed to process these parts. The availability of the third-party machines is negotiable, depending on the price. Consequently, the manufacturer has to (1) negotiate an agreement to secure the machine times on the third-party machines, and (2) generate a schedule to process the jobs, so as to minimize the total cost, including the cost for the use of the third-party machines and the cost incurred if the due dates of the jobs cannot be met. In general, consideration of third-party machines in machine scheduling problems relaxes a common assumption made in traditional scheduling studies. The main objective of this project is to explore models and algorithms to solve this new branch of scheduling problems. Nash Bargaining theory will be applied.

X. Cai and Xian Zhou

We study a new class of scheduling problems involving perishable jobs with post-completion deterioration, where each finished product will be picked up by a transporter that arrives with uncertainty. The processing time to complete a job, as well as its fresh time, are random variables. If a job is finished too early, it may decay and thus incur a decaying cost; on the other hand, if it misses the pickup, it will suffer a loss due to such causes as having to be put ot a local market at a discounted price. The problem is to determine an optimal ploicy to process and handle all the jobs, so as to minimize the total expected loss. The objective of this project is to develop an in-depth study of scheduling problems with features as described above. Topics to be addressed include those on modelling, propositions of optimal policies, and algorithms.

Realistically large stochastic integer programs are in practice impossible to solve. This project, financed by the Research Council of Norway, and carried out in cooperation with the team of professor Teodor G. Crainic in Montreal,tries a new path for solving some such problems. We try to understand how the optimal solutions to stochastic programs differ from those of their deterministic counterparts, and use this knowledge to develop deterministic models that produce good solutions to their stochastic counterparts. This way we do not have to solve (neither exactly nor approximately) and stochastic programs. The approach is closely related to option theory.

Recently, semidefinite programming (SDP) has proven to be a very powerful tool in the study of the Graph Realization Problem, whose applications include sensor network localization, molecular conformation, and dimensionality reduction in manifold learning. In this project, we will continue to explore the connection between optimization theory and the geometry behind the Graph Realization Problem. We will also evaluate the quality of the proposed algorithms in empirical settings.

Just-In-Time (JIT) manufacturing is proposed to eliminate wastes of material, labor, and space in their manufacturing systems. U-shaped production lines instead of traditional straight production lines are adopted. In this research, we investigate the problem of designing U-shaped lines. Unlike designing traditional straight lines, very little research has been done on the U-line problem. The purpose of this research is to develop new knowledge for designing and operating U-lines. In particular, we explore and evaluate the use of various algorithms.