|
Leslie E. Trotter, Jr. School of Operations Research and Industrial Engineering |
|
|
|
Leslie E. Trotter, Jr.: Research Interests
How does one determine a solution or, alternatively, demonstrate inconsistency for a family of simultaneous linear equations? This classical question assumes modern relevance through variations in which special additional stipulations are placed on solutions. When nonnegative solutions are sought, this is the realm of linear programming, perhaps the most widely used and successful tool of operations research; integer-valued (no fractional values) solutions are the subject of geometric lattices. The combined requirement of nonnegativity and integrality forms the topic of integer programming, the area of our research effort. Our research deals specifically with discrete optimization models. Many real-world applications fall into this class: optimization problems dealing with resource allocation, production and distribution of commodities, routing and sequencing in networks representing processes of computation, communication, and production. Discrete-valued variables can be used in modeling to reflect whether or not a particular decision is taken, so design models also often fall into this class: optimal location of product distribution centers or emergency public service centers, optimal layout of networks, optimal component construction when alternative materials can be used. Our basic research attempts to gain a deeper understanding of these models through study of their fundamental algebraic and algorithmic properties. We have developed and tested several new efficient algorithms for determining (or proving nonexistence of) lattice solutions, algorithmic tools with application in control theory, for example. A major thrust of our research effort has been investigation of the inherent relation between an integer programming model and its linear programming counterpart. This approach has led to new approximation results for industrial stock-cutting and bin-packing models. It also serves as the foundation for our present effort to implement in fully parallel computational environment three discrete optimization models prototypical of the broad class of discrete optimization models: models dealing with routing, airline crew scheduling, and multi-commodity network flows. Current Research Projects Other participants: R. G. Bland, D. Shmoys, E. Tardos, and M. J. Todd, faculty members (operations research and industrial engineering), and T. F. Coleman, Y. Li and S. Vavasis, faculty members (computer science)
|
Research