Próbuję wykonać optymalizację plecaka 0-1 z ograniczeniem źródła przedmiotów. Wziąłem przykład z witryny Ortools (Przykład Ortool) i spróbuj dodać ograniczenie Aby móc wybrać jeden przedmiot od każdego właściciela w plecaku.

Mam listę przedmiotów z powiązanymi wagami (dane ["Wagi"]), wartości (dane ["wartości"]) i źródło (dane ["posiada"]). Chciałbym znaleźć najlepszą kombinację przedmiotów do umieszczenia w plecaku, wiedząc, że tylko jeden przedmiot na źródło może wejść do plecaku.

Nie jestem pewien, jak pisać ograniczenie.

Jeśli spojrzysz na kod poniżej i mieć 1 plecak, to optymalne rozwiązanie powinno być w większości 1 elementu od właściciela 0, jeden z właściciela 1 i jeden z właściciela 2, który podąża za ograniczeniem wagi i wyjątkowości wybranej pozycji (waga poniżej 100).

Oto kod, którego używam (pobrane z Przykładu z wielokrotnego plecaku 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
Kodsama 12 marzec 2021, 14:39

1 odpowiedź

Najlepsza odpowiedź

Przede wszystkim chciałbym podziękować @sascha, który zapewnił odpowiedź!

Dołączyłem poniżej kodu (używam 2 pojemników, 3 różnych właścicieli):

#!/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()
0
Kodsama 13 marzec 2021, 16:00