Dual-Feasible Functions for Integer Programming and Combinatorial Optimization

This book provides a postgraduate audience the keys they need to understand and further develop a set of tools for the efficient computation of lower bounds and valid inequalities in integer programs and combinatorial optimization problems. After discussing the classical approaches described in the literature, the book addresses how to extend these tools to other non-standard formulations that may be applied to a broad set of applications. Examples are provided to illustrate the underlying concepts and to pave the way for future contributions.

Explains the concept of dual-feasible functions within the general framework of duality, Dantzig-Wolfe decomposition and column generation Details relevant extensions and applications of dual-feasible functions to different combinatorial optimization problems Provides a comprehensive set of illustrative examples to clarify the essential concepts, properties, and the main ideas behind recent extensions

Autorentext

Cláudio Alves is Associate Professor of Operations Research at the Department of Production and Systems, School of Engineering, University of Minho, Portugal. He received his M.Sc., Ph.D. and Habilitation degrees in Industrial and Systems Engineering from the University of Minho. He has published more than 60 papers that appeared in international volumes and journals such as European Journal of Operational Research, Computers and Operations Research, INFORMS Journal on Computing, Operations Research Letters and Annals of Operations Research.His main scientific interests include the development and analysis of integer programming models and solution methods with an emphasis on decomposition-based approaches, combinatorial optimization, heuristics, metaheuristics and matheuristics, integrated optimization problems, applications of mixed integer programming to production and supply chain management, and the development of optimization software and decision support systems. François Clautiaux is Professor of Operations Research at the Mathematic Department of the University of Bordeaux, France. He received both his M.Sc. and Ph.D. degrees from the University of Technology of Compiègne, France. He has published in international journals including European Journal of Operational Research, Discrete Applied Mathematics, Discrete Optimization, INFORMS Journal on Computing, Computers and Operations Research, and Annals of Operations Research.His research interests are focused on methods based on integer programming, and their applications to several fields including cutting and packing, employee scheduling, vehicle routing, and clustering. José Valério de Carvalho graduated in engineering at the Faculdade de Engenharia da Universidade do Porto, and received his M.Sc. degree in Industrial Engineering and Operations Research from the Virginia Polytechnic Institute and State University, and his Ph.D. degree in Engineering Production and Operations Research from the University of Minho. He is currently Professor of Operations Research at the Department of Production and Systems, School of Engineering, University of Minho, Portugal, and head of the department.His main research areas of interest are pseudo-polynomial models, column generation and heuristics, and their application in large scale integer programming in the areas of cutting and packing, scheduling, and routing. Other topics of interest are stabilization and acceleration of column generation. He has published in Operations Research, European Journal of Operational Research, Computers and Operations Research, Annals of Operations Research, Computational Optimization and Applications, Optimization Letters, INFORMS Journal on Computing, Journal of the Operational Research Society, Networks and other journals.He has been invited speaker and member of the scientific committee of several international conferences and President of APDIO (the Portuguese Operations Research Association). Jürgen Rietz studied mathematics and earned his diploma degree from the Technische Universität Dresden, and received the doctor degree (Ph.D.) from the Technische Universität Bergakademie Freiberg (Technical University for Mining and Technology). He investigated dual-feasible functions (DFF) at the Universidade do Minho, Portugal. He is co-author of several scientific contributions in journals like Discrete Applied Mathematics, Optimization, Operations Research Letters, INFORMS Journal on Computing, Optimization Letters, European Journal of Operational Research and in proceedings of international conferences. His research topics comprise the one-dimensional cutting stock problem, two- and three-dimensional container loading, non-linear optimization and DFF.

Inhalt
Linear and Integer Programming.- Classical Dual-feasible Functions.- General Dual-feasible Functions.- Applications for Cutting and Packing Problems.- Other Applications in General Integer Programming.