taki["blog"] = "200 OK"

社会人3年目の日常

2018/2/12 眠

荷物が届いていたので早めに家に帰宅(ホワイト)(祝日労働だけど)。その後部屋の食べ物がなくなっていたので、買い物に行った。少しは部屋に備蓄しておきたいけど、平日に食べていくので、なかなかたまらないわけだ(ためておく場所もないけど)。

始まるまではイマイチ気にしていなかったけど、最近ウィンタースポーツを土日にやっている影響で、オリンピックが意外と楽しくなってきた。会社の食堂でも思ったけど、昼も競技してるんだね。

リハビリで家でJuliaを書いた。グラフのMSTを最適化で求める。グラフを真面目に持つのが辛かったので、適当に入力した(悪い)(書捨てプログラムに悪いとかあるのか?)。

f:id:takilog:20180212224258p:plain

# -*- coding: utf-8 -*-

using JuMP, Cbc

el = Tuple{Int64,Int64}[
    (0, 1),
    (0, 2),
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 4)
]
cicles = [
    (1, 3, 2),
    (1, 5, 6, 2),
    (3, 6, 5)
]
wlist = [2, 8, 6, 1, 3, 9]
V = 5
E = length(el)

# min. problem
m = Model(solver=CbcSolver())
@variable(m, x[1:E], Bin)

# objectives
@objective(m, Min, dot(wlist, x))

# constraints 1: cycle
for c in cicles
    c1 = zeros(E)
    for _c in c
        c1[_c] = 1
    end
    @constraint(m, dot(c1, x) <= length(c) - 1)
end

# constraint 2: # of edges
@constraint(m, dot(ones(E), x) == V - 1)

# print model
println(m)

# solve the model
status = solve(m)
println("Objective is: ", getobjectivevalue(m))
for i=1:E
    if getvalue(x[i]) > 0
        println("$(el[i])")
    end
end
Min 2 x[1] + 8 x[2] + 6 x[3] + x[4] + 3 x[5] + 9 x[6]
Subject to
 x[1] + x[2] + x[3] ≤ 2
 x[1] + x[2] + x[5] + x[6] ≤ 3
 x[3] + x[5] + x[6] ≤ 2
 x[1] + x[2] + x[3] + x[4] + x[5] + x[6] = 4
 x[i] ∈ {0,1} ∀ i ∈ {1,2,…,5,6}

Objective is: 12.0
(0, 1)
(1, 2)
(1, 3)
(1, 4)