如何用OR-Tools求解依赖组合的动态成本背包最小化问题？

核心错误点 #

1. 目标函数与变量完全脱节：原代码中getCost(wastes)传入的是所有物品的列表，而非选中的物品组合，且通过setOffset设置的是固定值，和二进制变量x（是否选中物品）没有任何关联。这导致优化目标是一个常量，完全起不到最小化组合成本的作用。
2. 多目标设置无效：OR-Tools的MPSolver仅支持单目标优化，后设置的weight目标会直接覆盖之前的costValue目标，实际运行时只会最大化重量，完全忽略成本需求。

解决方案思路 #

由于你的成本是依赖物品组合的非线性函数（由TensorFlow模型计算，无法拆解为单个物品的线性系数），传统线性规划（LP/MIP）无法直接处理这种目标。推荐采用以下两种方案：

方案一：使用CP-SAT求解器（推荐） #

OR-Tools的CP-SAT求解器支持自定义目标评估逻辑，可以在求解过程中对每个候选可行解调用TensorFlow模型计算成本，引导求解器寻找成本最小的解，同时能轻松处理你的容量约束。

代码示例

public List<Waste> main(List<Waste> nowStock) throws Exception {
    Loader.loadNativeLibraries();

    HashMap<Integer, Waste> iToWaste = Maps.newHashMap();
    for (int i = 0; i < nowStock.size(); i++) {
        iToWaste.put(i, nowStock.get(i));
    }
    final int numItems = nowStock.size();
    final double binMinCapacity = 70 * 0.95;
    final double binMaxCapacity = 70 * 1.05;

    // 初始化CP-SAT模型
    CpModel model = new CpModel();
    Literal[] x = new Literal[numItems];
    for (int i = 0; i < numItems; i++) {
        x[i] = model.newBoolVar("x_" + i);
    }

    // 添加容量约束：选中物品总重量在[95%*70, 105%*70]区间内
    LinearExpr totalWeight = LinearExpr.newBuilder();
    for (int i = 0; i < numItems; i++) {
        totalWeight.addTerm(x[i], iToWaste.get(i).getWeight().doubleValue());
    }
    model.addLinearConstraint(totalWeight, binMinCapacity, binMaxCapacity);

    // 自定义目标：遍历所有可行解，筛选成本最小的组合
    CpSolver solver = new CpSolver();
    solver.getParameters().setNumThreads(20);

    List<Waste> bestSolution = null;
    double minCost = Double.MAX_VALUE;

    // 注册解回调函数，评估每个可行解的成本
    solver.searchAllSolutions(model, new CpSolverSolutionCallback() {
        @Override
        public void onSolutionCallback() {
            List<Waste> selected = new ArrayList<>();
            for (int i = 0; i < numItems; i++) {
                if (value(x[i])) {
                    selected.add(iToWaste.get(i));
                }
            }
            // 调用TensorFlow模型计算当前组合的成本
            double currentCost = getCost(selected).doubleValue();
            // 更新最优解记录
            if (currentCost < minCost) {
                minCost = currentCost;
                bestSolution = new ArrayList<>(selected);
            }
        }
    });

    // 执行求解
    CpSolver.Status status = solver.solve(model);
    if (status == CpSolver.Status.FEASIBLE || status == CpSolver.Status.OPTIMAL) {
        return bestSolution;
    }
    return null;
}

方案二：线性加权多目标（仅适用于小规模场景） #

如果可以接受近似优化，可通过加权系数将「成本最小化」和「重量最大化」合并为单目标函数，例如：
总目标 = 成本权重 * 组合成本 - 重量权重 * 总重量
然后最小化该目标值。具体步骤：

• 先筛选所有满足容量约束的可行组合；
• 对每个组合调用TensorFlow计算成本；
• 根据加权公式计算总目标值，选择最优组合。

这种方法仅适合物品数量较少的场景，否则可行组合数量会爆炸式增长，导致性能问题。

关键注意事项 #

• 若必须使用MPSolver（线性规划），则成本函数必须能拆解为单个物品的线性系数，但根据你的需求，成本依赖组合，因此MPSolver不适用。
• 当物品数量较多时，CP-SAT的searchAllSolutions可能耗时过长，可通过solver.getParameters().setMaxTimeInSeconds(60)设置超时时间，或限制遍历的解数量。

内容的提问来源于stack exchange，提问作者冯佳奇