Solving the variable size bin packing problem with discretized formulations

Isabel Correia, Luís Gouveia, Francisco Saldanha-da-Gama

Research output: Contribution to journalArticle

45 Citations (Scopus)

Abstract

In this paper we study the use of a discretized formulation for solving the variable size bin packing problem (VSBPP). The VSBPP is a generalization of the bin packing problem where bins of different capacities (and different costs) are available for packing a set of items. The objective is to pack all the items minimizing the total cost associated with the bins. We start by presenting a straightforward integer programming formulation to the problem and later on, propose a less straightforward formulation obtained by using a so-called discretized model reformulation technique proposed for other problems (see [Gouveia L. A 2n constraint formulation for the capacitated minimal spanning tree problem. Operations Research 1995; 43:130-141; Gouveia L, Saldanha-da-Gama F. On the capacitated concentrator location problem: a reformulation by discretization. Computers and Operations Research 2006; 33:1242-1258]). New valid inequalities suggested by the variables of the discretized model are also proposed to strengthen the original linear relaxation bounds. Computational results (see Section 4) with up to 1000 items show that these valid inequalities not only enhance the linear programming relaxation bound but may also be extremely helpful when using a commercial package for solving optimally VSBPP.

Original languageEnglish
Pages (from-to)2103-2113
Number of pages11
JournalComputers and Operations Research
Volume35
Issue number6
DOIs
Publication statusPublished - 1 Jun 2008

Keywords

  • Discretized reformulations
  • Extended formulations
  • Variable size bin packing

Fingerprint Dive into the research topics of 'Solving the variable size bin packing problem with discretized formulations'. Together they form a unique fingerprint.

Cite this