期刊
COMPUTERS & OPERATIONS RESEARCH
卷 39, 期 10, 页码 2425-2438出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2011.12.010
关键词
Constraint programming; Linear programming; Column generation
类别
资金
- Erasmus Mundus ECW [EM ECW-L04 TUD 08-134]
- German Research Foundation (DFG) [BE 4433/1-1]
We consider the 2D orthogonal feasibility problem (OPP-2) and the 2D strip packing problem (SPP-2). Given a set of rectangular items, the OPP-2 is to decide whether all items can be orthogonally packed into the given rectangular container; the SPP-2 is to find a packing of all items occupying the minimal height of the given semi-infinite strip. Both OPP-2 and SPP-2 are considered without items rotation. We investigate the known Constraint Programming (CP) approaches for OPP-2, in particular the dichotomy and disjunctive branching strategies and adapt 1D relaxation bounds based on linear programming (LP) into the constraint propagation process of the CP. Using the dichotomic search procedure the developed methods for OPP-2 are transformed for the case of SPP-2. Numerical results demonstrate the efficiency of the proposed strategies and of the combination of CP and LP-based pruning rules. (C) 2011 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据