Arc-flow formulation and branch-and-price-and-cut algorithm for the bin-packing problem with fragile objects

被引：0

作者：

Wang, Sunkanghong ^{[1
]}

Yao, Shaowen ^{[1
]}

Zhang, Hao ^{[1
]}

Liu, Qiang ^{[1
]}

Wei, Lijun ^{[1
]}

机构：

[1] Guangdong Univ Technol, Guangdong Prov Key Lab Comp Integrated Mfg Syst, State Key Lab Precis Elect Mfg Technol & Equipment, Guangzhou 510006, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2025年 / 173卷

关键词：

Packing; Fragile objects; Exact algorithm; Branch-and-price-and-cut; Arc-flow; ALLOCATION;

D O I：

10.1016/j.cor.2024.106878

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This study introduces an arc-flow formulation and the first branch-and-price-and-cut (BPC) algorithm designed to solve the bin-packing problem with fragile objects (BPPFO). This variant of the bin-packing problem originates in the field of telecommunications, particularly in the allocation of cellular calls to frequency channels. The arc-flow formulation is inspired by previous studies and modifies the graph construction method to accommodate fragility constraints. We proved the correctness of this formulation and demonstrated its superiority in instances with small maximum fragility through extensive experiments. The proposed BPC algorithm leverages advanced cutting and packing techniques and incorporates innovative elements such as problem reduction, additional cutting planes, and a label-setting-based exact pricing algorithm. The experimental results demonstrate that the proposed BPC algorithm is highly competitive with the state-of-the-art algorithm for solving the BPPFO and can successfully solve several previously unsolved instances.

引用

页数：14