期刊
COMPUTERS & OPERATIONS RESEARCH
卷 35, 期 6, 页码 2103-2113出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2006.10.014
关键词
variable size bin packing; discretized reformulations; extended formulations
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 E 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. (c) 2006 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据