Solving large-scale optimization problems

	Siriphong (Toi) Lawphongpanich http://www.ise.ufl.edu/toi/

Dr. Siriphong (Toi) Lawphongpanich´s research focuses on techniques for solving large-scale optimization problems. To make them amenable for the intended computers, or to take advantage of any underlying structure, the problems are decomposed into smaller problems to be solved sequentially or in parallel. In some applications, it is natural to refer to one of the smaller problems as the master problem and the remaining as subproblems. Much of the literature assumes that both the master and subproblems are solved optimally or nearly so. However, Dr. Lawphongpanich has shown that several familiar decomposition techniques still converge to optimal solutions of the monolithic problems when the subproblems are solved crudely. For example, when solving subproblems by an iterative process, the process can be truncated long before it approaches an optimal solution, after a small, predetermined number of iterations. His experiments show that the truncation concept is efficient, requiring less time and fewer iterations. When solved in parallel, the predetermined number of iterations can be the same for all subproblems to better synchronize the decomposition process in a parallel computing environment. Dr. Lawphongpanich is extending the truncation concept to the master problem, particularly during the early stages of the decomposition, as well as to other types of decomposition and related techniques.

Many transportation and telecommunication problems are large-scale optimization problems. Dr. Lawphongpanich is interested in predicting traffic flows on transportation and telecommunication networks and determining tolls to encourage more efficient use of the network resource and minimize system congestion. Depending on assumptions and parameters, predicting traffic flows is an optimization, variational inequality, or optimal control problem. For toll pricing, his goal is to develop models for setting tolls for High Occupancy Vehicle (HOV) and High Occupancy Toll (HOT) lanes, and for cordoning off restricted areas such as historical sites and business districts. Toll pricing models in our study can be formulated as inverse optimization (or variational inequality) problems or mathematical programs with equilibrium constraints, a relatively new class of optimization problems that is difficult to solve even for small models. For both areas of interest, he developed efficient heuristic algorithms to solve problems that are NP-Hard, and we proposed efficient decomposition techniques to handle large problems.