2021-05-03 12:11:39 +02:00
|
|
|
#!/usr/bin/env python3
|
2025-01-10 11:35:44 +01:00
|
|
|
# Copyright 2010-2025 Google LLC
|
2014-01-29 15:21:07 +00:00
|
|
|
# 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.
|
2022-10-07 18:21:23 +02:00
|
|
|
|
2022-04-14 14:07:58 +02:00
|
|
|
# [START program]
|
2020-11-30 11:59:56 +01:00
|
|
|
"""Appointment selection.
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2020-11-30 11:59:56 +01:00
|
|
|
This module maximizes the number of appointments that can
|
|
|
|
|
be fulfilled by a crew of installers while staying close to ideal
|
|
|
|
|
ratio of appointment types.
|
|
|
|
|
"""
|
2018-08-30 07:59:49 +02:00
|
|
|
|
2020-11-30 11:59:56 +01:00
|
|
|
# overloaded sum() clashes with pytype.
|
|
|
|
|
|
2022-04-14 14:07:58 +02:00
|
|
|
# [START import]
|
2020-11-30 11:59:56 +01:00
|
|
|
from absl import app
|
|
|
|
|
from absl import flags
|
2014-01-29 15:21:07 +00:00
|
|
|
from ortools.linear_solver import pywraplp
|
2020-11-30 11:59:56 +01:00
|
|
|
from ortools.sat.python import cp_model
|
2023-07-01 06:06:53 +02:00
|
|
|
|
2022-04-14 14:07:58 +02:00
|
|
|
# [END import]
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
_LOAD_MIN = flags.DEFINE_integer("load_min", 480, "Minimum load in minutes.")
|
|
|
|
|
_LOAD_MAX = flags.DEFINE_integer("load_max", 540, "Maximum load in minutes.")
|
|
|
|
|
_COMMUTE_TIME = flags.DEFINE_integer("commute_time", 30, "Commute time in minutes.")
|
|
|
|
|
_NUM_WORKERS = flags.DEFINE_integer("num_workers", 98, "Maximum number of workers.")
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2018-09-06 15:09:32 +02:00
|
|
|
|
2018-11-20 04:35:48 -08:00
|
|
|
class AllSolutionCollector(cp_model.CpSolverSolutionCallback):
|
|
|
|
|
"""Stores all solutions."""
|
|
|
|
|
|
|
|
|
|
def __init__(self, variables):
|
|
|
|
|
cp_model.CpSolverSolutionCallback.__init__(self)
|
|
|
|
|
self.__variables = variables
|
|
|
|
|
self.__collect = []
|
|
|
|
|
|
2023-11-16 19:46:56 +01:00
|
|
|
def on_solution_callback(self) -> None:
|
2018-11-20 04:35:48 -08:00
|
|
|
"""Collect a new combination."""
|
2023-11-16 19:46:56 +01:00
|
|
|
combination = [self.value(v) for v in self.__variables]
|
2018-11-20 04:35:48 -08:00
|
|
|
self.__collect.append(combination)
|
|
|
|
|
|
2023-11-16 19:46:56 +01:00
|
|
|
def combinations(self) -> list[list[int]]:
|
2018-11-20 04:35:48 -08:00
|
|
|
"""Returns all collected combinations."""
|
|
|
|
|
return self.__collect
|
|
|
|
|
|
|
|
|
|
|
2023-12-03 16:59:16 +01:00
|
|
|
def enumerate_all_knapsacks_with_repetition(
|
2023-11-16 19:46:56 +01:00
|
|
|
item_sizes: list[int], total_size_min: int, total_size_max: int
|
|
|
|
|
) -> list[list[int]]:
|
2020-11-30 11:59:56 +01:00
|
|
|
"""Enumerate all possible knapsacks with total size in the given range.
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Args:
|
|
|
|
|
item_sizes: a list of integers. item_sizes[i] is the size of item #i.
|
|
|
|
|
total_size_min: an integer, the minimum total size.
|
|
|
|
|
total_size_max: an integer, the maximum total size.
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Returns:
|
|
|
|
|
The list of all the knapsacks whose total size is in the given inclusive
|
|
|
|
|
range. Each knapsack is a list [#item0, #item1, ... ], where #itemK is an
|
|
|
|
|
nonnegative integer: the number of times we put item #K in the knapsack.
|
|
|
|
|
"""
|
2018-11-20 04:35:48 -08:00
|
|
|
model = cp_model.CpModel()
|
2023-11-16 19:46:56 +01:00
|
|
|
variables = [
|
|
|
|
|
model.new_int_var(0, total_size_max // size, "") for size in item_sizes
|
|
|
|
|
]
|
2020-11-30 11:59:56 +01:00
|
|
|
load = sum(variables[i] * size for i, size in enumerate(item_sizes))
|
2023-11-16 19:46:56 +01:00
|
|
|
model.add_linear_constraint(load, total_size_min, total_size_max)
|
2018-11-20 04:35:48 -08:00
|
|
|
|
|
|
|
|
solver = cp_model.CpSolver()
|
|
|
|
|
solution_collector = AllSolutionCollector(variables)
|
2021-05-03 12:11:39 +02:00
|
|
|
# Enumerate all solutions.
|
|
|
|
|
solver.parameters.enumerate_all_solutions = True
|
2023-11-16 19:46:56 +01:00
|
|
|
# solve
|
|
|
|
|
solver.solve(model, solution_collector)
|
2018-11-20 04:35:48 -08:00
|
|
|
return solution_collector.combinations()
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2018-09-06 15:09:32 +02:00
|
|
|
|
2023-12-03 16:59:16 +01:00
|
|
|
def aggregate_item_collections_optimally(
|
2023-11-16 19:46:56 +01:00
|
|
|
item_collections: list[list[int]],
|
|
|
|
|
max_num_collections: int,
|
|
|
|
|
ideal_item_ratios: list[float],
|
|
|
|
|
) -> list[int]:
|
2020-11-30 11:59:56 +01:00
|
|
|
"""Selects a set (with repetition) of combination of items optimally.
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Given a set of collections of N possible items (in each collection, an item
|
|
|
|
|
may appear multiple times), a given "ideal breakdown of items", and a
|
|
|
|
|
maximum number of collections, this method finds the optimal way to
|
|
|
|
|
aggregate the collections in order to:
|
|
|
|
|
- maximize the overall number of items
|
|
|
|
|
- while keeping the ratio of each item, among the overall selection, as close
|
|
|
|
|
as possible to a given input ratio (which depends on the item).
|
|
|
|
|
Each collection may be selected more than one time.
|
|
|
|
|
|
|
|
|
|
Args:
|
|
|
|
|
item_collections: a list of item collections. Each item collection is a list
|
|
|
|
|
of integers [#item0, ..., #itemN-1], where #itemK is the number of times
|
|
|
|
|
item #K appears in the collection, and N is the number of distinct items.
|
|
|
|
|
max_num_collections: an integer, the maximum number of item collections that
|
|
|
|
|
may be selected (counting repetitions of the same collection).
|
|
|
|
|
ideal_item_ratios: A list of N float which sums to 1.0: the K-th element is
|
|
|
|
|
the ideal ratio of item #K in the whole aggregated selection.
|
|
|
|
|
|
|
|
|
|
Returns:
|
|
|
|
|
A pair (objective value, list of pairs (item collection, num_selections)),
|
|
|
|
|
where:
|
|
|
|
|
- "objective value" is the value of the internal objective function used
|
|
|
|
|
by the MIP Solver
|
|
|
|
|
- Each "item collection" is an element of the input item_collections
|
|
|
|
|
- and its associated "num_selections" is the number of times it was
|
|
|
|
|
selected.
|
|
|
|
|
"""
|
|
|
|
|
solver = pywraplp.Solver.CreateSolver("SCIP")
|
2022-06-03 17:09:29 +02:00
|
|
|
if not solver:
|
2022-10-07 18:21:23 +02:00
|
|
|
return []
|
2020-11-30 11:59:56 +01:00
|
|
|
n = len(ideal_item_ratios)
|
|
|
|
|
num_distinct_collections = len(item_collections)
|
|
|
|
|
max_num_items_per_collection = 0
|
|
|
|
|
for template in item_collections:
|
2023-07-01 06:06:53 +02:00
|
|
|
max_num_items_per_collection = max(max_num_items_per_collection, sum(template))
|
2020-11-30 11:59:56 +01:00
|
|
|
upper_bound = max_num_items_per_collection * max_num_collections
|
|
|
|
|
|
|
|
|
|
# num_selections_of_collection[i] is an IntVar that represents the number
|
|
|
|
|
# of times that we will use collection #i in our global selection.
|
|
|
|
|
num_selections_of_collection = [
|
2023-07-01 06:06:53 +02:00
|
|
|
solver.IntVar(0, max_num_collections, "s[%d]" % i)
|
2020-11-30 11:59:56 +01:00
|
|
|
for i in range(num_distinct_collections)
|
2018-11-11 09:39:59 +01:00
|
|
|
]
|
|
|
|
|
|
2020-11-30 11:59:56 +01:00
|
|
|
# num_overall_item[i] is an IntVar that represents the total count of item #i,
|
|
|
|
|
# aggregated over all selected collections. This is enforced with dedicated
|
|
|
|
|
# constraints that bind them with the num_selections_of_collection vars.
|
|
|
|
|
num_overall_item = [
|
2023-07-01 06:06:53 +02:00
|
|
|
solver.IntVar(0, upper_bound, "num_overall_item[%d]" % i) for i in range(n)
|
2020-11-30 11:59:56 +01:00
|
|
|
]
|
|
|
|
|
for i in range(n):
|
2018-11-11 09:39:59 +01:00
|
|
|
ct = solver.Constraint(0.0, 0.0)
|
2020-11-30 11:59:56 +01:00
|
|
|
ct.SetCoefficient(num_overall_item[i], -1)
|
|
|
|
|
for j in range(num_distinct_collections):
|
2023-07-01 06:06:53 +02:00
|
|
|
ct.SetCoefficient(num_selections_of_collection[j], item_collections[j][i])
|
2020-11-30 11:59:56 +01:00
|
|
|
|
|
|
|
|
# Maintain the num_all_item variable as the sum of all num_overall_item
|
|
|
|
|
# variables.
|
2023-07-01 06:06:53 +02:00
|
|
|
num_all_items = solver.IntVar(0, upper_bound, "num_all_items")
|
2020-11-30 11:59:56 +01:00
|
|
|
solver.Add(solver.Sum(num_overall_item) == num_all_items)
|
|
|
|
|
|
|
|
|
|
# Sets the total number of workers.
|
|
|
|
|
solver.Add(solver.Sum(num_selections_of_collection) == max_num_collections)
|
|
|
|
|
|
|
|
|
|
# Objective variables.
|
|
|
|
|
deviation_vars = [
|
2023-07-01 06:06:53 +02:00
|
|
|
solver.NumVar(0, upper_bound, "deviation_vars[%d]" % i) for i in range(n)
|
2018-06-11 11:51:18 +02:00
|
|
|
]
|
2020-11-30 11:59:56 +01:00
|
|
|
for i in range(n):
|
|
|
|
|
deviation = deviation_vars[i]
|
2023-07-01 06:06:53 +02:00
|
|
|
solver.Add(
|
|
|
|
|
deviation >= num_overall_item[i] - ideal_item_ratios[i] * num_all_items
|
|
|
|
|
)
|
|
|
|
|
solver.Add(
|
|
|
|
|
deviation >= ideal_item_ratios[i] * num_all_items - num_overall_item[i]
|
|
|
|
|
)
|
2018-11-11 09:39:59 +01:00
|
|
|
|
2020-11-30 11:59:56 +01:00
|
|
|
solver.Maximize(num_all_items - solver.Sum(deviation_vars))
|
2018-11-11 09:39:59 +01:00
|
|
|
|
|
|
|
|
result_status = solver.Solve()
|
|
|
|
|
|
|
|
|
|
if result_status == pywraplp.Solver.OPTIMAL:
|
2020-11-30 11:59:56 +01:00
|
|
|
# The problem has an optimal solution.
|
|
|
|
|
return [int(v.solution_value()) for v in num_selections_of_collection]
|
|
|
|
|
return []
|
|
|
|
|
|
|
|
|
|
|
2023-12-03 16:59:16 +01:00
|
|
|
def get_optimal_schedule(
|
2025-07-23 17:38:49 +02:00
|
|
|
demand: list[tuple[float, str, int]],
|
2023-11-16 19:46:56 +01:00
|
|
|
) -> list[tuple[int, list[tuple[int, str]]]]:
|
2020-11-30 11:59:56 +01:00
|
|
|
"""Computes the optimal schedule for the installation input.
|
|
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Args:
|
|
|
|
|
demand: a list of "appointment types". Each "appointment type" is a triple
|
|
|
|
|
(ideal_ratio_pct, name, duration_minutes), where ideal_ratio_pct is the
|
|
|
|
|
ideal percentage (in [0..100.0]) of that type of appointment among all
|
|
|
|
|
appointments scheduled.
|
2020-11-30 11:59:56 +01:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
Returns:
|
|
|
|
|
The same output type as EnumerateAllKnapsacksWithRepetition.
|
|
|
|
|
"""
|
2023-12-03 16:59:16 +01:00
|
|
|
combinations = enumerate_all_knapsacks_with_repetition(
|
2023-11-16 19:46:56 +01:00
|
|
|
[a[2] + _COMMUTE_TIME.value for a in demand],
|
|
|
|
|
_LOAD_MIN.value,
|
|
|
|
|
_LOAD_MAX.value,
|
2023-07-01 06:06:53 +02:00
|
|
|
)
|
|
|
|
|
print(
|
|
|
|
|
(
|
|
|
|
|
"Found %d possible day schedules " % len(combinations)
|
|
|
|
|
+ "(i.e. combination of appointments filling up one worker's day)"
|
|
|
|
|
)
|
|
|
|
|
)
|
2020-11-30 11:59:56 +01:00
|
|
|
|
2023-12-03 16:59:16 +01:00
|
|
|
selection = aggregate_item_collections_optimally(
|
2023-07-01 06:06:53 +02:00
|
|
|
combinations, _NUM_WORKERS.value, [a[0] / 100.0 for a in demand]
|
|
|
|
|
)
|
2020-11-30 11:59:56 +01:00
|
|
|
output = []
|
2023-11-16 19:46:56 +01:00
|
|
|
for i, s in enumerate(selection):
|
|
|
|
|
if s != 0:
|
2023-07-01 06:06:53 +02:00
|
|
|
output.append(
|
|
|
|
|
(
|
2023-11-16 19:46:56 +01:00
|
|
|
s,
|
2023-07-01 06:06:53 +02:00
|
|
|
[
|
2023-11-16 19:46:56 +01:00
|
|
|
(combinations[i][t], d[1])
|
|
|
|
|
for t, d in enumerate(demand)
|
2023-07-01 06:06:53 +02:00
|
|
|
if combinations[i][t] != 0
|
|
|
|
|
],
|
|
|
|
|
)
|
|
|
|
|
)
|
2020-11-30 11:59:56 +01:00
|
|
|
|
|
|
|
|
return output
|
|
|
|
|
|
|
|
|
|
|
2022-10-07 18:21:23 +02:00
|
|
|
def main(_):
|
2023-07-01 06:06:53 +02:00
|
|
|
demand = [(45.0, "Type1", 90), (30.0, "Type2", 120), (25.0, "Type3", 180)]
|
|
|
|
|
print("*** input problem ***")
|
|
|
|
|
print("Appointments: ")
|
2020-11-30 11:59:56 +01:00
|
|
|
for a in demand:
|
2023-07-01 06:06:53 +02:00
|
|
|
print(" %.2f%% of %s : %d min" % (a[0], a[1], a[2]))
|
|
|
|
|
print("Commute time = %d" % _COMMUTE_TIME.value)
|
|
|
|
|
print(
|
|
|
|
|
"Acceptable duration of a work day = [%d..%d]"
|
|
|
|
|
% (_LOAD_MIN.value, _LOAD_MAX.value)
|
|
|
|
|
)
|
|
|
|
|
print("%d workers" % _NUM_WORKERS.value)
|
2023-12-03 16:59:16 +01:00
|
|
|
selection = get_optimal_schedule(demand)
|
2020-11-30 11:59:56 +01:00
|
|
|
print()
|
|
|
|
|
installed = 0
|
|
|
|
|
installed_per_type = {}
|
2018-11-11 09:39:59 +01:00
|
|
|
for a in demand:
|
2020-11-30 11:59:56 +01:00
|
|
|
installed_per_type[a[1]] = 0
|
|
|
|
|
|
2022-04-14 14:07:58 +02:00
|
|
|
# [START print_solution]
|
2023-07-01 06:06:53 +02:00
|
|
|
print("*** output solution ***")
|
2018-11-11 09:39:59 +01:00
|
|
|
for template in selection:
|
2020-11-30 11:59:56 +01:00
|
|
|
num_instances = template[0]
|
2023-07-01 06:06:53 +02:00
|
|
|
print("%d schedules with " % num_instances)
|
2018-11-11 09:39:59 +01:00
|
|
|
for t in template[1]:
|
2020-11-30 11:59:56 +01:00
|
|
|
mult = t[0]
|
2023-07-01 06:06:53 +02:00
|
|
|
print(" %d installation of type %s" % (mult, t[1]))
|
2020-11-30 11:59:56 +01:00
|
|
|
installed += num_instances * mult
|
|
|
|
|
installed_per_type[t[1]] += num_instances * mult
|
|
|
|
|
|
|
|
|
|
print()
|
2023-07-01 06:06:53 +02:00
|
|
|
print("%d installations planned" % installed)
|
2020-11-30 11:59:56 +01:00
|
|
|
for a in demand:
|
2022-10-07 18:21:23 +02:00
|
|
|
name = a[1]
|
|
|
|
|
per_type = installed_per_type[name]
|
|
|
|
|
if installed != 0:
|
|
|
|
|
print(
|
2023-11-16 19:46:56 +01:00
|
|
|
f" {per_type} ({per_type * 100.0 / installed}%) installations of"
|
|
|
|
|
f" type {name} planned"
|
2022-10-07 18:21:23 +02:00
|
|
|
)
|
|
|
|
|
else:
|
2023-07-01 06:06:53 +02:00
|
|
|
print(f" {per_type} installations of type {name} planned")
|
2022-04-14 14:07:58 +02:00
|
|
|
# [END print_solution]
|
2014-01-29 15:21:07 +00:00
|
|
|
|
2018-09-06 15:09:32 +02:00
|
|
|
|
2023-07-01 06:06:53 +02:00
|
|
|
if __name__ == "__main__":
|
2022-10-07 18:21:23 +02:00
|
|
|
app.run(main)
|
2022-04-14 14:07:58 +02:00
|
|
|
# [END program]
|
