|
# Derived from multiple_knapsack_sat.py |
|
# |
|
# Copyright 2010-2018 Google LLC |
|
# Licensed under the Apache License, Version 2.0 (the "License"); |
|
# you may not use this file except in compliance with the License. |
|
# You may obtain a copy of the License at |
|
# |
|
# http://www.apache.org/licenses/LICENSE-2.0 |
|
# |
|
# Unless required by applicable law or agreed to in writing, software |
|
# distributed under the License is distributed on an "AS IS" BASIS, |
|
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
# See the License for the specific language governing permissions and |
|
# limitations under the License. |
|
# [START program] |
|
"""Solves a multiple knapsack problem using the CP-SAT solver.""" |
|
|
|
# [START import] |
|
from ortools.sat.python import cp_model |
|
# [END import] |
|
|
|
|
|
# [START data_model] |
|
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] |
|
lengths = [12, 15, 16, 12, 12, 2, 4, 14, 4, 15, 2, 11, 2, 12, 2] |
|
data['num_items'] = len(weights) |
|
data['all_items'] = range(data['num_items']) |
|
data['weights'] = weights |
|
data['values'] = values |
|
data['lengths'] = lengths |
|
data['bin_capacities'] = [120, 100, 100, 100, 150] |
|
# data['bin_axle_loads'] = [100, 100, 100, 100, 100] |
|
data['num_bins'] = len(data['bin_capacities']) |
|
data['all_bins'] = range(data['num_bins']) |
|
data['length_wagon'] = 20 |
|
data['max_pseudoaxle_load'] = 100 |
|
return data |
|
|
|
# [END data_model] |
|
|
|
|
|
# [START solution_printer] |
|
def print_solutions(data, solver, x, positions): |
|
"""Display the solution.""" |
|
total_weight = 0 |
|
total_value = 0 |
|
for b in data['all_bins']: |
|
print('Bin', b, '\n') |
|
bin_weight = 0 |
|
bin_value = 0 |
|
item_lengths = 0 |
|
last_position_ends = 0 |
|
loaded_items = [] |
|
for idx, val in enumerate(data['weights']): |
|
if solver.Value(x[(idx, b)]) > 0: |
|
loaded_items.append({"position": solver.Value(positions[idx]), |
|
"item": idx, |
|
"weight": val, |
|
"value": data['values'][idx], |
|
"length": data['lengths'][idx]}) |
|
item_lengths += data['lengths'][idx] |
|
bin_weight += val |
|
bin_value += data['values'][idx] |
|
loaded_items.sort(key=lambda k: k['position']) |
|
for item in loaded_items: |
|
print(item) |
|
print(f"\nSum of item lengths {item_lengths}") |
|
print('Packed bin weight:', bin_weight) |
|
print('Packed bin value:', bin_value, '\n') |
|
total_weight += bin_weight |
|
total_value += bin_value |
|
print('Total packed weight:', total_weight) |
|
print('Total packed value:', total_value) |
|
|
|
# [END solution_printer] |
|
|
|
|
|
def compute_item_load(weight, dist, axledist=2): |
|
constant = int(weight / axledist) |
|
load = constant + constant * dist |
|
return load |
|
|
|
|
|
def main(): |
|
# [START data] |
|
data = create_data_model() |
|
# [END data] |
|
|
|
# [START model] |
|
model = cp_model.CpModel() |
|
# [END model] |
|
|
|
# Main variables. |
|
# [START variables] |
|
x = {} |
|
for idx in data['all_items']: |
|
for b in data['all_bins']: |
|
x[(idx, b)] = model.NewIntVar(0, 1, f'x_{idx}_{b}') |
|
max_value = sum(data['values']) |
|
# value[b] is the value of bin b when packed. |
|
value = [ |
|
model.NewIntVar(0, max_value, f'value_{b}') for b in data['all_bins'] |
|
] |
|
for b in data['all_bins']: |
|
model.Add(value[b] == sum( |
|
x[(i, b)] * data['values'][i] for i in data['all_items'])) |
|
# [END variables] |
|
|
|
# item_loaded = [model.NewBoolVar(f"item_{idx} is loaded") |
|
# for idx in data['all_items']] |
|
|
|
max_wagon_length = data['length_wagon'] |
|
positions = [model.NewIntVar(0, max_wagon_length - data['lengths'][idx], f'position of item {idx}') |
|
for idx in data['all_items']] |
|
|
|
max_load = max(data['weights']) * data['length_wagon'] |
|
item_loads = [model.NewIntVar(0, max_load, f"load for item {idx}") |
|
for idx, p in enumerate(positions)] |
|
|
|
# [START constraints] |
|
# Each item can be in at most one bin. |
|
is_loaded = [] |
|
for idx in data['all_items']: |
|
item_is_loaded = model.NewIntVar(0, 1, f"item {idx} is loaded somewhere") |
|
model.Add(item_is_loaded == sum(x[idx, b] for b in data['all_bins'])) |
|
is_loaded.append(item_is_loaded) |
|
model.Add(item_loads[idx] == compute_item_load(data["weights"][idx], positions[idx])).OnlyEnforceIf(item_is_loaded) |
|
model.Add(item_loads[idx] == 0).OnlyEnforceIf(item_is_loaded.Not()) |
|
|
|
# The amount packed in each bin cannot exceed its capacity. |
|
for b in data['all_bins']: |
|
# for bin capacities |
|
model.Add( |
|
sum(x[(i, b)] * data['weights'][i] |
|
for i in data['all_items']) <= data['bin_capacities'][b]) |
|
# limit each bin's pseudo axle loads |
|
loaded_weights = [] |
|
for i in data['all_items']: |
|
loaded_weight = model.NewIntVar(0, 10000, f"item {i} weight in bin {b}") |
|
model.Add(loaded_weight == item_loads[i]).OnlyEnforceIf(x[(i, b)]) |
|
model.Add(loaded_weight == 0).OnlyEnforceIf(x[(i, b)].Not()) |
|
loaded_weights.append(loaded_weight) |
|
model.Add(sum(loaded_weights) <= data['max_pseudoaxle_load']) |
|
|
|
literals = {} |
|
|
|
for bin_number, bin in enumerate(data['all_bins']): |
|
arcs = [] # accumulate the graph edges |
|
for item_number, item in enumerate(data['all_items']): |
|
# might be first, might not. |
|
start_lit = model.NewBoolVar(f"item {item} is first in bin {bin}") |
|
# item_node = bin_number * num_items + item_number + 1 |
|
item_node = item_number + 1 |
|
arcs.append([0, item_node, start_lit]) |
|
end_lit = model.NewBoolVar(f"item {item} is last in bin {bin}") |
|
arcs.append([item_node, 0, end_lit]) |
|
|
|
# self loop in case this item is not loaded |
|
skip_lit = model.NewBoolVar(f"item {item} is skipped for bin {bin}") |
|
arcs.append([item_node, item_node, skip_lit]) |
|
|
|
literals[(item_number, bin_number)] = {} |
|
literals[(item_number, bin_number)]['start'] = start_lit |
|
literals[(item_number, bin_number)]['end'] = end_lit |
|
literals[(item_number, bin_number)]['skip'] = skip_lit |
|
|
|
model.Add(skip_lit == 1).OnlyEnforceIf(x[(item_number, bin_number)].Not()) |
|
model.Add(skip_lit == 0).OnlyEnforceIf(x[(item_number, bin_number)]) |
|
|
|
model.Add(positions[item_number] == 0).OnlyEnforceIf(start_lit) |
|
|
|
for next_item_number, next_item in enumerate(data['all_items']): |
|
if next_item_number == item_number: |
|
continue |
|
# next_item_node = bin_number * num_items + next_item_number + 1 |
|
next_item_node = next_item_number + 1 |
|
|
|
i_j_lit = model.NewBoolVar(f"item {next_item} follows item {item} in bin {bin}") |
|
|
|
literals[(item_number, bin_number)][f"next_{next_item_number}"] = i_j_lit |
|
|
|
arcs.append([item_node, next_item_node, i_j_lit]) |
|
|
|
length_of_preceding_container = data['lengths'][item_number] |
|
model.Add(positions[next_item_number] == positions[item_number] + |
|
length_of_preceding_container).OnlyEnforceIf(i_j_lit) |
|
|
|
|
|
# create the Circuit constraint |
|
# print(arcs) |
|
model.AddCircuit(arcs) |
|
|
|
#bin_arcs.append(arcs) |
|
# [END constraints] |
|
|
|
# [START objective] |
|
# Maximize total value of packed items. |
|
model.Maximize(sum(value)) |
|
# [END objective] |
|
|
|
# [START solver] |
|
solver = cp_model.CpSolver() |
|
# [END solver] |
|
|
|
solver.parameters.log_search_progress = True |
|
solver.parameters.max_time_in_seconds = 300 |
|
solver.parameters.num_search_workers = 9 |
|
|
|
# [START solve] |
|
status = solver.Solve(model) |
|
# [END solve] |
|
|
|
# [START print_solution] |
|
if status == cp_model.OPTIMAL: |
|
for i, l in enumerate(item_loads): |
|
print(f"item {i}, weight is {data['weights'][i]}, is is loaded? {solver.Value(is_loaded[i])}, load is {solver.Value(l)}") |
|
# for key, value in literals.items(): |
|
# for kk, vv in value.items(): |
|
# print(f"{key}: {kk} {vv} is {solver.Value(vv)}") |
|
print_solutions(data, solver, x, positions) |
|
else: |
|
print('you messed up dude') |
|
|
|
# [END solutions_printer] |
|
|
|
|
|
|
|
if __name__ == '__main__': |
|
main() |
|
# [END program] |