Combinational optimization (CO) is a topic in applied mathematics, decision science and computer science that consists of finding the best solution from a non-exhaustive search. CO is related to disciplines such as computational complexity theory and algorithm theory, and has important applications in fields such as operations research/management science, artificial intelligence, machine learning, and software engineering.
Advances in Combinatorial Optimization presents a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial sized linear programs. Though developed based on the 'traveling salesman problem' (TSP), the framework allows for the formulating of many of the well-known NP-Complete COPs directly (without the need to reduce them to other COPs) as linear programs, and demonstrates the same for three other problems (e.g. the 'vertex coloring problem' (VCP)). This work also represents a proof of the equality of the complexity classes "P" (polynomial time) and "NP" (nondeterministic polynomial time), and makes a contribution to the theory and application of 'extended formulations' (EFs).
On a whole, Advances in Combinatorial Optimization offers new modeling and solution perspectives which will be useful to professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.
Errata(s)
Errata (267 KB)
Sample Chapter(s)
Chapter 1: Introduction (312 KB)
Contents:
- Introduction
- Basic IP Model Using the TSP
- Basic LP Model Using the TSP
- Generic LP Modeling for COPs
- Non-Symmetry of the Basic (TSP) Model
- Non-Applicability of Extended Formulations Theory
- Illustrations for Other NP-Complete COPs
Readership: Professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general.
Moustapha Diaby is Associate Professor of Production and Operations Management at the University of Connecticut. He received a PhD degree in Management Science/Operations Research, MS degree in Industrial Engineering, and BS degree in Chemical Engineering from University at Buffalo — The State University of New York, USA. His teaching and research interests are in the areas of Mathematical Programming, Manufacturing Systems Modeling and Analysis, Operations and Supply Chain Management, and Management of International Development Projects. His publications have appeared in European Journal of Operational Research, Information Systems Frontiers Journal, INFORMS Journal on Computing, International Journal of Mathematics in Operational Research, International Journal of Operational Research, International Journal of Production Economics, International Journal of Production Research, International Transactions in Operational Research, Journal of the Operational Research Society, Management Science, Multi-Criteria Decision Analysis, Operations Management Review, Operations Research, and WSEAS Transactions on Mathematics. He serves/has served as a Reviewer and/or ad-hoc Editorial Team Member for many of these, as well as other journals, and for government agencies such as the NSERC (National Sciences and Engineering Research Council of Canada), and the NSF (National Science Foundation, USA).
Mark H Karwan is the Praxair Professor in Operations Research at the Department of Industrial and Systems Engineering at University at Buffalo — The State University of New York, USA, where he has taught for 34 years. He has broad expertise in the area of mathematical programming — modeling and algorithmic development. His 25 PhD students have been guided in areas of algorithmic development in integer programming, multiple criteria decision making and 'mixed' areas such as integer/nonlinear or integer/multi-criteria. His 80+ publications show diverse application areas such as logistics, production planning under real time pricing, capacitated lot-sizing, hazardous waste routing and security, and military path planning. Techniques to solve these problems come from the fields of linear, nonlinear and integer programming. Funding has come from NSF, ONR and industry. Prof. Karwan's industry consulting experience has largely been in the industrial gas industry and concerned with all areas of production planning, routing, forecasting and energy use planning and in supporting corporate contracts in military operations research focused on logistics and dynamic resource allocation. He has won multiple teaching awards including the (SUNY) Chancellor's Award for Excellence in Teaching. His research interests include Discrete Optimization, Multiple Criteria Decision Making, Multilevel Systems, Vehicle Routing and Scheduling, Visual Search, and Industrial Inspection.
