python - 具有软限制的聚合目标函数/目标的多背包问题

Question

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

在原始示例中，项目具有用于计算约束的权重和用于计算最佳解决方案的值。在我的变体中，我有多个权重/容量，它们构成了某些类型项目的配额和兼容性。此外，每个箱子都有一个资金目标，每个元素都有一个值(value)。我想尽量减少每个箱子的资金缺口:

# 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.SetCoefficient 方法计算资金短缺，但我不断收到错误，我认为这些错误与此方法有关，不喜欢像 sum 这样的聚合函数。

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

Answer 1

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

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

1. 每个容器需要两组新变量。我们称它们为 shortfall[j](连续)和 filled[j]( bool )。

2. Shorfall[j] 就是 funding_requirement[j] - sum_i(funding[items i])

3. filled[j] 是一个 bool 值，如果 bin 中每个项目的资金总和大于其资金需求，我们希望它为 1，否则为 0。

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

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

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

           shortfall + BigM * filled > 0

请注意，如果 shortfall 变为负数，它会强制 filled 变量变为 1。如果 shortfall 为正，则 filled 可以保持为 0 .(我们将使用目标函数强制执行此操作。)

1. 在最大化问题的目标函数中，您对填充变量进行惩罚。

    Obj: Max sum(i,j) Xij * value_i + sum(j) filled_j * -100
   

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

您可以尝试使用目标函数变量和惩罚。

使用 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()

希望能帮助您前进。