Exact Algorithms for a Loading Problem with Bounded Clique Width
Exact Algorithms for a Loading Problem with Bounded Clique Width
复制标题
有限团宽度加载问题的精确算法
DOI：
--
复制
发表时间：
2006
影响因子：
2.1
通讯作者：
F. Spieksma
中科院分区：
文献类型：
--
作者：
Linda S. Moonen;F. Spieksma
在本文中，我们讨论了一个特殊的装载问题，我们遇到了一个制造公司。在图论术语中，这个问题等价于将置换图划分为有界大小的集团。我们将该问题描述为一个整数规划问题，并给出了两个求解该问题的精确算法：第一个算法是基于整数规划的分枝价格算法，第二个算法是基于有界团宽概念的算法.后一种算法的动机是现实世界中存在的结构。测试结果，无论是现实世界的实例和随机生成的实例。据我们所知，这是第一个实现的算法的基础上有界团宽度。
In this paper we discuss a special pallet-loading problem, which we encountered at a manufacturing company. In graph-theoretical terms, the problem is equivalent to partitioning a permutation graph into bounded-size cliques. We formulate the problem as an integer program, and present two exact algorithms for solving it. The first algorithm is a branch-and-price algorithm based on the integer-programming formulation; the second one is an algorithm based on the concept of bounded clique width. The latter algorithm was motivated by the structure present in the real-world instances. Test results are given, both for real-world instances and randomly generated instances. As far as we are aware, this is the first implementation of an algorithm based on bounded clique width.