ナーススケジューリング
Published:
By nobCategory: Posts
Tags: 数理最適化 Python-MIP Python
ナーススケジューリング問題を検索してみると論文が見つかった。
統計数理 第53巻 第2号 ナース・スケジューリング － 調査・モデル化・アルゴリズム －
東京女子医科大学付属病院の1996年11月の勤務表作成条件が記載されている。この条件を基に勤務表を作成する。
import pandas as pd
from IPython.display import display
pd.options.display.max_columns = 40
pd.options.display.max_rows = 100
シフト拘束条件
日勤のシフト拘束条件
- 毎日の日勤について, 各チームからベテラン(skilled)もしくは2年目(second-year)ナースが少なくとも2名(a_ss_day_lower_bound, b_ss_day_lower_bound, c_ss_day_lower_bound), 全体でベテランが少なくとも1名(s_day_lower_bound)必要
- 通常のウィークデイは, 合計で10-11名, 各チーム3-4名必要
- 日曜日と祝祭日(4日と 23日? )には合計9名, 各チーム3名ずつ必要
- 6日と19日は, 合計12-14名, 各チーム4-5名必要
- 26日は, 合計12-16名, 各チーム4-6名必要
日勤のシフト拘束条件(?)
- 土曜日は合計で9-10名, 各チーム3-4名必要
夜勤のシフト拘束条件
- 毎日の夜勤に働くナースの合計数は4名(all_night_lower_bound)必要
- A, B, C各チームからベテラン(skilled)もしくは2年目(second-year)ナースが少なくとも1名(a_ss_night_lower_bound, b_ss_night_lower_bound, c_ss_night_lower_bound), 全体でベテランが少なくとも1名(s_night_lower_bound)必要
shift_constraints = pd.read_csv("data/pism/53-2-231-table-11.csv")
shift_constraints["day"] = shift_constraints["day"] - 1
display(shift_constraints)
| day | day_of_week | holiday | all_day_lower_bound | all_day_upper_bound | all_night_lower_bound | all_night_upper_bound | a_day_lower_bound | a_day_upper_bound | a_night_lower_bound | a_night_upper_bound | b_day_lower_bound | b_day_upper_bound | b_night_lower_bound | b_night_upper_bound | c_day_lower_bound | c_day_upper_bound | c_night_lower_bound | c_night_upper_bound | s_day_lower_bound | s_day_upper_bound | s_night_lower_bound | s_night_upper_bound | a_ss_day_lower_bound | a_ss_day_upper_bound | a_ss_night_lower_bound | a_ss_night_upper_bound | b_ss_day_lower_bound | b_ss_day_upper_bound | b_ss_night_lower_bound | b_ss_night_upper_bound | c_ss_day_lower_bound | c_ss_day_upper_bound | c_ss_night_lower_bound | c_ss_night_upper_bound | rq_day_lower_bound | rq_day_upper_bound | rq_night_lower_bound | rq_night_upper_bound | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | Fri | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 1 | 1 | Sat | 0 | 9 | 10 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 2 | 2 | Sun | 0 | 9 | 9 | 4 | 4 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 0 | 7 | 0 | 1 |
| 3 | 3 | Mon | 1 | 9 | 9 | 4 | 4 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 0 | 7 | 0 | 1 |
| 4 | 4 | Tue | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 5 | 5 | Wed | 0 | 12 | 14 | 4 | 4 | 4 | 5 | 1 | 2 | 4 | 5 | 1 | 2 | 4 | 5 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 6 | 6 | Thu | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 7 | 7 | Fri | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 8 | 8 | Sat | 0 | 9 | 10 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 9 | 9 | Sun | 0 | 9 | 9 | 4 | 4 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 0 | 7 | 0 | 1 |
| 10 | 10 | Mon | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 11 | 11 | Tue | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 12 | 12 | Wed | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 13 | 13 | Thu | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 14 | 14 | Fri | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 15 | 15 | Sat | 0 | 9 | 10 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 16 | 16 | Sun | 0 | 9 | 9 | 4 | 4 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 0 | 7 | 0 | 1 |
| 17 | 17 | Mon | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 18 | 18 | Tue | 0 | 12 | 14 | 4 | 4 | 4 | 5 | 1 | 2 | 4 | 5 | 1 | 2 | 4 | 5 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 19 | 19 | Wed | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 20 | 20 | Thu | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 21 | 21 | Fri | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 22 | 22 | Sat | 1 | 9 | 10 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 23 | 23 | Sun | 0 | 9 | 9 | 4 | 4 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 3 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 1 | 2 | 0 | 7 | 0 | 1 |
| 24 | 24 | Mon | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 25 | 25 | Tue | 0 | 12 | 16 | 4 | 4 | 4 | 6 | 1 | 2 | 4 | 6 | 1 | 2 | 4 | 6 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 5 | 1 | 2 | 2 | 5 | 1 | 2 | 2 | 5 | 1 | 2 | 0 | 7 | 0 | 1 |
| 26 | 26 | Wed | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 27 | 27 | Thu | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 28 | 28 | Fri | 0 | 10 | 11 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
| 29 | 29 | Sat | 0 | 9 | 10 | 4 | 4 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 2 | 4 | 1 | 2 | 0 | 7 | 0 | 1 |
ナース拘束条件
ナースの休日, 日勤, 夜勤の回数の下限値と上限値(Type I拘束条件)
ナースの属性を読み込む。
| 項目 | 意味 |
|---|---|
| team | 所属チーム |
| nurse_no | ナース |
| skill_level | スキルレベル |
| off_lower_bound | 休日の回数の下限 |
| off_upper_bound | 休日の回数の上限 |
| day_lower_bound | 日勤の回数の下限 |
| day_upper_bound | 日勤の回数の上限 |
| night_lower_bound | 夜勤の回数の下限 |
| night_upper_bound | 夜勤の回数の上限 |
nurse_constraints = pd.read_csv("data/pism/53-2-231-table-12.csv")
nurse_constraints["nurse_no"] = nurse_constraints["nurse_no"] - 1
display(nurse_constraints)
| team | nurse_no | skill_level | off_lower_bound | off_upper_bound | day_lower_bound | day_upper_bound | night_lower_bound | night_upper_bound | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | A | 0 | skilled | 9 | 10 | 9 | 12 | 4 | 5 |
| 1 | A | 1 | skilled | 9 | 10 | 10 | 13 | 4 | 5 |
| 2 | A | 2 | skilled | 9 | 10 | 10 | 13 | 4 | 5 |
| 3 | A | 3 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 4 | A | 4 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 5 | A | 5 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 6 | A | 6 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 7 | A | 7 | recently_qualified | 9 | 10 | 8 | 11 | 4 | 5 |
| 8 | A | 8 | recently_qualified | 9 | 10 | 9 | 12 | 4 | 5 |
| 9 | A | 9 | recently_qualified | 9 | 10 | 10 | 13 | 4 | 5 |
| 10 | B | 10 | skilled | 9 | 10 | 9 | 12 | 4 | 5 |
| 11 | B | 11 | skilled | 9 | 10 | 10 | 13 | 4 | 5 |
| 12 | B | 12 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 13 | B | 13 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 14 | B | 14 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 15 | B | 15 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 16 | B | 16 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 17 | B | 17 | recently_qualified | 9 | 10 | 9 | 12 | 4 | 5 |
| 18 | B | 18 | recently_qualified | 8 | 10 | 18 | 20 | 0 | 0 |
| 19 | C | 19 | skilled | 9 | 10 | 10 | 13 | 4 | 5 |
| 20 | C | 20 | skilled | 9 | 10 | 10 | 13 | 4 | 5 |
| 21 | C | 21 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 22 | C | 22 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 23 | C | 23 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 24 | C | 24 | second_year | 9 | 10 | 10 | 13 | 4 | 5 |
| 25 | C | 25 | second_year | 9 | 10 | 9 | 12 | 4 | 5 |
| 26 | C | 26 | recently_qualified | 9 | 10 | 8 | 11 | 4 | 5 |
| 27 | C | 27 | recently_qualified | 9 | 10 | 14 | 17 | 2 | 3 |
上限回数を合計しても勤務表作成対象の日数に満たないように見えるが、夜勤の後は夜勤明けというシフトになるので合計は30以上の値になっている。
nurse_constraints[
[
"off_upper_bound",
"day_upper_bound",
"night_upper_bound",
"night_upper_bound",
]
].sum(axis=1)
0 32
1 33
2 33
3 33
4 33
5 33
6 32
7 31
8 32
9 33
10 32
11 33
12 33
13 33
14 32
15 33
16 32
17 32
18 30
19 33
20 33
21 33
22 32
23 32
24 33
25 32
26 31
27 33
dtype: int64
前月末からのスケジュール(Type II拘束条件)
前月末の勤務表を読み込む。
| 記号 | 意味 |
|---|---|
| - | 日勤 |
| N | 夜勤 |
| n | 夜勤明け |
| / | 休日 |
| + | その他の勤務 |
拘束条件に4日連続の日勤は許されていない、とあるのだが2人が該当している。
last_shift_table_temp = pd.read_csv("data/pism/53-2-231-table-13-1.csv")
last_shift_table_temp["nurse_no"] = last_shift_table_temp["nurse_no"] - 1
display(last_shift_table_temp)
| nurse_no | 26 | 27 | 28 | 29 | 30 | 31 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | / | / | / | - | - | N |
| 1 | 1 | / | / | - | - | - | / |
| 2 | 2 | - | N | n | / | - | - |
| 3 | 3 | N | n | / | / | N | n |
| 4 | 4 | - | - | N | n | / | - |
| 5 | 5 | n | / | - | - | N | n |
| 6 | 6 | - | - | + | N | n | / |
| 7 | 7 | / | / | N | n | / | - |
| 8 | 8 | N | n | / | - | - | + |
| 9 | 9 | / | - | - | - | + | + |
| 10 | 10 | / | / | / | - | N | n |
| 11 | 11 | N | n | / | / | / | - |
| 12 | 12 | / | / | N | n | / | / |
| 13 | 13 | - | - | - | N | n | / |
| 14 | 14 | n | / | - | - | - | N |
| 15 | 15 | - | N | n | / | - | - |
| 16 | 16 | / | / | - | N | n | / |
| 17 | 17 | - | - | - | - | + | - |
| 18 | 18 | - | - | - | / | - | - |
| 19 | 19 | - | N | n | / | / | - |
| 20 | 20 | - | - | - | / | - | / |
| 21 | 21 | / | / | N | n | / | - |
| 22 | 22 | N | n | / | - | - | - |
| 23 | 23 | n | / | + | N | n | / |
| 24 | 24 | / | - | - | + | - | N |
| 25 | 25 | / | / | / | / | N | n |
| 26 | 26 | / | - | - | - | - | N |
| 27 | 27 | - | N | n | / | + | - |
後で使いやすいように変形する
last_shift_table = (
pd.DataFrame(
last_shift_table_temp.drop("nurse_no", axis=1).unstack(level=1)
)
.reset_index()
.dropna()
)
last_shift_table.columns = ["day", "staff", "shift"]
last_shift_table["day"] = last_shift_table["day"].astype(int) - 32
last_shift_table = pd.get_dummies(
last_shift_table,
columns=["shift"],
dtype=int,
prefix="",
prefix_sep="",
)
last_shift_table = (
last_shift_table.set_index(["staff", "day"]).stack().reset_index()
)
last_shift_table.columns = ["staff", "day", "shift", "var"]
display(last_shift_table)
| staff | day | shift | var | |
|---|---|---|---|---|
| 0 | 0 | -6 | + | 0 |
| 1 | 0 | -6 | - | 0 |
| 2 | 0 | -6 | / | 1 |
| 3 | 0 | -6 | N | 0 |
| 4 | 0 | -6 | n | 0 |
| ... | ... | ... | ... | ... |
| 835 | 27 | -1 | + | 0 |
| 836 | 27 | -1 | - | 1 |
| 837 | 27 | -1 | / | 0 |
| 838 | 27 | -1 | N | 0 |
| 839 | 27 | -1 | n | 0 |
840 rows × 4 columns
ナース達の勤務や休みの希望（Type II拘束条件）
| 記号 | 意味 |
|---|---|
| - | 日勤 |
| N | 夜勤 |
| n | 夜勤明け |
| / | 休日 |
| + | その他の勤務 |
| * | 夜勤不可 |
| x | 日勤不可 |
desired_shifts_temp = pd.read_csv("data/pism/53-2-231-table-13-2.csv")
desired_shifts_temp["nurse_no"] = desired_shifts_temp["nurse_no"] - 1
display(desired_shifts_temp)
| nurse_no | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | n | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN |
| 1 | 1 | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | * | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | / | NaN | * |
| 2 | 2 | NaN | NaN | / | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 3 | 3 | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 4 | 4 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 5 | 5 | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 6 | 6 | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | / | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 7 | 7 | NaN | NaN | NaN | NaN | NaN | + | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | / | x | NaN | NaN | NaN | NaN | NaN |
| 8 | 8 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / | / | NaN | NaN | NaN | NaN | NaN |
| 9 | 9 | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 10 | 10 | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | / | NaN | NaN | NaN |
| 11 | 11 | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 12 | 12 | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / | NaN | NaN | NaN | NaN |
| 13 | 13 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 14 | 14 | n | / | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / |
| 15 | 15 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / | NaN | NaN | NaN | NaN | NaN | NaN |
| 16 | 16 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 17 | 17 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 18 | 18 | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 19 | 19 | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 20 | 20 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 21 | 21 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 22 | 22 | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | / | x | NaN | NaN | NaN | NaN | NaN | NaN |
| 23 | 23 | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 24 | 24 | n | / | NaN | NaN | NaN | N | n | / | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | N | n | / | NaN | NaN | NaN | NaN |
| 25 | 25 | / | NaN | NaN | NaN | N | n | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | - |
| 26 | 26 | n | / | NaN | NaN | NaN | NaN | NaN | NaN | / | NaN | NaN | + | NaN | / | NaN | NaN | NaN | NaN | NaN | NaN | + | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
| 27 | 27 | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
夜勤明けの翌日は休日である必要があるのだが、夜勤, 夜勤明け, その他の勤務という勤務を希望しているナースがいる(#25)。
夜勤不可は日勤・夜勤明け・その他の勤務・休日の何れか、日勤不可は夜勤・夜勤明け・その他の勤務・休日の何れかを希望していると解釈した。
その他の勤務はセミナー参加等ということで制約があるようにも思える。
後で使いやすいように変形する
desired_shifts = (
pd.DataFrame(desired_shifts_temp.drop("nurse_no", axis=1).unstack(level=1))
.reset_index()
.dropna()
)
desired_shifts.columns = ["day", "staff", "shift"]
desired_shifts["day"] = desired_shifts["day"].astype(int) - 1
desired_shifts = desired_shifts.reindex(
columns=["staff", "day", "shift"]
).sort_values(["staff", "day", "shift"])
display(desired_shifts)
| staff | day | shift | |
|---|---|---|---|
| 0 | 0 | 0 | n |
| 28 | 0 | 1 | / |
| 308 | 0 | 11 | + |
| 728 | 0 | 26 | / |
| 1 | 1 | 0 | / |
| 421 | 1 | 15 | * |
| 729 | 1 | 26 | / |
| 757 | 1 | 27 | / |
| 813 | 1 | 29 | * |
| 58 | 2 | 2 | / |
| 86 | 2 | 3 | / |
| 450 | 2 | 16 | / |
| 3 | 3 | 0 | / |
| 535 | 3 | 19 | / |
| 5 | 5 | 0 | / |
| 174 | 6 | 6 | + |
| 258 | 6 | 9 | / |
| 286 | 6 | 10 | / |
| 147 | 7 | 5 | + |
| 203 | 7 | 7 | + |
| 623 | 7 | 22 | / |
| 651 | 7 | 23 | / |
| 679 | 7 | 24 | x |
| 316 | 8 | 11 | + |
| 596 | 8 | 21 | N |
| 624 | 8 | 22 | n |
| 652 | 8 | 23 | / |
| 680 | 8 | 24 | / |
| 177 | 9 | 6 | / |
| 10 | 10 | 0 | / |
| 318 | 10 | 11 | + |
| 710 | 10 | 25 | / |
| 738 | 10 | 26 | / |
| 67 | 11 | 2 | / |
| 12 | 12 | 0 | / |
| 656 | 12 | 23 | N |
| 684 | 12 | 24 | n |
| 712 | 12 | 25 | / |
| 377 | 13 | 13 | / |
| 405 | 13 | 14 | / |
| 14 | 14 | 0 | n |
| 42 | 14 | 1 | / |
| 182 | 14 | 6 | + |
| 546 | 14 | 19 | / |
| 770 | 14 | 27 | N |
| 798 | 14 | 28 | n |
| 826 | 14 | 29 | / |
| 295 | 15 | 10 | N |
| 323 | 15 | 11 | n |
| 351 | 15 | 12 | / |
| 603 | 15 | 21 | N |
| 631 | 15 | 22 | n |
| 659 | 15 | 23 | / |
| 324 | 16 | 11 | + |
| 381 | 17 | 13 | + |
| 74 | 18 | 2 | / |
| 326 | 18 | 11 | + |
| 382 | 18 | 13 | + |
| 159 | 19 | 5 | / |
| 553 | 21 | 19 | / |
| 190 | 22 | 6 | + |
| 638 | 22 | 22 | / |
| 666 | 22 | 23 | x |
| 191 | 23 | 6 | + |
| 24 | 24 | 0 | n |
| 52 | 24 | 1 | / |
| 164 | 24 | 5 | N |
| 192 | 24 | 6 | n |
| 220 | 24 | 7 | / |
| 668 | 24 | 23 | N |
| 696 | 24 | 24 | n |
| 724 | 24 | 25 | / |
| 25 | 25 | 0 | / |
| 137 | 25 | 4 | N |
| 165 | 25 | 5 | n |
| 193 | 25 | 6 | + |
| 837 | 25 | 29 | - |
| 26 | 26 | 0 | n |
| 54 | 26 | 1 | / |
| 250 | 26 | 8 | / |
| 334 | 26 | 11 | + |
| 390 | 26 | 13 | / |
| 586 | 26 | 20 | + |
その他の制約(Type III)
- 各ナース, 少なくとも1回は週末2連休(2-3日, 3-4日, 9-10日, 16-17日, 23-24日の中から選ぶ. 4日は祭日)を必要とする
- 夜勤の翌日は休みでなければならない
- 夜勤と夜勤の間は少なくとも3日あけなければならない
- 1週間に1回は休みが入らなくてはならない
- 4日連続の日勤は許されていない
- 日勤, 休み, 日勤, 休み, 日勤というパターンは許されていない
- 前月末とのシフトの並びについても考慮しなければならない
モデルの作成
以上の制約条件からモデルを作成する。
目的関数はシフトの実現度とした。
from mip import Model, OptimizationStatus, maximize, xsum
model = Model(name="nurse_scheduling", solver_name="cbc")
model.threads = -1
staffs = nurse_constraints["nurse_no"]
staffs.name = "staff"
days = shift_constraints["day"]
days.name = "day"
shifts = pd.Series(["-", "N", "n", "/", "+"], name="shift")
num_staffs = staffs.shape[0]
num_days = days.shape[0]
num_shifts = shifts.shape[0]
# 当月のみの制約条件を作成する為に用いる
shift_table = pd.merge(pd.merge(staffs, days, "cross"), shifts, "cross")
shift_table["var"] = model.add_var_tensor(
(len(shift_table),), "var", var_type="B"
)
shift_table = shift_table.join(
nurse_constraints.set_index("nurse_no"),
on="staff",
how="left",
)
# 前月・当月を通して制約条件を作成する為に用いる
shift_temp = pd.concat(
[
last_shift_table.join(
nurse_constraints.set_index("nurse_no"),
on="staff",
how="left",
),
shift_table,
],
ignore_index=True,
)
shift_table = shift_table.join(
shift_constraints.set_index("day"),
on="day",
how="left",
)
"""
制約条件
"""
# 全員にシフトが割り当てられている
for _, shift in shift_table.groupby(["staff", "day"]):
model += xsum(shift["var"]) == 1
# 禁止パターン
forbidden_patterns = [
# 夜勤の翌日は夜勤明けでなければならない
["N", "-"],
["N", "/"],
["N", "+"],
# 夜勤開けの翌日は休みでなければならない
["n", "-"],
["n", "n"],
["n", "N"],
# 全ての拘束条件を満たしているとされる勤務表の例(表1)を見ると
# ナース#26の5日からのシフトでは夜勤明け, その他の勤務が許容されている。
# 勤務の希望(表13)を見るとこれは本人の希望のようである。
# ["n","+"],
#
# 夜勤明け, その他の勤務, 休日は許容されているようである
# しかし夜勤明け, その他の勤務, 日勤を禁止するとinfeasibleとなる
# ["n","+", "-"],
["n", "+", "N"],
["n", "+", "n"],
["n", "+", "+"],
["-", "n"],
["/", "n"],
["+", "n"],
# 日勤, 休み, 日勤, 休み, 日勤というパターンは許されていない
["-", "/", "-", "/", "-"],
# 4日連続の日勤は許されていない
["-", "-", "-", "-"],
]
shift_temp_days = shift_temp["day"].unique()
num_shift_temp_days = shift_temp_days.shape[0]
# 前月・当月通しての制約
for _, groupby_staff in shift_temp.groupby("staff"):
# 1週間に1回は休みが入らなくてはならない
window = 7
for days_in_window in [
shift_temp_days[i : i + window]
for i in range(0, num_shift_temp_days - window + 1, 1)
]:
model += (
xsum(
groupby_staff[
(groupby_staff["day"].isin(days_in_window))
& (groupby_staff["shift"] == "/")
]["var"]
)
>= 1
)
# 禁止パターン
for forbidden_pattern in forbidden_patterns:
window = len(forbidden_pattern)
for days_in_window in [
shift_temp_days[i : i + window]
for i in range(0, num_shift_temp_days - window + 1, 1)
]:
model += (
xsum(
[
groupby_staff.at[j, "var"]
for j in [
groupby_staff.index[
(groupby_staff["day"] == days_in_window[k])
& (
groupby_staff["shift"]
== forbidden_pattern[k]
)
].to_list()[0]
for k in range(len(days_in_window))
]
]
)
<= window - 1
)
# 夜勤と夜勤の間は少なくとも3日あけなければならない
# 夜勤明けを含めて5日間で計算する
window = 5
for days_in_window in [
shift_temp_days[i : i + window]
for i in range(0, num_shift_temp_days - window + 1, 1)
]:
model += (
xsum(
groupby_staff[
(groupby_staff["day"].isin(days_in_window))
& (groupby_staff["shift"] == "N")
]["var"]
)
<= 1
)
# 当月のみ、ナース毎の制約
for _, groupby_staff in shift_table.groupby("staff"):
# 日勤の上限・下限
for shift_name, shift_code in zip(
["day", "night", "off"], ["-", "N", "/"]
):
lower_bound = groupby_staff.at[
groupby_staff.index[0], "{}_lower_bound".format(shift_name)
]
upper_bound = groupby_staff.at[
groupby_staff.index[0], "{}_upper_bound".format(shift_name)
]
staff_sum = xsum(
groupby_staff[groupby_staff["shift"] == shift_code]["var"]
)
model += staff_sum >= lower_bound
model += staff_sum <= upper_bound
team_shift_skill_levels = [
[
"all_day",
["A", "B", "C"],
["skilled", "second_year", "recently_qualified"],
"-",
],
[
"all_night",
["A", "B", "C"],
["skilled", "second_year", "recently_qualified"],
"N",
],
["s_day", ["A", "B", "C"], ["skilled"], "-"],
["s_night", ["A", "B", "C"], ["skilled"], "N"],
["rq_day", ["A", "B", "C"], ["recently_qualified"], "-"],
["rq_night", ["A", "B", "C"], ["recently_qualified"], "N"],
["a_ss_day", ["A"], ["skilled", "second_year"], "-"],
["a_ss_night", ["A"], ["skilled", "second_year"], "N"],
["b_ss_day", ["B"], ["skilled", "second_year"], "-"],
["b_ss_night", ["B"], ["skilled", "second_year"], "N"],
["c_ss_day", ["C"], ["skilled", "second_year"], "-"],
["c_ss_night", ["C"], ["skilled", "second_year"], "N"],
["a_day", ["A"], ["skilled", "second_year", "recently_qualified"], "-"],
["a_night", ["A"], ["skilled", "second_year", "recently_qualified"], "N"],
["b_day", ["B"], ["skilled", "second_year", "recently_qualified"], "-"],
["b_night", ["B"], ["skilled", "second_year", "recently_qualified"], "N"],
["c_day", ["C"], ["skilled", "second_year", "recently_qualified"], "-"],
["c_night", ["C"], ["skilled", "second_year", "recently_qualified"], "N"],
]
# 日毎
for day, groupby_day in shift_table.groupby("day"):
for shift_name, team, skill_level, shift_code in team_shift_skill_levels:
lower_bound = groupby_day.at[
groupby_day.index[0], "{}_lower_bound".format(shift_name)
]
upper_bound = groupby_day.at[
groupby_day.index[0], "{}_upper_bound".format(shift_name)
]
num_assigned_staffs = xsum(
groupby_day[
(groupby_day["team"].isin(team))
& (groupby_day["skill_level"].isin(skill_level))
& (groupby_day["shift"] == shift_code)
]["var"]
)
model += num_assigned_staffs >= lower_bound
model += num_assigned_staffs <= upper_bound
# 各ナース, 少なくとも1回は週末2連休
# (2-3日, 3-4日, 9-10日, 16-17日, 23-24日の中から選ぶ.4日は祭日)
# を必要とする
holiday_in_rows = list(
map(
lambda x: list(map(lambda y: y - 1, x)),
[
[2, 3],
[3, 4],
[9, 10],
[16, 17],
[23, 24],
],
)
)
holiday_constr = model.add_var_tensor(
(
num_staffs,
len(holiday_in_rows),
),
"holiday_constr",
var_type="B",
)
for staff, groupby_staff in shift_table.groupby("staff"):
for i, holiday_in_a_row in enumerate(holiday_in_rows):
model += (
xsum(
[
groupby_staff.at[j, "var"]
for j in [
groupby_staff.index[
(groupby_staff["day"] == day)
& (groupby_staff["shift"] == "/")
].to_list()[0]
for day in holiday_in_a_row
]
]
)
== 2 * holiday_constr[staff, i]
)
model += xsum(holiday_constr[staff]) >= 1
"""
目的関数
"""
# シフトの希望が最大限叶うようにする
shift_satisfaction = desired_shifts.join(
shift_table.set_index(["day", "staff", "shift"]),
on=["day", "staff", "shift"],
how="left",
)
# 夜勤以外を希望 => 日勤・夜勤明け・休日
for index, row in shift_satisfaction[
shift_satisfaction["shift"].isin(["*"])
].iterrows():
shift_satisfaction = pd.concat(
[
shift_satisfaction,
shift_table[
(shift_table["day"] == row["day"])
& (shift_table["staff"] == row["staff"])
& (shift_table["shift"].isin(["-", "n", "+", "/"]))
],
],
ignore_index=True,
)
# 日勤以外を希望 => 夜勤・夜勤明け・休日
for index, row in shift_satisfaction[
shift_satisfaction["shift"].isin(["x"])
].iterrows():
shift_satisfaction = pd.concat(
[
shift_satisfaction,
shift_table[
(shift_table["day"] == row["day"])
& (shift_table["staff"] == row["staff"])
& (shift_table["shift"].isin(["N", "n", "+", "/"]))
],
],
ignore_index=True,
)
shift_satisfaction = shift_satisfaction[
shift_satisfaction["shift"].isin(["-", "N", "n", "/", "+"])
]
model.objective = maximize(xsum(shift_satisfaction["var"]))
model.optimize()
Welcome to the CBC MILP Solver
Version: devel
Build Date: Aug 4 2024
Starting solution of the Linear programming relaxation problem using Primal Simplex
Coin0506I Presolve 14089 (-1607) rows, 4059 (-281) columns and 54492 (-4728) elements
Clp0030I 37 infeas 0.081453527, obj 83.004957 - mu 0.0018794197, its 52, 3829 interior
Clp1000I sum of infeasibilities 5.24049e-05 - average 3.71956e-09, 152 fixed columns
Coin0506I Presolve 13092 (-997) rows, 3885 (-174) columns and 51396 (-3096) elements
Clp0006I 0 Obj 82.982614 Primal inf 8.0589436e-06 (18) Dual inf 8.1e+13 (150)
Clp0029I End of values pass after 3885 iterations
Clp0014I Perturbing problem by 0.001% of 1.5248741 - largest nonzero change 2.9978863e-05 ( 0.0014989431%) - largest zero change 2.963241e-05
Clp0000I Optimal - objective value 83
Clp0000I Optimal - objective value 83
Coin0511I After Postsolve, objective 83, infeasibilities - dual 0 (0), primal 0 (0)
Clp0006I 0 Obj 83 Dual inf 3.999995 (5)
Clp0014I Perturbing problem by 0.001% of 1.5148767 - largest nonzero change 2.9943914e-05 ( 0.0014971957%) - largest zero change 2.9976734e-05
Clp0000I Optimal - objective value 83
Clp0000I Optimal - objective value 83
Clp0000I Optimal - objective value 83
Coin0511I After Postsolve, objective 83, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 83 - 0 iterations time 1.782, Presolve 0.03, Idiot 1.74
Starting MIP optimization
threads was changed from 0 to 20
maxSavedSolutions was changed from 1 to 10
Continuous objective value is 83 - 0.004914 seconds
Cgl0002I 112 variables fixed
Cgl0003I 77 fixed, 0 tightened bounds, 4664 strengthened rows, 2462 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 10457 strengthened rows, 91 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 6674 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 4948 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2176 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 762 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 305 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 111 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 55 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 25 strengthened rows, 0 substitutions
Cgl0004I processed model has 7152 rows, 3092 columns (3092 integer (3092 of which binary)) and 47765 elements
Coin3009W Conflict graph built in 0.007 seconds, density: 0.076%
Cgl0015I Clique Strengthening extended 2 cliques, 6 were dominated
After applying Clique Strengthening continuous objective value is 78
Cbc0045I Nauty did not find any useful orbits in time 0.229306
Cbc0038I Initial state - 878 integers unsatisfied sum - 208.403
Cbc0038I Pass 1: (20.55 seconds) suminf. 87.71429 (420) obj. 73.4286 iterations 4990
Cbc0038I Pass 2: (23.52 seconds) suminf. 40.50199 (243) obj. 70.74 iterations 5871
Cbc0038I Pass 3: (27.06 seconds) suminf. 22.28571 (70) obj. 69.8571 iterations 6072
Cbc0038I Pass 4: (28.01 seconds) suminf. 0.00000 (0) obj. 69 iterations 1480
Cbc0038I Solution found of 69
Cbc0038I Before mini branch and bound, 1979 integers at bound fixed and 41 continuous
Cbc0038I Full problem 7148 rows 3092 columns, reduced to 2691 rows 756 columns
Cbc0038I Mini branch and bound improved solution from 69 to 69 (36.11 seconds)
Cbc0038I Round again with cutoff of 70.7999
Cbc0038I Pass 5: (36.13 seconds) suminf. 87.71429 (420) obj. 73.4286 iterations 0
Cbc0038I Pass 6: (38.22 seconds) suminf. 40.92920 (236) obj. 70.7999 iterations 4238
Cbc0038I Pass 7: (40.75 seconds) suminf. 25.13309 (96) obj. 70.7999 iterations 4271
Cbc0038I Pass 8: (41.09 seconds) suminf. 25.09490 (94) obj. 70.7999 iterations 488
Cbc0038I Pass 9: (41.36 seconds) suminf. 24.96113 (93) obj. 70.7999 iterations 375
Cbc0038I Pass 10: (42.18 seconds) suminf. 17.87483 (60) obj. 70.7999 iterations 1212
Cbc0038I Pass 11: (42.98 seconds) suminf. 11.79946 (64) obj. 70.7999 iterations 1195
Cbc0038I Pass 12: (44.24 seconds) suminf. 7.19919 (37) obj. 70.7999 iterations 2000
Cbc0038I Pass 13: (44.71 seconds) suminf. 1.20054 (6) obj. 70.7999 iterations 673
Cbc0038I Solution found of 71
Cbc0038I Before mini branch and bound, 1961 integers at bound fixed and 39 continuous
Cbc0038I Full problem 7148 rows 3092 columns, reduced to 2742 rows 777 columns
Cbc0038I Mini branch and bound did not improve solution (52.99 seconds)
Cbc0038I Round again with cutoff of 73.1999
Cbc0038I Pass 14: (53.45 seconds) suminf. 87.71429 (420) obj. 73.4286 iterations 0
Cbc0038I Pass 15: (56.11 seconds) suminf. 52.10027 (347) obj. 73.1999 iterations 5388
Cbc0038I Pass 16: (58.27 seconds) suminf. 31.42105 (127) obj. 73.1999 iterations 3852
Cbc0038I Pass 17: (61.23 seconds) suminf. 15.38822 (63) obj. 73.1999 iterations 4817
Cbc0038I Pass 18: (61.94 seconds) suminf. 12.03285 (61) obj. 73.1999 iterations 1080
Cbc0038I Pass 19: (62.34 seconds) suminf. 11.37460 (42) obj. 73.1999 iterations 580
Cbc0038I Pass 20: (62.62 seconds) suminf. 11.37460 (42) obj. 73.1999 iterations 399
Cbc0038I Pass 21: (62.70 seconds) suminf. 11.37460 (42) obj. 73.1999 iterations 101
Cbc0038I Pass 22: (62.80 seconds) suminf. 11.37460 (42) obj. 73.1999 iterations 120
Cbc0038I Pass 23: (62.89 seconds) suminf. 11.37460 (42) obj. 73.1999 iterations 106
Cbc0038I Pass 24: (63.85 seconds) suminf. 13.86619 (40) obj. 73.1999 iterations 1388
Cbc0038I Pass 25: (64.77 seconds) suminf. 10.39968 (41) obj. 73.1999 iterations 1380
Cbc0038I Pass 26: (65.09 seconds) suminf. 10.79968 (24) obj. 73.1999 iterations 436
Cbc0038I Pass 27: (65.38 seconds) suminf. 3.79968 (10) obj. 73.1999 iterations 375
Cbc0038I Pass 28: (65.57 seconds) suminf. 3.79968 (10) obj. 73.1999 iterations 255
Cbc0038I Pass 29: (65.75 seconds) suminf. 3.79968 (10) obj. 73.1999 iterations 213
Cbc0038I Pass 30: (66.37 seconds) suminf. 3.00000 (6) obj. 74 iterations 839
Cbc0038I Pass 31: (66.67 seconds) suminf. 3.00000 (6) obj. 74 iterations 420
Cbc0038I Pass 32: (66.73 seconds) suminf. 3.00000 (6) obj. 74 iterations 76
Cbc0038I Pass 33: (67.62 seconds) suminf. 7.19952 (18) obj. 73.1999 iterations 1362
Cbc0038I Pass 34: (68.71 seconds) suminf. 5.79968 (14) obj. 73.1999 iterations 1574
Cbc0038I Pass 35: (68.79 seconds) suminf. 3.79968 (10) obj. 73.1999 iterations 93
Cbc0038I Pass 36: (68.99 seconds) suminf. 3.79968 (10) obj. 73.1999 iterations 263
Cbc0038I Pass 37: (69.57 seconds) suminf. 3.00000 (6) obj. 74 iterations 782
Cbc0038I Pass 38: (69.81 seconds) suminf. 3.00000 (6) obj. 74 iterations 332
Cbc0038I Pass 39: (70.66 seconds) suminf. 3.39984 (8) obj. 73.1999 iterations 1256
Cbc0038I Pass 40: (71.37 seconds) suminf. 3.39984 (8) obj. 73.1999 iterations 1036
Cbc0038I Pass 41: (71.51 seconds) suminf. 3.39984 (8) obj. 73.1999 iterations 180
Cbc0038I Pass 42: (71.55 seconds) suminf. 3.39984 (8) obj. 73.1999 iterations 39
Cbc0038I Pass 43: (71.63 seconds) suminf. 3.39984 (8) obj. 73.1999 iterations 103
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1903 integers at bound fixed and 39 continuous
Cbc0038I Full problem 7148 rows 3092 columns, reduced to 2846 rows 825 columns
Cbc0038I Mini branch and bound improved solution from 71 to 76 (79.77 seconds)
Cbc0038I Round again with cutoff of 77.2999
Cbc0038I Reduced cost fixing fixed 186 variables on major pass 4
Cbc0038I Pass 43: (81.30 seconds) suminf. 117.60168 (548) obj. 77.7801 iterations 2207
Cbc0038I Pass 44: (83.00 seconds) suminf. 92.56253 (454) obj. 77.7094 iterations 3497
Cbc0038I Pass 45: (84.53 seconds) suminf. 79.08765 (523) obj. 77.6998 iterations 3059
Cbc0038I Pass 46: (85.18 seconds) suminf. 74.92516 (599) obj. 77.6775 iterations 1392
Cbc0038I Pass 47: (85.74 seconds) suminf. 72.99388 (556) obj. 77.6234 iterations 1125
Cbc0038I Pass 48: (86.09 seconds) suminf. 72.25176 (700) obj. 77.6925 iterations 652
Cbc0038I Pass 49: (86.33 seconds) suminf. 70.51602 (563) obj. 77.6691 iterations 456
Cbc0038I Pass 50: (86.63 seconds) suminf. 69.12010 (485) obj. 77.6848 iterations 548
Cbc0038I Pass 51: (87.19 seconds) suminf. 69.04219 (642) obj. 77.6602 iterations 1055
Cbc0038I Pass 52: (87.69 seconds) suminf. 67.33903 (504) obj. 77.7208 iterations 900
Cbc0038I Pass 53: (88.06 seconds) suminf. 67.03349 (627) obj. 77.7362 iterations 651
Cbc0038I Pass 54: (88.34 seconds) suminf. 66.67160 (591) obj. 77.7352 iterations 521
Cbc0038I Pass 55: (88.51 seconds) suminf. 66.51749 (620) obj. 77.7299 iterations 281
Cbc0038I Pass 56: (89.03 seconds) suminf. 61.39625 (593) obj. 77.5215 iterations 1044
Cbc0038I Pass 57: (89.84 seconds) suminf. 57.48672 (722) obj. 77.5069 iterations 1639
Cbc0038I Pass 58: (90.06 seconds) suminf. 54.43044 (741) obj. 77.4195 iterations 445
Cbc0038I Pass 59: (90.46 seconds) suminf. 52.38335 (619) obj. 77.3283 iterations 846
Cbc0038I Pass 60: (90.79 seconds) suminf. 52.83048 (602) obj. 77.3333 iterations 641
Cbc0038I Pass 61: (90.99 seconds) suminf. 52.73466 (600) obj. 77.3212 iterations 303
Cbc0038I Pass 62: (91.36 seconds) suminf. 53.36578 (663) obj. 77.3716 iterations 716
Cbc0038I Pass 63: (91.71 seconds) suminf. 50.82215 (717) obj. 77.3302 iterations 712
Cbc0038I Pass 64: (92.30 seconds) suminf. 48.67360 (702) obj. 77.2999 iterations 1138
Cbc0038I Pass 65: (92.51 seconds) suminf. 48.53307 (645) obj. 77.2999 iterations 336
Cbc0038I Pass 66: (92.69 seconds) suminf. 48.15155 (670) obj. 77.2999 iterations 275
Cbc0038I Pass 67: (92.91 seconds) suminf. 47.91803 (684) obj. 77.2999 iterations 362
Cbc0038I Pass 68: (93.09 seconds) suminf. 48.66993 (710) obj. 77.3333 iterations 321
Cbc0038I Pass 69: (93.74 seconds) suminf. 55.67194 (586) obj. 77.3333 iterations 1511
Cbc0038I Pass 70: (94.67 seconds) suminf. 48.17802 (713) obj. 77.3106 iterations 2011
Cbc0038I Pass 71: (94.97 seconds) suminf. 47.93933 (691) obj. 77.2999 iterations 536
Cbc0038I Pass 72: (95.35 seconds) suminf. 48.52271 (774) obj. 77.3333 iterations 712
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1381 integers at bound fixed and 31 continuous
Cbc0038I Mini branch and bound did not improve solution (95.37 seconds)
Cbc0038I After 95.37 seconds - Feasibility pump exiting with objective of 76 - took 77.04 seconds
Cbc0012I Integer solution of 76 found by feasibility pump after 0 iterations and 0 nodes (95.38 seconds)
Cbc0038I Full problem 7148 rows 3092 columns, reduced to 2176 rows 593 columns
Cbc0031I 6 added rows had average density of 27.5
Cbc0013I At root node, 6 cuts changed objective from 78 to 78 in 3 passes
Cbc0014I Cut generator 0 (Probing) - 1 row cuts average 8.0 elements, 15 column cuts (15 active) in 0.080 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 5 row cuts average 115.6 elements, 0 column cuts (0 active) in 0.255 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.081 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.040 seconds - new frequency is -100
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.216 seconds - new frequency is -100
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.021 seconds - new frequency is -100
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 7 (TwoMirCuts) - 46 row cuts average 103.1 elements, 0 column cuts (0 active) in 0.333 seconds - new frequency is -100
Cbc0014I Cut generator 8 (ZeroHalf) - 4 row cuts average 7.2 elements, 0 column cuts (0 active) in 0.784 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 76 best solution, best possible 78 (104.45 seconds)
Cbc0010I After 1 nodes, 2 on tree, 76 best solution, best possible 78 (107.23 seconds)
Cbc0010I After 2 nodes, 2 on tree, 76 best solution, best possible 78 (109.74 seconds)
Cbc0010I After 4 nodes, 2 on tree, 76 best solution, best possible 78 (111.28 seconds)
Cbc0010I After 5 nodes, 1 on tree, 76 best solution, best possible 78 (112.94 seconds)
Cbc0010I After 7 nodes, 2 on tree, 76 best solution, best possible 78 (113.78 seconds)
Cbc0010I After 9 nodes, 2 on tree, 76 best solution, best possible 78 (114.60 seconds)
Cbc0010I After 11 nodes, 2 on tree, 76 best solution, best possible 78 (116.24 seconds)
Cbc0010I After 13 nodes, 2 on tree, 76 best solution, best possible 78 (117.05 seconds)
Cbc0010I After 17 nodes, 1 on tree, 76 best solution, best possible 78 (118.65 seconds)
Cbc0010I After 19 nodes, 2 on tree, 76 best solution, best possible 78 (119.68 seconds)
Cbc0010I After 24 nodes, 1 on tree, 76 best solution, best possible 78 (121.04 seconds)
Cbc0010I After 26 nodes, 2 on tree, 76 best solution, best possible 78 (122.25 seconds)
Cbc0010I After 28 nodes, 1 on tree, 76 best solution, best possible 78 (123.10 seconds)
Cbc0010I After 34 nodes, 6 on tree, 76 best solution, best possible 78 (123.99 seconds)
Cbc0010I After 37 nodes, 7 on tree, 76 best solution, best possible 78 (124.69 seconds)
Cbc0010I After 40 nodes, 7 on tree, 76 best solution, best possible 78 (125.87 seconds)
Cbc0010I After 42 nodes, 8 on tree, 76 best solution, best possible 78 (126.60 seconds)
Cbc0010I After 48 nodes, 12 on tree, 76 best solution, best possible 78 (127.51 seconds)
Cbc0010I After 53 nodes, 16 on tree, 76 best solution, best possible 78 (128.22 seconds)
Cbc0010I After 55 nodes, 16 on tree, 76 best solution, best possible 78 (129.23 seconds)
Cbc0010I After 60 nodes, 18 on tree, 76 best solution, best possible 78 (130.31 seconds)
Cbc0010I After 64 nodes, 21 on tree, 76 best solution, best possible 78 (131.35 seconds)
Cbc0010I After 68 nodes, 25 on tree, 76 best solution, best possible 78 (132.24 seconds)
Cbc0010I After 76 nodes, 29 on tree, 76 best solution, best possible 78 (133.13 seconds)
Cbc0010I After 78 nodes, 31 on tree, 76 best solution, best possible 78 (133.90 seconds)
Cbc0010I After 82 nodes, 34 on tree, 76 best solution, best possible 78 (134.72 seconds)
Cbc0010I After 86 nodes, 38 on tree, 76 best solution, best possible 78 (135.51 seconds)
Cbc0010I After 89 nodes, 40 on tree, 76 best solution, best possible 78 (136.29 seconds)
Cbc0010I After 93 nodes, 43 on tree, 76 best solution, best possible 78 (137.02 seconds)
Cbc0010I After 99 nodes, 47 on tree, 76 best solution, best possible 78 (138.09 seconds)
Cbc0010I After 102 nodes, 49 on tree, 76 best solution, best possible 78 (138.88 seconds)
Cbc0010I After 106 nodes, 50 on tree, 76 best solution, best possible 78 (139.92 seconds)
Cbc0010I After 109 nodes, 51 on tree, 76 best solution, best possible 78 (140.67 seconds)
Cbc0010I After 114 nodes, 54 on tree, 76 best solution, best possible 78 (141.81 seconds)
Cbc0010I After 118 nodes, 57 on tree, 76 best solution, best possible 78 (142.75 seconds)
Cbc0010I After 123 nodes, 60 on tree, 76 best solution, best possible 78 (143.79 seconds)
Cbc0010I After 127 nodes, 63 on tree, 76 best solution, best possible 78 (145.27 seconds)
Cbc0010I After 132 nodes, 67 on tree, 76 best solution, best possible 78 (146.66 seconds)
Cbc0010I After 137 nodes, 69 on tree, 76 best solution, best possible 78 (147.40 seconds)
Cbc0010I After 141 nodes, 71 on tree, 76 best solution, best possible 78 (148.25 seconds)
Cbc0010I After 144 nodes, 73 on tree, 76 best solution, best possible 78 (149.21 seconds)
Cbc0010I After 146 nodes, 74 on tree, 76 best solution, best possible 78 (150.79 seconds)
Cbc0010I After 149 nodes, 76 on tree, 76 best solution, best possible 78 (151.65 seconds)
Cbc0010I After 156 nodes, 81 on tree, 76 best solution, best possible 78 (152.61 seconds)
Cbc0010I After 159 nodes, 83 on tree, 76 best solution, best possible 78 (154.08 seconds)
Cbc0010I After 164 nodes, 85 on tree, 76 best solution, best possible 78 (155.40 seconds)
Cbc0010I After 169 nodes, 90 on tree, 76 best solution, best possible 78 (156.37 seconds)
Cbc0010I After 172 nodes, 92 on tree, 76 best solution, best possible 78 (157.33 seconds)
Cbc0010I After 176 nodes, 93 on tree, 76 best solution, best possible 78 (158.41 seconds)
Cbc0010I After 179 nodes, 95 on tree, 76 best solution, best possible 78 (159.15 seconds)
Cbc0010I After 182 nodes, 97 on tree, 76 best solution, best possible 78 (160.06 seconds)
Cbc0010I After 187 nodes, 98 on tree, 76 best solution, best possible 78 (161.14 seconds)
Cbc0010I After 191 nodes, 100 on tree, 76 best solution, best possible 78 (162.18 seconds)
Cbc0010I After 197 nodes, 105 on tree, 76 best solution, best possible 78 (163.02 seconds)
Cbc0010I After 201 nodes, 108 on tree, 76 best solution, best possible 78 (164.01 seconds)
Cbc0010I After 203 nodes, 108 on tree, 76 best solution, best possible 78 (164.84 seconds)
Cbc0010I After 206 nodes, 110 on tree, 76 best solution, best possible 78 (165.92 seconds)
Cbc0010I After 209 nodes, 112 on tree, 76 best solution, best possible 78 (166.77 seconds)
Cbc0010I After 213 nodes, 113 on tree, 76 best solution, best possible 78 (167.91 seconds)
Cbc0010I After 219 nodes, 117 on tree, 76 best solution, best possible 78 (168.62 seconds)
Cbc0010I After 224 nodes, 120 on tree, 76 best solution, best possible 78 (169.69 seconds)
Cbc0010I After 226 nodes, 122 on tree, 76 best solution, best possible 78 (170.58 seconds)
Cbc0010I After 228 nodes, 123 on tree, 76 best solution, best possible 78 (171.42 seconds)
Cbc0010I After 229 nodes, 124 on tree, 76 best solution, best possible 78 (172.13 seconds)
Cbc0010I After 232 nodes, 124 on tree, 76 best solution, best possible 78 (173.21 seconds)
Cbc0010I After 239 nodes, 127 on tree, 76 best solution, best possible 78 (173.94 seconds)
Cbc0010I After 245 nodes, 131 on tree, 76 best solution, best possible 78 (174.91 seconds)
Cbc0010I After 247 nodes, 132 on tree, 76 best solution, best possible 78 (175.91 seconds)
Cbc0010I After 248 nodes, 132 on tree, 76 best solution, best possible 78 (176.99 seconds)
Cbc0010I After 252 nodes, 135 on tree, 76 best solution, best possible 78 (178.00 seconds)
Cbc0010I After 260 nodes, 142 on tree, 76 best solution, best possible 78 (179.14 seconds)
Cbc0010I After 266 nodes, 145 on tree, 76 best solution, best possible 78 (180.27 seconds)
Cbc0010I After 268 nodes, 146 on tree, 76 best solution, best possible 78 (181.20 seconds)
Cbc0010I After 270 nodes, 147 on tree, 76 best solution, best possible 78 (182.16 seconds)
Cbc0010I After 273 nodes, 149 on tree, 76 best solution, best possible 78 (182.93 seconds)
Cbc0010I After 279 nodes, 154 on tree, 76 best solution, best possible 78 (183.75 seconds)
Cbc0010I After 284 nodes, 157 on tree, 76 best solution, best possible 78 (184.72 seconds)
Cbc0010I After 287 nodes, 157 on tree, 76 best solution, best possible 78 (185.72 seconds)
Cbc0010I After 289 nodes, 159 on tree, 76 best solution, best possible 78 (186.46 seconds)
Cbc0010I After 292 nodes, 161 on tree, 76 best solution, best possible 78 (187.20 seconds)
Cbc0010I After 297 nodes, 163 on tree, 76 best solution, best possible 78 (188.05 seconds)
Cbc0010I After 301 nodes, 165 on tree, 76 best solution, best possible 78 (189.32 seconds)
Cbc0010I After 305 nodes, 166 on tree, 76 best solution, best possible 78 (190.09 seconds)
Cbc0010I After 308 nodes, 169 on tree, 76 best solution, best possible 78 (190.95 seconds)
Cbc0010I After 310 nodes, 169 on tree, 76 best solution, best possible 78 (191.77 seconds)
Cbc0010I After 317 nodes, 174 on tree, 76 best solution, best possible 78 (192.59 seconds)
Cbc0010I After 320 nodes, 176 on tree, 76 best solution, best possible 78 (193.60 seconds)
Cbc0010I After 322 nodes, 178 on tree, 76 best solution, best possible 78 (194.48 seconds)
Cbc0010I After 328 nodes, 183 on tree, 76 best solution, best possible 78 (195.20 seconds)
Cbc0010I After 334 nodes, 186 on tree, 76 best solution, best possible 78 (196.10 seconds)
Cbc0010I After 336 nodes, 186 on tree, 76 best solution, best possible 78 (196.85 seconds)
Cbc0010I After 340 nodes, 188 on tree, 76 best solution, best possible 78 (197.65 seconds)
Cbc0010I After 345 nodes, 192 on tree, 76 best solution, best possible 78 (198.42 seconds)
Cbc0010I After 349 nodes, 194 on tree, 76 best solution, best possible 78 (199.20 seconds)
Cbc0010I After 354 nodes, 197 on tree, 76 best solution, best possible 78 (200.29 seconds)
Cbc0010I After 359 nodes, 202 on tree, 76 best solution, best possible 78 (201.02 seconds)
Cbc0010I After 364 nodes, 203 on tree, 76 best solution, best possible 78 (201.88 seconds)
Cbc0010I After 367 nodes, 206 on tree, 76 best solution, best possible 78 (202.62 seconds)
Cbc0010I After 371 nodes, 209 on tree, 76 best solution, best possible 78 (203.34 seconds)
Cbc0010I After 377 nodes, 210 on tree, 76 best solution, best possible 78 (204.09 seconds)
Cbc0010I After 382 nodes, 213 on tree, 76 best solution, best possible 78 (205.04 seconds)
Cbc0010I After 387 nodes, 216 on tree, 76 best solution, best possible 78 (206.01 seconds)
Cbc0010I After 392 nodes, 219 on tree, 76 best solution, best possible 78 (206.72 seconds)
Cbc0010I After 395 nodes, 220 on tree, 76 best solution, best possible 78 (207.43 seconds)
Cbc0010I After 402 nodes, 225 on tree, 76 best solution, best possible 78 (208.18 seconds)
Cbc0010I After 408 nodes, 227 on tree, 76 best solution, best possible 78 (209.42 seconds)
Cbc0010I After 416 nodes, 232 on tree, 76 best solution, best possible 78 (210.33 seconds)
Cbc0010I After 419 nodes, 234 on tree, 76 best solution, best possible 78 (211.31 seconds)
Cbc0010I After 429 nodes, 239 on tree, 76 best solution, best possible 78 (212.12 seconds)
Cbc0010I After 433 nodes, 242 on tree, 76 best solution, best possible 78 (212.95 seconds)
Cbc0010I After 436 nodes, 243 on tree, 76 best solution, best possible 78 (213.71 seconds)
Cbc0010I After 440 nodes, 245 on tree, 76 best solution, best possible 78 (214.46 seconds)
Cbc0010I After 448 nodes, 250 on tree, 76 best solution, best possible 78 (215.29 seconds)
Cbc0010I After 455 nodes, 256 on tree, 76 best solution, best possible 78 (216.66 seconds)
Cbc0010I After 460 nodes, 257 on tree, 76 best solution, best possible 78 (217.43 seconds)
Cbc0010I After 468 nodes, 260 on tree, 76 best solution, best possible 78 (218.44 seconds)
Cbc0010I After 473 nodes, 263 on tree, 76 best solution, best possible 78 (219.22 seconds)
Cbc0010I After 481 nodes, 267 on tree, 76 best solution, best possible 78 (220.05 seconds)
Cbc0010I After 487 nodes, 273 on tree, 76 best solution, best possible 78 (220.83 seconds)
Cbc0010I After 491 nodes, 274 on tree, 76 best solution, best possible 78 (221.69 seconds)
Cbc0010I After 500 nodes, 279 on tree, 76 best solution, best possible 78 (222.45 seconds)
Cbc0010I After 503 nodes, 279 on tree, 76 best solution, best possible 78 (223.28 seconds)
Cbc0010I After 512 nodes, 284 on tree, 76 best solution, best possible 78 (224.28 seconds)
Cbc0010I After 519 nodes, 288 on tree, 76 best solution, best possible 78 (225.73 seconds)
Cbc0010I After 526 nodes, 292 on tree, 76 best solution, best possible 78 (226.60 seconds)
Cbc0010I After 536 nodes, 297 on tree, 76 best solution, best possible 78 (227.31 seconds)
Cbc0010I After 541 nodes, 300 on tree, 76 best solution, best possible 78 (228.10 seconds)
Cbc0010I After 544 nodes, 302 on tree, 76 best solution, best possible 78 (228.98 seconds)
Cbc0010I After 552 nodes, 306 on tree, 76 best solution, best possible 78 (229.69 seconds)
Cbc0010I After 559 nodes, 311 on tree, 76 best solution, best possible 78 (230.41 seconds)
Cbc0010I After 563 nodes, 313 on tree, 76 best solution, best possible 78 (231.11 seconds)
Cbc0010I After 567 nodes, 314 on tree, 76 best solution, best possible 78 (231.98 seconds)
Cbc0010I After 574 nodes, 316 on tree, 76 best solution, best possible 78 (232.81 seconds)
Cbc0010I After 583 nodes, 321 on tree, 76 best solution, best possible 78 (233.72 seconds)
Cbc0010I After 590 nodes, 325 on tree, 76 best solution, best possible 78 (234.44 seconds)
Cbc0010I After 592 nodes, 326 on tree, 76 best solution, best possible 78 (235.28 seconds)
Cbc0010I After 598 nodes, 328 on tree, 76 best solution, best possible 78 (236.00 seconds)
Cbc0010I After 609 nodes, 336 on tree, 76 best solution, best possible 78 (236.80 seconds)
Cbc0010I After 613 nodes, 339 on tree, 76 best solution, best possible 78 (237.53 seconds)
Cbc0010I After 620 nodes, 341 on tree, 76 best solution, best possible 78 (238.36 seconds)
Cbc0010I After 628 nodes, 344 on tree, 76 best solution, best possible 78 (239.30 seconds)
Cbc0010I After 634 nodes, 350 on tree, 76 best solution, best possible 78 (240.14 seconds)
Cbc0010I After 639 nodes, 353 on tree, 76 best solution, best possible 78 (240.93 seconds)
Cbc0010I After 648 nodes, 359 on tree, 76 best solution, best possible 78 (241.71 seconds)
Cbc0010I After 651 nodes, 360 on tree, 76 best solution, best possible 78 (242.44 seconds)
Cbc0010I After 659 nodes, 364 on tree, 76 best solution, best possible 78 (243.31 seconds)
Cbc0010I After 666 nodes, 365 on tree, 76 best solution, best possible 78 (244.16 seconds)
Cbc0010I After 675 nodes, 373 on tree, 76 best solution, best possible 78 (245.11 seconds)
Cbc0010I After 681 nodes, 375 on tree, 76 best solution, best possible 78 (245.82 seconds)
Cbc0010I After 688 nodes, 379 on tree, 76 best solution, best possible 78 (246.79 seconds)
Cbc0010I After 694 nodes, 383 on tree, 76 best solution, best possible 78 (247.50 seconds)
Cbc0010I After 700 nodes, 386 on tree, 76 best solution, best possible 78 (248.21 seconds)
Cbc0010I After 706 nodes, 389 on tree, 76 best solution, best possible 78 (249.30 seconds)
Cbc0010I After 714 nodes, 393 on tree, 76 best solution, best possible 78 (250.05 seconds)
Cbc0010I After 724 nodes, 400 on tree, 76 best solution, best possible 78 (250.91 seconds)
Cbc0010I After 727 nodes, 402 on tree, 76 best solution, best possible 78 (251.62 seconds)
Cbc0010I After 734 nodes, 408 on tree, 76 best solution, best possible 78 (252.47 seconds)
Cbc0010I After 741 nodes, 412 on tree, 76 best solution, best possible 78 (253.31 seconds)
Cbc0010I After 745 nodes, 415 on tree, 76 best solution, best possible 78 (254.03 seconds)
Cbc0010I After 754 nodes, 419 on tree, 76 best solution, best possible 78 (255.30 seconds)
Cbc0010I After 762 nodes, 422 on tree, 76 best solution, best possible 78 (256.01 seconds)
Cbc0010I After 769 nodes, 425 on tree, 76 best solution, best possible 78 (256.80 seconds)
Cbc0010I After 774 nodes, 429 on tree, 76 best solution, best possible 78 (257.73 seconds)
Cbc0010I After 781 nodes, 435 on tree, 76 best solution, best possible 78 (258.51 seconds)
Cbc0010I After 787 nodes, 438 on tree, 76 best solution, best possible 78 (259.23 seconds)
Cbc0010I After 795 nodes, 442 on tree, 76 best solution, best possible 78 (260.22 seconds)
Cbc0010I After 804 nodes, 446 on tree, 76 best solution, best possible 78 (260.93 seconds)
Cbc0010I After 809 nodes, 449 on tree, 76 best solution, best possible 78 (261.63 seconds)
Cbc0010I After 815 nodes, 452 on tree, 76 best solution, best possible 78 (262.39 seconds)
Cbc0010I After 819 nodes, 453 on tree, 76 best solution, best possible 78 (263.15 seconds)
Cbc0010I After 827 nodes, 458 on tree, 76 best solution, best possible 78 (264.15 seconds)
Cbc0010I After 835 nodes, 464 on tree, 76 best solution, best possible 78 (265.04 seconds)
Cbc0010I After 841 nodes, 467 on tree, 76 best solution, best possible 78 (265.76 seconds)
Cbc0010I After 845 nodes, 469 on tree, 76 best solution, best possible 78 (266.52 seconds)
Cbc0010I After 851 nodes, 472 on tree, 76 best solution, best possible 78 (267.30 seconds)
Cbc0010I After 858 nodes, 477 on tree, 76 best solution, best possible 78 (268.00 seconds)
Cbc0010I After 863 nodes, 481 on tree, 76 best solution, best possible 78 (268.81 seconds)
Cbc0010I After 869 nodes, 483 on tree, 76 best solution, best possible 78 (269.55 seconds)
Cbc0010I After 871 nodes, 484 on tree, 76 best solution, best possible 78 (270.28 seconds)
Cbc0010I After 877 nodes, 488 on tree, 76 best solution, best possible 78 (270.99 seconds)
Cbc0010I After 886 nodes, 493 on tree, 76 best solution, best possible 78 (272.02 seconds)
Cbc0010I After 891 nodes, 496 on tree, 76 best solution, best possible 78 (272.88 seconds)
Cbc0010I After 897 nodes, 500 on tree, 76 best solution, best possible 78 (273.79 seconds)
Cbc0010I After 904 nodes, 503 on tree, 76 best solution, best possible 78 (274.56 seconds)
Cbc0010I After 907 nodes, 503 on tree, 76 best solution, best possible 78 (275.37 seconds)
Cbc0010I After 913 nodes, 505 on tree, 76 best solution, best possible 78 (276.07 seconds)
Cbc0010I After 922 nodes, 510 on tree, 76 best solution, best possible 78 (276.82 seconds)
Cbc0010I After 926 nodes, 511 on tree, 76 best solution, best possible 78 (277.82 seconds)
Cbc0010I After 930 nodes, 513 on tree, 76 best solution, best possible 78 (278.53 seconds)
Cbc0010I After 937 nodes, 515 on tree, 76 best solution, best possible 78 (279.34 seconds)
Cbc0010I After 943 nodes, 519 on tree, 76 best solution, best possible 78 (280.21 seconds)
Cbc0004I Integer solution of 78 found after 711006 iterations and 937 nodes (280.60 seconds)
Cbc0012I Integer solution of 78 found by heuristic after 718472 iterations and 944 nodes (280.60 seconds)
Cbc0004I Integer solution of 78 found after 718822 iterations and 944 nodes (282.52 seconds)
Cbc0030I Thread 0 used 56 times, waiting to start 0.73805904, 285 locks, 0.021552563 locked, 0.0001168251 waiting for locks
Cbc0030I Thread 1 used 51 times, waiting to start 3.5307941, 262 locks, 0.01808691 locked, 7.8201294e-05 waiting for locks
Cbc0030I Thread 2 used 51 times, waiting to start 7.1101875, 262 locks, 0.019477129 locked, 0.00023293495 waiting for locks
Cbc0030I Thre
<OptimizationStatus.OPTIMAL: 0>
if model.status == OptimizationStatus.OPTIMAL:
model.write("data/pism/nurse-scheduling.lp")
shift_satisfaction["val"] = shift_satisfaction["var"].astype(float)
not_satisfied = shift_satisfaction[
shift_satisfaction["val"] < 1
].sort_values(["staff", "day", "shift"])[["staff", "day", "shift", "val"]]
# シフト希望 "*", "x"は候補の中で1つ希望が叶えばよい
dups = not_satisfied[
not_satisfied.duplicated(keep=False, subset=["day", "staff"])
].sort_values(["staff", "day", "shift"])[["staff", "day", "shift"]]
print("'x', '*' シフト")
display(dups)
non_dups = (
pd.merge(
not_satisfied,
dups,
on=["staff", "day", "shift"],
how="outer",
indicator=True,
)
.query('_merge != "both"')
.sort_values(["staff", "day", "shift"])[["staff", "day", "shift"]]
)
print("希望か叶わなかったシフト")
display(non_dups)
print(
"シフトの実現度: {}%".format(
int(
100
* model.objective_value
/ (shift_satisfaction.shape[0] - dups.shape[0])
)
)
)
shift_table["val"] = shift_table["var"].astype(float).round().astype(int)
answer = shift_table[shift_table["val"] > 0.5]
pivot = answer.pivot(
columns="day", index="staff", values="shift"
).reset_index()
def highlight_not_satisfied(row, target, props):
staff = row.name
style = [
(
props
if any(t[0] == staff and t[1] == day for t in target)
else ""
)
for day, shift in row.items()
]
return style
styled = pivot.style.apply(
highlight_not_satisfied,
target=non_dups.to_numpy(),
props="background-color: #ffff00; color: #ff0000; font-weight: bold;",
axis=1,
)
def add_div(func):
def wrapper(*args, **kwargs):
return '<div class="dataframe">{}</div>'.format(
func(*args, **kwargs)
)
return wrapper
styled.to_html = add_div(styled.to_html)
display(styled)
else:
print(model.status)
'x', '*' シフト
| staff | day | shift | |
|---|---|---|---|
| 86 | 1 | 15 | + |
| 83 | 1 | 15 | - |
| 85 | 1 | 15 | / |
| 90 | 1 | 29 | + |
| 89 | 1 | 29 | / |
| 88 | 1 | 29 | n |
| 94 | 7 | 24 | + |
| 91 | 7 | 24 | N |
| 92 | 7 | 24 | n |
| 98 | 22 | 23 | + |
| 95 | 22 | 23 | N |
| 96 | 22 | 23 | n |
希望か叶わなかったシフト
| staff | day | shift | |
|---|---|---|---|
| 6 | 2 | 2 | / |
| 7 | 2 | 3 | / |
| 11 | 8 | 23 | / |
| 12 | 15 | 23 | / |
| 16 | 26 | 8 | / |
シフトの実現度: 93%
| day | staff | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | n | / | / | / | N | n | / | - | - | N | n | + | - | / | - | - | - | N | n | / | - | - | N | n | / | - | / | N | n | / |
| 1 | 1 | / | N | n | + | - | / | N | n | + | - | - | - | / | - | N | n | + | - | / | N | n | / | / | / | - | - | / | / | - | - |
| 2 | 2 | N | n | + | - | / | N | n | / | - | - | N | n | / | / | - | / | / | - | N | n | / | - | - | - | N | n | / | - | - | / |
| 3 | 3 | / | - | - | - | / | - | - | N | n | + | - | / | - | N | n | / | / | / | - | / | - | N | n | + | / | - | - | / | N | n |
| 4 | 4 | - | + | - | - | - | / | - | - | N | n | / | - | / | - | - | N | n | / | - | - | N | n | / | / | - | N | n | / | / | / |
| 5 | 5 | / | + | - | N | n | / | - | - | / | / | / | - | N | n | / | - | - | - | / | - | N | n | + | - | - | / | N | n | / | - |
| 6 | 6 | - | - | N | n | / | - | + | - | / | / | / | N | n | / | / | - | N | n | / | - | / | - | - | N | n | / | - | - | / | N |
| 7 | 7 | - | - | N | n | / | + | / | + | + | - | N | n | / | - | / | + | - | N | n | / | - | - | / | / | / | N | n | / | - | - |
| 8 | 8 | - | / | / | / | - | - | - | / | - | N | n | + | - | / | N | n | + | / | - | - | / | N | n | + | / | / | - | - | N | n |
| 9 | 9 | / | N | n | + | - | - | / | N | n | + | - | - | / | - | - | / | / | - | - | N | n | / | - | - | / | - | N | n | / | / |
| 10 | 10 | / | - | - | N | n | / | - | - | N | n | / | + | - | N | n | / | / | / | - | - | / | - | - | N | n | / | / | - | N | n |
| 11 | 11 | - | / | / | / | - | - | - | N | n | + | / | - | - | - | / | N | n | / | / | - | N | n | + | - | - | / | N | n | / | - |
| 12 | 12 | / | N | n | + | / | - | N | n | / | / | - | - | N | n | / | - | - | - | N | n | / | / | - | N | n | / | - | - | / | - |
| 13 | 13 | / | + | - | - | - | N | n | / | / | / | - | N | n | / | / | - | - | N | n | / | - | / | - | - | N | n | / | - | - | N |
| 14 | 14 | n | / | / | / | N | n | + | - | - | - | / | N | n | / | - | - | N | n | / | / | - | - | N | n | / | - | - | N | n | / |
| 15 | 15 | N | n | + | - | / | N | n | / | - | - | N | n | / | - | - | / | / | - | - | / | / | N | n | + | - | - | - | / | - | / |
| 16 | 16 | - | - | N | n | / | - | / | - | - | N | n | + | / | - | N | n | + | / | - | N | n | / | / | / | - | N | n | / | - | / |
| 17 | 17 | / | - | - | - | N | n | / | / | / | / | - | - | - | + | / | - | N | n | / | - | - | - | N | n | / | - | - | N | n | / |
| 18 | 18 | - | / | / | / | - | - | - | / | - | - | - | + | / | + | - | + | - | - | - | / | - | / | + | - | - | - | / | - | - | - |
| 19 | 19 | - | - | N | n | / | / | - | N | n | + | - | / | N | n | / | / | / | - | - | / | - | N | n | + | - | / | - | - | / | N |
| 20 | 20 | N | n | + | - | / | - | N | n | / | / | - | N | n | / | - | - | N | n | / | - | - | / | - | - | / | N | n | / | / | - |
| 21 | 21 | - | + | - | N | n | / | - | - | / | / | - | - | N | n | / | - | - | N | n | / | / | - | N | n | / | - | / | N | n | / |
| 22 | 22 | / | N | n | + | - | - | + | / | - | N | n | / | - | - | N | n | + | - | / | - | N | n | / | / | - | - | / | / | - | / |
| 23 | 23 | - | - | - | N | n | / | + | - | N | n | / | / | - | N | n | + | - | / | - | N | n | / | / | / | - | - | N | n | / | / |
| 24 | 24 | n | / | / | / | - | N | n | / | - | - | N | n | / | - | - | N | n | / | - | - | / | / | - | N | n | / | - | - | N | n |
| 25 | 25 | / | - | - | - | N | n | + | / | - | - | / | - | - | N | n | / | / | / | N | n | / | - | + | - | N | n | / | / | - | - |
| 26 | 26 | n | / | / | / | - | - | N | n | + | - | / | + | - | / | / | - | - | - | N | n | + | / | - | - | N | n | / | / | - | N |
| 27 | 27 | N | n | + | - | / | - | - | - | N | n | / | - | / | - | - | N | n | / | - | / | - | - | / | / | / | - | - | - | / | - |
夜勤のシフトをうまくスケジュールできていない。
(続く)
データの出典
- 池上 敦子. ナース・スケジューリング--調査・モデル化・アルゴリズム. 統計数理 = Proceedings of the Institute of Statistical Mathematics. 53(2) (通号 102) 2005,p.231～259.