Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem
Cláudio Alves, José Valério de Carvalho, François Clautiaux, Jürgen Rietz
Submitted, 2011
ABSTRACT
In this paper, we address the 2-dimensional vector packing problem where an optimal layout for a set of items with
two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in
areas such as the telecommunications, transportation and production planning lead to this combinatorial
problem. Here, we focus on the computation of fast lower bounds using original approaches based on the concept of dual-feasible functions.
Dual-feasible functions have been used in the past to compute lower bounds and valid inequalities for different combinatorial optimization and integer programming problems. Until now, all the dual-feasible functions proposed in the literature were 1-dimensional functions. In this paper, we extend the principles of dual-feasible functions to the m-dimensional case by introducing the concept of vector packing dual-feasible function, and we propose and analyze different new families of functions. All the proposed approaches were tested extensively using benchmark and random instances of the 2-dimensional vector packing problem. Our computational results show that these functions can approximate very efficiently the best known lower bounds for this problem and improve significantly the convergence of branch-and-bound algorithms.
BIBTEX ENTRY
@article{AlvesCarvalhoClautiauxRietzVPDFF11,
author = {Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho and Fran\c{c}ois Clautiaux and J{\"u}rgen Rietz},
title = {Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem},
year = {2011},
note = {submitted} }