Plenary Lecture
Path-Based Modeling: A Generalized Framework for Formulating
Combinatorial Optimization Problems as Linear Programs
Professor Moustapha Diaby
School of Business Administration,
University of Connecticut,
E mail: Moustapha.Diaby@business.uconn.edu
Abstract: The subject of combinatorial
optimization spans several fields of study, and is applicable in a large number
of practical contexts. The great difficulty involved in solving combinatorial
optimization problems has to do, mostly, with their discrete nature. The general
idea of most of the theoretical developments dealing with these problems over
the past several decades has been to tackle this discreteness directly, by
enforcing it through integrality requirement constraints. As a result of this
“quest for integrality,” the optimal resolution of these problems has typically
required some enumeration of the solutions, and the goal of the theoretical
developments in general has consisted of providing tools that can be used to
craft “tailor-made” procedures that exploit, to the extent possible, the
particular characteristics of the problem at hand. In this talk we will define
the notion of “Path-Based Modeling” and discuss its use in formulating some of
the well-known NP-Complete combinatorial optimization problems as linear
programs. Unlike other approaches, the focus in this approach is on enforcing
the convexity of a complete feasible solution with respect to the objects being
modeled, rather than attempting to enforce the integrality of individual
variables. The approach will be illustrated using the Set Partitioning Problem
as an example. Some reflections on the computational complexity paradigm will
also be discussed.
About the speaker:
Moustapha Diaby is Associate Professor of Production and Operations Management
at the School of Business Administration, University of Connecticut. He received
a Ph.D. degree in Management Science/Operations Research, M.S. degree in
Industrial Engineering, and B.S. degree in Chemical Engineering from the State
University of New York at Buffalo. His teaching and research interests are in
the areas of mathematical programming, production planning and control,
manufacturing systems modeling and analysis, and supply chain and logistics
management. His publications have appeared in many of the top-tier journals in
these areas. He has served/currently serves as a reviewer and/or ad-hoc
editorial team member for many of these journals also, and for government
agencies (such as NSF for example). He has also held national-level offices
within the professional societies and chaired several national-level events and
activities.