Блог

Главная - Вопросы по программированию - ИЛИ-Инструменты: 0-1 рюкзак с ограничением на источник товара

ИЛИ-Инструменты: 0-1 рюкзак с ограничением на источник товара

#python #optimization #constraints #knapsack-problem #or-tools

Вопрос:

Я пытаюсь выполнить оптимизацию рюкзака 0-1 с ограничением на источник предметов. Я взял пример с веб-сайта ortools (пример ortool) и попытался добавить ограничение, чтобы иметь возможность выбирать только один предмет у каждого владельца в рюкзаке.

У меня есть список элементов со связанными весами (данные [«веса»]), значениями (данные[«значения»]) и источником (данные[«владеет»]). Я хотел бы найти лучшую комбинацию предметов, которые можно положить в рюкзак, зная, что в рюкзак может поместиться только один предмет из каждого источника.

Я не уверен, как написать ограничение.

Если вы посмотрите на приведенный ниже код и у вас есть 1 рюкзак, то оптимальным решением должно быть не более 1 предмета от владельца 0, одного от владельца 1 и одного от владельца 2, что соответствует ограничению веса и уникальности выбранного предмета (вес ниже 100).

Вот код, который я использую (взят из примера с несколькими рюкзаками ortool):

 from ortools.linear_solver import pywraplp


def create_data_model():
    """Create the data for the example."""
    data = {}
    data['weights'] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data['values'] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    data['owns'] = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
    data['owners'] = list(range(3))
    data['items'] = list(range(len(data['weights'])))
    data['num_items'] = len(data['weights'])
    data['bins'] = []
    data['bin_capacity'] = 100
    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 = {}
    for i in data['items']:
        for j in data['bins']:
            x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

    # y[i, j] = 1 if item i from owner j in bin.
    y = {}
    for i in data['owns']:
        for j in data['owners']:
            y[(i, j)] = solver.IntVar(0, 1, 'y_%i_%i' % (i, j))

    # 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)
    # Each item can be at from one owner.
    # for i in data['items']:
    #     solver.Add(sum(y[i, j] for j in data['owners']) <= 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']) <= data['bin_capacity'])

    # Objective
    objective = solver.Objective()

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

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('Total packed value:', objective.Value())
        total_weight = 0
        for j in data['bins']:
            bin_weight = 0
            bin_value = 0
            print('Bin ', j, 'n')
            for i in data['items']:
                if x[i, j].solution_value() > 0:
                    print('Item', i, '- weight:', data['weights'][i], ' value:',
                          data['values'][i])
                    bin_weight  = data['weights'][i]
                    bin_value  = data['values'][i]
            print('Packed bin weight:', bin_weight)
            print('Packed bin value:', bin_value)
            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()

Комментарии:

1. вместо этого вам следует использовать решатель CP-SAT, так как у вас есть только целое число

2. У меня есть ценности, которые могут быть плавающими. Я просто упростил это для примера. Более того, как бы я тогда интегрировал ограничение владельца?

3. В чем проблема? Есть ли в вашем коде что-нибудь, кроме копирования и вставки какого-нибудь примера? Ограничение владельца просто означает: get unique values in data['owns'] with their indices (potential 1 to n mapping) , for each unique value, indices: add a constraint: sum(indices) <= 1 (предполагается, что индексы ссылаются на двоичные переменные, решающие назначение рюкзака)

4. indices это набор. не скаляр. В вашем простом примере первое ограничение (из 3) будет выглядеть следующим образом: sum([x[0, :].sum(), x[1, :].sum(), x[2, :].sum(), x[3, :].sum(), x[4, :].sum()]) <= 1 . Это : там, чтобы суммировать по всем ячейкам. Теперь, как решатель сможет выбрать из владельца 1, которому принадлежат элементы 0, 1, 2, 3, 4 более одного раза? (Нет необходимости в переменной y!)

5. Если я основываюсь только на элементе indice, как я могу узнать, находится ли он в той же группе, что и другие? Например, я могу выбрать элемент 0 (w:48), отметить его как выбранный, чтобы он не был выбран снова, но я не вижу, как обеспечить, чтобы при его выборе другие элементы с владельцем 1 также не были выбраны. Я согласен, что это более или менее пример кода, мне пока не удалось добавить в него ограничение владельца. Я попытался использовать переменную y и прокомментировал объявление ограничений, но это не сработало.

Ответ №1:

Прежде всего, я хотел бы поблагодарить @sascha, который дал ответ!

Я прикрепляю ниже код (я использую 2 ящика, 3 разных владельца):

 #!/usr/bin/env python3
# -*- coding: utf-8 -*-
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]
    owns = [0, 1, 2, 0, 1, 2, 2, 1, 0, 1, 2, 0, 0, 1, 2]
    # owns = [0 for _ in range(len(weights))]
    data['weights'] = weights
    data['values'] = values
    data['owners'] = [0, 1, 2]
    data['owns'] = owns
    data['items'] = list(range(len(weights)))
    data['num_items'] = len(weights)
    data['bins'] = list(range(2))
    data['bin_capacities'] = [150, 100]
    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 = {}
    for i in data['items']:
        for j in data['bins']:
            x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

    # 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)

    # Each item can be at from one owner.
    for o in data['owners']:
        for j in data['bins']:
            owner = []
            for i in data['items']:
                if data['owns'][i] == o:
                    owner.append(x[i, j])
            solver.Add(sum(owner) <= 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']) <= data['bin_capacities'][j])

    # Objective
    objective = solver.Objective()

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

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('Total packed value:', objective.Value())
        total_weight = 0
        for j in data['bins']:
            bin_weight = 0
            bin_value = 0
            print('Bin ', j, 'n')
            for i in data['items']:
                if x[i, j].solution_value() > 0:
                    print('Item', i, '- weight:', data['weights'][i],
                          ' value:', data['values'][i],
                          ' owner:', data['owns'][i])
                    bin_weight  = data['weights'][i]
                    bin_value  = data['values'][i]
            print('Packed bin weight:', bin_weight)
            print('Packed bin value:', bin_value)
            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()
Метки: