Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2016 | Book

Linear and Integer Programming Read chapter Read first chapter

Dual-Feasible Functions for Integer Programming and Combinatorial Optimization

Basics, Extensions and Applications

Authors: Claudio Alves, Francois Clautiaux, José Valerio de Carvalho, Jurgen Rietz

Publisher: Springer International Publishing

Book Series : EURO Advanced Tutorials on Operational Research

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Wirtschaft" , Springer Professional "Technik"

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

Frontmatter
Chapter 1. Linear and Integer Programming
Abstract
Integer Programming (IP) is a modelling tool that has been widely applied in the last decades to obtain solutions for complex real problems, as those that arise in cutting and packing, location, routing and many other areas.
Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz
Chapter 2. Classical Dual-Feasible Functions
Abstract
Dual-feasible functions (DFF) have been used to improve the resolution of different combinatorial optimization problems with knapsack inequalities, including cutting and packing, scheduling and network routing problems. They were used mainly to compute algorithmic lower bounds, but also to generate valid inequalities for integer programs.
Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz
Chapter 3. General Dual-Feasible Functions
Abstract
Classical dual-feasible functions are defined only for nonnegative arguments thus limiting their applicability. In this chapter, we explore the extension of dual-feasible functions to more general domains with a focus on real numbers. Other attempts of generalizing the concept of dual-feasible function will be done later in the book. In Chap. 4, we will discuss for instance an extension to multidimensional domains yielding the so-called vector packing dual-feasible functions, whichmay be used to compute bounds for vector packing problems.
Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz
Chapter 4. Applications for Cutting and Packing Problems
Abstract
Dual-feasible functions have been designed specifically for the cutting-stock problem. As shown in Chap. 1, they arise naturally from the dual of the classical formulation of Gilmore and Gomory for this problem. Since many problems can be modeled using a similar formulation, it makes sense to explore the concept of dual-feasible function within a more general class of applications. A first approach is to considermulti-dimensional dual-feasible functions,which can be used to derive lower bounds for the vector packing problem. Here, we also consider different packing problems with more complicated subproblems such as multi-dimensional orthogonal packing and packing with conflicts. Dual-feasible functions can still be derived in these cases.
Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz
Chapter 5. Other Applications in General Integer Programming
Abstract
In this chapter, we briefly review an alternative application of dual-feasible functions in general integer programming. We explore these functions in particular to derive valid inequalities for integer programs. Since the notion of superadditivity is essential for this purpose, we start by reviewing superadditivity in the scope of valid inequalities. Different examples are provided with alternative families of dualfeasible functions. We discuss also the difference between the valid inequalities derived by dual-feasible functions and the well-known Chvátal-Gomory cuts.
Cláudio Alves, François Clautiaux, José Valério de Carvalho, Jürgen Rietz
Backmatter
Metadata
Title
Dual-Feasible Functions for Integer Programming and Combinatorial Optimization
Authors
Claudio Alves
Francois Clautiaux
José Valerio de Carvalho
Jurgen Rietz
Copyright Year
2016
Electronic ISBN
978-3-319-27604-5
Print ISBN
978-3-319-27602-1
DOI
https://doi.org/10.1007/978-3-319-27604-5

Premium Partner

    Image Credits