带重量上下限的装箱问题无解，求近似解法及阻碍项排查方案

问题描述 #

需将化学品袋装入尽可能少的箱子中，每个箱子总重量必须介于2.7kg至3.3kg之间。使用Google OR-Tools的SCIP后端求解该装箱问题，但运行后显示无解。需要找到近似解法，或识别阻碍求解的物品。

用户提供的代码如下：

from ortools.linear_solver import pywraplp

def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [1.0, 1.001, 1.09, 1.002, 1.006, 1.007, 1.0, .674, 1.002 , .22, .36, .24, 1.20, .4, .947, .987, .456]
    data['weights'] = weights
    data['items'] = list(range(len(weights)))
    data['bins'] = data['items']
    data['bin_capacity_upper_limit'] = 3.3
    data['bin_capacity_lower_limit'] = 2.7
    return data


# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')

data = create_data_model()

# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data['items']:
    for j in data['bins']:
        x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

# y[j] = 1 if bin j is used.
y = {}
for j in data['bins']:
    y[j] = solver.IntVar(0, 1, 'y[%i]' % j)
    
    
# Constraints
# Each item must be in exactly one bin.
for i in data['items']:
    solver.Add(sum(x[i, j] for j in data['bins']) == 1)

# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
    solver.Add(
        sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= y[j] *
        data['bin_capacity_upper_limit'])
    
    solver.Add(
        sum(x[(i, j)] * data['weights'][i] for i in data['items']) >= y[j] *
        data['bin_capacity_lower_limit'])
    

# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data['bins']]))


status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    num_bins = 0
    for j in data['bins']:
        if y[j].solution_value() == 1:
            bin_items = []
            bin_weight = 0
            for i in data['items']:
                if x[i, j].solution_value() > 0:
                    bin_items.append(i)
                    bin_weight += data['weights'][i]
            if bin_items:
                num_bins += 1
                print('Bin number', j)
                print('  Items packed:', bin_items)
                print('  Total weight:', bin_weight)
                print()
    print()
    print('Number of bins used:', num_bins)
    print('Time = ', solver.WallTime(), ' milliseconds')
else:
    print('The problem does not have an optimal solution.')

无解原因分析 #

1. 总重量与理论箱数矛盾：所有物品总重量约为13.592kg，理论最少需要ceil(13.592/3.3)=5个箱子，最多需要floor(13.592/2.7)=5个箱子，即必须用5个箱子且每个箱子刚好装2.718kg左右。但实际物品组合无法满足每个箱子都落在2.7-3.3区间内。
2. 小物品组合瓶颈：重量小于0.7kg的小物品总重量为2.35kg，这些物品无法单独凑够2.7kg的下限，必须与大物品搭配。但大物品两两或三三组合后，剩余小物品无法填补到符合要求的箱子中，导致无解。

解决方案建议 #

1. 放松约束（业务允许的情况下） #

如果可以接受个别箱子略微偏离重量上下限，修改约束中的数值后重新求解：

data['bin_capacity_upper_limit'] = 3.5
data['bin_capacity_lower_limit'] = 2.5

2. 贪心启发式近似解法 #

采用首次适应递减算法（FFD），先将物品按重量降序排序，再依次放入合适的箱子，是装箱问题常用的近似解法：

def greedy_packing(weights, lower, upper):
    # 按重量降序排序，保留原物品索引
    sorted_items = sorted(enumerate(weights), key=lambda x: -x[1])
    bins = []  # 每个元素格式：(当前总重量, [物品索引列表])

    for idx, weight in sorted_items:
        placed = False
        # 尝试放入已有箱子
        for bin in bins:
            if bin[0] + weight <= upper:
                bin[0] += weight
                bin[1].append(idx)
                placed = True
                break
        if not placed:
            # 单个物品超重则无法装箱
            if weight > upper:
                print(f"物品{idx}重量{weight}超过上限，无法装箱")
                continue
            bins.append([weight, [idx]])

    # 整理结果，标记未达下限的箱子
    final_bins = []
    for i, (weight, items) in enumerate(bins):
        final_bins.append({
            "箱子编号": i+1,
            "物品索引": items,
            "总重量": round(weight, 3),
            "是否符合约束": lower <= weight <= upper
        })
    return final_bins

# 执行贪心装箱
data = create_data_model()
result = greedy_packing(data['weights'], data['bin_capacity_lower_limit'], data['bin_capacity_upper_limit'])

# 输出结果
for bin_info in result:
    print(f"箱子{bin_info['箱子编号']}:")
    print(f"  物品索引: {bin_info['物品索引']}")
    print(f"  总重量: {bin_info['总重量']}kg")
    print(f"  是否符合约束: {'是' if bin_info['是否符合约束'] else '否'}")
    print()
print(f"总共使用箱子数: {len(result)}")

3. 优化MIP模型约束 #

给原模型添加冗余约束，帮助SCIP更快判断无解或找到可行解：

total_weight = sum(data['weights'])
min_bins = int(total_weight / data['bin_capacity_upper_limit']) + (1 if total_weight % data['bin_capacity_upper_limit'] > 0 else 0)
max_bins = int(total_weight / data['bin_capacity_lower_limit'])
solver.Add(solver.Sum(y) >= min_bins)
solver.Add(solver.Sum(y) <= max_bins)

4. 识别"麻烦"物品 #

• 重量接近上限的大物品：如1.2kg、1.09kg，这类物品与其他大物品组合容易接近上限，剩余空间无法容纳足够小物品达到下限。
• 零散小物品：总重量2.35kg的小物品无法单独成箱，且难以与已组合的大物品匹配，是导致无解的核心原因。

总结 #

原问题不存在严格满足所有箱子重量在2.7-3.3之间的解，核心瓶颈是零散小物品无法凑够下限。建议优先考虑放松约束或使用贪心启发式算法获取近似解，若必须使用精确解法，可添加冗余约束帮助求解器更快判断问题状态。

内容的提问来源于stack exchange，提问作者zoc99