带有软限制的聚合 objective function/objective 的多背包问题

Question

我正在尝试解决 Google OR-tools 中多背包示例的一个变体。我似乎无法编码的一个功能是对值的软限制。

在原始示例中，项目具有用于计算约束的权重和用于计算最优解的值。在我的变体中，我有多个 weights/capacities 构成某些类型项目的配额和兼容性。此外，每个箱子都有一个资金目标，每个物品都有一个价值。我想尽量减少每个箱子的资金缺口：

# pseudocode!
minimise: sum(max(0, funding_capacity[j] - sum(item[i, j] * item_value[i] for i in num_items)) for j in num_bins)

此方法与示例之间的主要区别在于，如果 item_1 的值为 110，而 bin_A 的资金需求为 100，则 item_1 可以适合 bin_A 并使资金缺口变为零。值为 50 的 item_2 也可以适合 bin_A（只要满足其他约束条件）但优化器不会看到 objective 函数有任何改进。我曾尝试使用 objective.SetCoefficient 方法来计算资金短缺，但我不断收到错误，我认为这些错误与此方法有关，不喜欢像 sum 这样的聚合函数。

如何在 objective 函数或约束中实现上面的资金短缺 objective？如何使用汇总计算形成 objective 函数？ 理想的答案是 Python 中 OR 工具的代码片段，但在其他编程中来自 OR 工具的清晰说明性答案语言也会有所帮助。

Answer 1

下面是工作代码，但这里是您将如何继续制定。

多个背包问题的公式更改given here

每个容器需要两组新变量。我们称它们为 shortfall[j]（连续）和 filled[j]（布尔）。
Shorfall[j] 就是 funding_requirement[j] - sum_i(funding[items i])
filled[j] 是一个布尔值，如果 bin 中每个项目的资金总和大于其资金需求，我们希望它为 1，否则为 0。

我们必须求助于整数规划中的标准技巧，涉及使用大 M。（大数）

        if total_item_funding >= requirement, filled = 1
        if total_item_funding < requirement, filled = 0

这可以用线性约束来表示：

           shortfall + BigM * filled > 0

请注意，如果差额变为负数，它会强制 filled 变量变为 1。如果 shortfall 为正数，filled 可以保持为 0。（我们将使用objective 函数。）

在最大化问题的 objective 函数中，您对填充的变量进行惩罚。
```
 Obj: Max sum(i,j) Xij * value_i + sum(j) filled_j * -100
```

所以，这个多背包公式被激励接近每个垃圾箱的资金需求，但如果它超过了需求，它就会受到惩罚。

您可以使用 objective 函数变量和惩罚。

使用 Google-OR 工具的公式

工作 Python 代码。为了简单起见，我只制作了 3 个箱子。

from ortools.linear_solver import pywraplp


def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    item_funding = [50, 17, 38, 45, 65, 60, 15, 30, 10, 25, 75, 30, 40, 40, 35]
    data['weights'] = weights
    data['values'] = values
    data['i_fund'] = item_funding
    data['items'] = list(range(len(weights)))
    data['num_items'] = len(weights)
    num_bins = 3
    data['bins'] = list(range(num_bins))
    data['bin_capacities'] = [100, 100, 80,]
    data['bin_funding'] = [100, 100, 50,]

    return data

def main():
    data = create_data_model()

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

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

    BIG_M, MAX_SHORT = 1e4, 500
    for j in data['bins']:
        short[j] = solver.NumVar(-MAX_SHORT, MAX_SHORT, 
                                 'bin_shortfall_%i' % (j))
        filled[j] = solver.IntVar(0,1,  'filled[%i]' % (i))

    # Constraints
    # Each item can be in at most one bin.
    for i in data['items']:
        solver.Add(sum(x[i, j] for j in data['bins']) <= 1)

    for j in data['bins']:
        # The amount packed in each bin cannot exceed its capacity.
        solver.Add(
            sum(x[(i, j)] * data['weights'][i]
                for i in data['items']) <= data['bin_capacities'][j])
        
        #define bin shortfalls as equality constraints
        solver.Add(
            data['bin_funding'][j] - sum(x[(i, j)] * data['i_fund'][i]
                for i in data['items']) == short[j])
        
        # If shortfall is negative, filled is forced to be true
        solver.Add(
            short[j] + BIG_M * filled[j] >= 0)


    # Objective
    objective = solver.Objective()

    for i in data['items']:
        for j in data['bins']:
            objective.SetCoefficient(x[(i, j)], data['values'][i])

    for j in data['bins']:
            # objective.SetCoefficient(short[j], 1)
            objective.SetCoefficient(filled[j], -100)

    objective.SetMaximization()

    print('Number of variables =', solver.NumVariables())
    status = solver.Solve()


    if status == pywraplp.Solver.OPTIMAL:
        print('OPTMAL SOLUTION FOUND\n\n')
        total_weight = 0
        for j in data['bins']:
            bin_weight = 0
            bin_value = 0
            bin_fund = 0

            print('Bin ', j, '\n')

            print(f"Funding {data['bin_funding'][j]} Shortfall \
            {short[j].solution_value()}")

            for i in data['items']:
                if x[i, j].solution_value() > 0:
                    print('Item', i, '- weight:', data['weights'][i], ' value:',
                          data['values'][i], data['i_fund'][i])
                    bin_weight += data['weights'][i]
                    bin_value += data['values'][i]
                    bin_fund += data['i_fund'][i]

            print('Packed bin weight:', bin_weight)
            print('Packed bin value:', bin_value)
            print('Packed bin Funding:', bin_fund)
            print()
            total_weight += bin_weight
        print('Total packed weight:', total_weight)
    else:
        print('The problem does not have an optimal solution.')


if __name__ == '__main__':
    main()

希望能帮助您前进。

带有软限制的聚合 objective function/objective 的多背包问题

Multi-knapsack problem with aggregate objective function/objective with a soft limit

python

linear-programming

or-tools

多个背包问题的公式更改given here

使用 Google-OR 工具的公式