Dual-Feasible Functions for Integer Programming and Combinatorial Optimization

Beschreibung

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.
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

Autor*in

Cláudio Alves

Themen in »Dual-Feasible Functions for Integer Programming and Combinatorial Optimization«

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

Stimmen zu »Dual-Feasible Functions for Integer Programming and Combinatorial Optimization«

“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)

Details

Link teilen