Dual-Feasible Functions for Integer Programming and Combinatorial Optimization

1. Front Matter

   Pages i-xi

   PDF

2. Linear and Integer Programming

   • Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz

   Pages 1-19

3. Classical Dual-Feasible Functions

   • Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz

   Pages 21-49

4. General Dual-Feasible Functions

   • Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz

   Pages 51-89

5. Applications for Cutting and Packing Problems

   • Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz

   Pages 91-123

6. Other Applications in General Integer Programming

   • Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz

   Pages 125-131

7. Back Matter

   Pages 133-159

   PDF

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.

• Dantzig-Wolfe decomposition
• combinatorial optimization
• cutting and packing problem
• integer programming
• production planning
• routing and location application
• scheduling

“In this book, DFFs are discussed within the general framework of duality. A whole machinery of theoretical results is developed. It is demonstrated that many results on integer optimization problems can actually be obtained in a unified manner from this machinery. … I expect the book to be extremely helpful for readers who are interested in integer linear optimization and techniques for proving good lower bounds.” (Hans-Ulrich Simon, Mathematical Reviews, January, 2017)

“The authors provide a textbook covering the topic of dual feasible functions (DFF), that were originally used to solve the problems involving the knapsack inequalities … . the results are illustrated with examples. There are also exercises with solutions ending each chapter. The book will be for sure interesting and useful for the graduate students in operations research, mathematics, optimization and similar areas, as well as for their lecturers. Also, more advanced undergraduate students could make use of this textbook.” (Marcin Anholcer, zbMATH 1354.90101, 2017)

• Department of Production and Systems, University of Minho, Braga, Portugal

  Claudio Alves, José Valerio de Carvalho

• Institut de Mathématiques de Bordeaux, University of Bordeaux, Talence, France

  Francois Clautiaux

• Centro Algoritmi, University of Minho, Braga, Portugal

  Jurgen Rietz

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.

Policies and ethics