# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install pulp matplotlib

# ライブラリ読み込み
import math
import pulp                     # モデル作成
import matplotlib.pyplot as plt # 可視化

# ダミーデータ作成(p-center 問題入門と同じ地域)
coords_fac = [(0, 0), (10, 0), (0, 10), (10, 10)]  # 候補点座標
coords_dem = [(2, 1), (3, 7), (6, 2), (7, 8), (1, 9), (9, 1), (5, 5), (8, 4)]  # 需要点座標

I = range(len(coords_fac))  # 候補点集合
J = range(len(coords_dem))  # 需要点集合
D = 8.5  # 被覆距離

print(f"候補点数: {len(I)}, 需要点数: {len(J)}, 被覆距離: {D}")

候補点数: 4, 需要点数: 8, 被覆距離: 8.5

# 距離行列と被覆関係の計算
dist = [[math.dist(coords_fac[i], coords_dem[j]) for j in J] for i in I]

# N_j: 需要点j をカバーできる候補点の集合
N = {j: [i for i in I if dist[i][j] <= D] for j in J}
for j in J:
    print(f"需要点{j} をカバーできる候補点: {N[j]}")

需要点0 をカバーできる候補点: [0, 1]
需要点1 をカバーできる候補点: [0, 2, 3]
需要点2 をカバーできる候補点: [0, 1]
需要点3 をカバーできる候補点: [2, 3]
需要点4 をカバーできる候補点: [2]
需要点5 をカバーできる候補点: [1]
需要点6 をカバーできる候補点: [0, 1, 2, 3]
需要点7 をカバーできる候補点: [1, 3]

# モデル宣言
prob = pulp.LpProblem("LSCP", pulp.LpMinimize)

# 変数
x = pulp.LpVariable.dicts('x', I, cat='Binary')

# 目的関数: 施設数の最小化
prob += pulp.lpSum(x[i] for i in I)

# 制約: すべての需要点が少なくとも1つの施設にカバーされる
for j in J:
    prob += pulp.lpSum(x[i] for i in N[j]) >= 1

print(prob)

LSCP:
MINIMIZE
1*x_0 + 1*x_1 + 1*x_2 + 1*x_3 + 0.0
SUBJECT TO
_C1: x_0 + x_1 >= 1

_C2: x_0 + x_2 + x_3 >= 1

_C3: x_0 + x_1 >= 1

_C4: x_2 + x_3 >= 1

_C5: x_2 >= 1

_C6: x_1 >= 1

_C7: x_0 + x_1 + x_2 + x_3 >= 1

_C8: x_1 + x_3 >= 1

VARIABLES
0 <= x_0 <= 1 Integer
0 <= x_1 <= 1 Integer
0 <= x_2 <= 1 Integer
0 <= x_3 <= 1 Integer

# CBC ソルバーで解く
prob.solve(pulp.PULP_CBC_CMD(msg=1))
print("求解結果:", pulp.LpStatus[prob.status])
print(f"最小施設数 z* = {int(pulp.value(prob.objective))}")

# 開設した施設
open_sites = [i for i in I if pulp.value(x[i]) > 0.5]
print("開設候補点番号:", open_sites)

Welcome to the CBC MILP Solver 
Version: 2.10.10 
Build Date: Sep 26 2023 

command line - cbc /tmp/2393882d361d414d9abc85475c92d16d-pulp.mps -timeMode elapsed -branch -printingOptions all -solution /tmp/2393882d361d414d9abc85475c92d16d-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 13 COLUMNS
At line 43 RHS
At line 52 BOUNDS
At line 57 ENDATA
Problem MODEL has 8 rows, 4 columns and 17 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 2 - 0.00 seconds
Cgl0004I processed model has 0 rows, 0 columns (0 integer (0 of which binary)) and 0 elements
Cbc3007W No integer variables - nothing to do
Cuts at root node changed objective from 2 to -1.79769e+308
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                2.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.01

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.02

求解結果: Optimal
最小施設数 z* = 2
開設候補点番号: [1, 2]

# 結果の可視化: 開設施設を赤、被覆範囲を円で示す
plt.figure(figsize=(8, 8))

# 被覆範囲の円
ax = plt.gca()
for i in open_sites:
    circle = plt.Circle(coords_fac[i], D, fill=True, alpha=0.1, color='red')
    ax.add_patch(circle)
    circle = plt.Circle(coords_fac[i], D, fill=False, color='red', linestyle='--')
    ax.add_patch(circle)

# 候補点(灰)、開設施設(赤)、需要点(青)
for i in I:
    c = 'red' if i in open_sites else 'gray'
    plt.scatter(*coords_fac[i], c=c, s=120, marker='s', zorder=3)
    plt.text(coords_fac[i][0] + 0.2, coords_fac[i][1] + 0.2, f'cand{i}', fontsize=9)
for j in J:
    plt.scatter(*coords_dem[j], c='tab:blue', s=60, zorder=3)
    plt.text(coords_dem[j][0] + 0.2, coords_dem[j][1] + 0.2, f'dem{j}', fontsize=9)

plt.axis('equal')
plt.grid(True, alpha=0.3)
plt.title(f'LSCP solution (D = {D})')
plt.show()

# 被覆距離を小さくした場合(実行不能の例)
D2 = 7.0
N2 = {j: [i for i in I if dist[i][j] <= D2] for j in J}
print("カバーできる候補点が存在しない需要点:", [j for j in J if not N2[j]])

prob2 = pulp.LpProblem("LSCP_small_D", pulp.LpMinimize)
x2 = pulp.LpVariable.dicts('x', I, cat='Binary')
prob2 += pulp.lpSum(x2[i] for i in I)
for j in J:
    prob2 += pulp.lpSum(x2[i] for i in N2[j]) >= 1
prob2.solve(pulp.PULP_CBC_CMD(msg=0))
print("求解結果:", pulp.LpStatus[prob2.status])

カバーできる候補点が存在しない需要点: [6]
求解結果: Infeasible

名前	説明
$I$	候補点の集合(この例では4か所)
$J$	需要点の集合(この例では8か所)
$d_{ij}$	候補点 $i$ から需要点 $j$ までの距離
$D$	被覆距離(この例では8.5 km)
$N_j$	需要点 $j$ をカバーできる候補点の集合、すなわち $N_j = \{i \in I : d_{ij} \leq D\}$
$x_i$	候補点 $i$ に施設を建てるなら1、そうでなければ0

候補者ID	配達可能エリア(ID)	配達コスト
1	1, 2, 3	200
2	1, 4, 6	280
3	2, 5	175
4	3, 4, 5, 6, 7	560
5	1, 6	205
6	2, 4, 6	245
7	4	80
8	3, 7	195
9	3, 6, 7	265
10	2, 5, 7	190

集合被覆問題(LSCP)入門¶

1. はじめに¶

2. 前提知識と学習目標¶

学習目標¶

3. 問題設定と定式化¶

3.1 問題の具体例¶

3.2 数学的な定式化¶

3.2.1 定数および決定変数の定義¶

3.2.2 数理モデル¶

3.2.3 目的関数の意味¶

3.2.4 制約条件の意味¶

4. Python + PuLP による実装¶

4.1 準備¶

4.2 モデル構築¶

4.3 求解および結果の解釈¶

4.4 可視化¶

5. 発展: 道路ネットワーク上の休憩施設配置(RALP)¶

5.1 動く需要への拡張¶

5.2 RALP の定式化¶

5.3 さらに先へ: 時間軸の導入(RALMTD)¶

6. 課題¶

7. 注意事項¶

7.1 自分で問題を作る場合には¶

7.2 定式化が理解できないときは¶

8. 卒業研究概要への手引き¶

1章はじめに(文章量の比率: 15%)¶

2章集合被覆問題(文章量の比率: 30%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶

参考文献¶

集合被覆問題(LSCP)入門¶

1. はじめに¶

2. 前提知識と学習目標¶

学習目標¶

3. 問題設定と定式化¶

3.1 問題の具体例¶

3.2 数学的な定式化¶

3.2.1 定数および決定変数の定義¶

3.2.2 数理モデル¶

3.2.3 目的関数の意味¶

3.2.4 制約条件の意味¶

4. Python + PuLP による実装¶

4.1 準備¶

4.2 モデル構築¶

4.3 求解および結果の解釈¶

4.4 可視化¶

5. 発展: 道路ネットワーク上の休憩施設配置(RALP)¶

5.1 動く需要への拡張¶

5.2 RALP の定式化¶

5.3 さらに先へ: 時間軸の導入(RALMTD)¶

6. 課題¶

7. 注意事項¶

7.1 自分で問題を作る場合には¶

7.2 定式化が理解できないときは¶

8. 卒業研究概要への手引き¶

1章 はじめに(文章量の比率: 15%)¶

2章 集合被覆問題(文章量の比率: 30%)¶

3章 実験(文章量の比率: 40%)¶

3.1節 概要¶

3.2節 結果と考察¶

4章 おわりに(文章量の比率: 15%)¶

参考文献¶

1章はじめに(文章量の比率: 15%)¶

2章集合被覆問題(文章量の比率: 30%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶