久しぶりの「勝手に回答」シリーズ。今回はTeratailの
複数の制約があるなかでの価値最大化。(ナップサック問題応用)
です。
質問では「Pythonで」ということでしたがPythonはよく分からないので，
自分のためのJuliaのJuMPの勉強としてJulia言語で実装してみます。
幸いにしてJuMPのサイトにはナップサック問題の例があるので，
これに対してうんうん悩みながら条件を追加していきます。
実装例は次のような感じです。
もうちょっと簡単にできるのかもしれないですけど，
あまりコーディング能力がない自分が初めて書いたにしては上出来かなと思います。
using JuMP, HiGHS
価格 = Float64[5, 6, 12, 3, 4, 4, 5, 6, 5, 6, 10]
体積 = Float64[2, 2, 9, 2, 5, 4, 3, 7, 2, 4, 8]
可黄袋 = Float64[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]
可青袋 = Float64[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1]
可赤袋 = Float64[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1]
可白袋 = Float64[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
const n = length(価格)
キャパ = 10.0
model = Model(HiGHS.Optimizer)
@variable(model, x[1:n, ["黄", "青", "赤", "白"]], Bin)
@constraint(model, cキャパ, sum(体積[i] * sum(x[i, :]) for i in 1:n) ≤ キャパ)
@constraint(model, c黄[i = 1:n], x[i, "黄"] ≤ 可黄袋[i])
@constraint(model, c青[i = 1:n], x[i, "青"] ≤ 可青袋[i])
@constraint(model, c赤[i = 1:n], x[i, "赤"] ≤ 可赤袋[i])
@constraint(model, c白[i = 1:n], x[i, "白"] ≤ 可白袋[i])
@constraint(model, c袋[f = ["黄", "青", "赤", "白"]], sum(x[i, f] for i in 1:n) ≤ 1.0)
@constraint(model, c[i = 1:n], sum(x[i, :]) ≤ 1.0 )
@objective(model, Max, sum(価格[i] * sum(x[i, :]) for i in 1:n))
optimize!(model)
for i in 1:n, j in ["黄", "青", "赤", "白"]
if value(x[i, j]) > 0.5
println("$(i)番目のボール($(j)袋))")
end
end
出力結果は次の通りです。
Julia言語はあくまでラッパーで，HiGHSのSolverのお蔭といえるかもしれません。
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e+00, 9e+00]
Cost [3e+00, 1e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+01]
Presolving model
13 rows, 21 cols, 60 nonzeros 0s
6 rows, 15 cols, 43 nonzeros 0s
6 rows, 10 cols, 26 nonzeros 0s
Objective function is integral with scale 1
Solving MIP model with:
6 rows
10 cols (10 binary, 0 integer, 0 implied int., 0 continuous)
26 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 34 -inf inf 0 0 0 0 0.0s
S 0 0 0 0.00% 34 14 142.86% 0 0 0 0 0.0s
R 0 0 0 0.00% 20 19 5.26% 0 0 0 6 0.0s
40.0% inactive integer columns, restarting
Solving report
Status Optimal
Primal bound 19
Dual bound 19
Gap 0% (tolerance: 0.01%)
Solution status feasible
19 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 6 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
2番目のボール(赤袋))
4番目のボール(黄袋))
7番目のボール(青袋))
9番目のボール(白袋))
質問で示された種類とは別解がでていますが，違いは体積と価格が同じボール(白袋なので色はどうでもいい)
なので多分合っているだろうということは分かります。
条件の記述をまとめて表現出来るのはJulia言語ならではでしょうか。
