netflow example

AJONA·2020년 9월 23일
0

gurobi

목록 보기
4/4
post-thumbnail

Problem

네트워크 flow 문제를 풀어본다
문제는 정의는 아래와 같음

Commodities
Pencils, Pens

Nodes
Detroit, Denver, Boston, New York, Seattle

Arc capacity
Detroit -> Boston : 100
Detroit -> New York : 80
Detroit -> Seattle : 120
Denver -> Boston : 120
Denver -> New York : 120
Denver -> Seattle : 120

Cost

  • Pencils
    Detroit -> Boston : 10
    Detroit -> New York : 20
    Detroit -> Seattle : 60
    Denver -> Boston : 40
    Denver -> New York : 40
    Denver -> Seattle : 30
  • Pens
    Detroit -> Boston : 20
    Detroit -> New York : 20
    Detroit -> Seattle : 80
    Denver -> Boston : 60
    Denver -> New York : 70
    Denver -> Seattle : 30

Demand

  • Pencils
    Detroit: 50
    Denver: 60
    Boston: -50
    New York: -50
    Seattle: -10
  • Pens
    Detroit: 60
    Denver: 40
    Boston: -40
    New York: -30
    Seattle: -30

정리하면,
두개의 상품(Comodities)을 총 5개의 도시(Nodes)에서 이송할꺼임
도시간에 상품을 이송하는데 최대량이 있음(Arc capacity)
운송 단위당 드는 비용(Cost)이 있음
요구되는 양을 맞춰야 함(Demand) -> 생산지는 양수로 수요지는 음수로 표기

Solution

import gurobipy as gp
from gurobipy import GRB

# Commidities & Nodes
commodities = ["Pencils", "Pens"]
nodes = ["Detroit", "Denver", "Boston", "New York", "Seattle"]

# Multidict class를 이용하여 arcs capacity 선언
arcs, capacity = gp.multidict(
    {
        ("Detroit", "Boston"): 100,
        ("Detroit", "New York"): 80,
        ("Detroit", "Seattle"): 120,
        ("Denver", "Boston"): 120,
        ("Denver", "New York"): 120,
        ("Denver", "Seattle"): 120,
    }
)

# Cost
cost = {
    ("Pencils", "Detroit", "Boston"): 10,
    ("Pencils", "Detroit", "New York"): 20,
    ("Pencils", "Detroit", "Seattle"): 60,
    ("Pencils", "Denver", "Boston"): 40,
    ("Pencils", "Denver", "New York"): 40,
    ("Pencils", "Denver", "Seattle"): 30,
    ("Pens", "Detroit", "Boston"): 20,
    ("Pens", "Detroit", "New York"): 20,
    ("Pens", "Detroit", "Seattle"): 80,
    ("Pens", "Denver", "Boston"): 60,
    ("Pens", "Denver", "New York"): 70,
    ("Pens", "Denver", "Seattle"): 30,
}

# Demand for pairs of commodity-city
inflow = {
    ("Pencils", "Detroit"): 50,
    ("Pencils", "Denver"): 60,
    ("Pencils", "Boston"): -50,
    ("Pencils", "New York"): -50,
    ("Pencils", "Seattle"): -10,
    ("Pens", "Detroit"): 60,
    ("Pens", "Denver"): 40,
    ("Pens", "Boston"): -40,
    ("Pens", "New York"): -30,
    ("Pens", "Seattle"): -30,
}


model = gp.Model("netflow")

flow = model.addVars(commodities, arcs, obj=cost, name="flow")

model.addConstrs((flow.sum("*", i, j) <= capacity[i, j] for i, j in arcs), "cap")

model.addConstrs(
    (flow.sum(h, "*", j) + inflow[h, j] == flow.sum(h, j, "*") for h in commodities for j in nodes),
    "nodes",
)

model.optimize()

addVars()

.addVars()를 이용해서 변수 선언.
flow = model.addVars(commodities, arcs, obj=cost, name="flow")의 경우, flow 라는 이름을 가지면서 cost를 coefficient로 가지게 됨.
ex) flow['Pencils', 'Detroit', Boston'] 이런식..

Constraints

Arc capacity

model.addConstrs((flow.sum("*", i, j) <= capacity[i, j] for i, j in arcs), "cap")
flow에서 i -> j로 가는 모든 Commodity(*)의 합은 i -> j arc의 capacity보다 작아야 함을 의미

Flow conservation

model.addConstrs((flow.sum(h, "*", j) + inflow[h, j] == flow.sum(h, j, "*") for h in commodities for j in nodes), "nodes")

flow에서 각 Commodity(h) 당 j로 부터 향하는 다른 Node(*)의 합 + 해당 노드에서 commodity의 수요 == flow에서 각 Commodity(h) 당 j로 부터 향하는 다른 Node(*)의 합

즉 수요 제약을 만족해야함 의미
ex) Boston을 향하는 모든 pencils의 합 + Boston의 pencils의 수요 == 0 (Boston에서 나가는게 없으니)

model.optimize()

print()
if model.status == GRB.OPTIMAL:
    solution = model.getAttr("x", flow)
    for h in commodities:
        print(h)
        for i, j in arcs:
            if solution[h, i, j] > 0:
                print(" ", i, j, solution[h, i, j])

최적화하고 정답을 출력하면 아래와 같은 결과를 얻는다

Optimize a model with 16 rows, 12 columns and 36 nonzeros
Model fingerprint: 0xc43e5943
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+01, 8e+01]
Bounds range [0e+00, 0e+00]
RHS range [1e+01, 1e+02]
Presolve removed 16 rows and 12 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Iteration Objective Primal Inf. Dual Inf. Time
0 5.5000000e+03 0.000000e+00 2.000000e+01 0s
Extra one simplex iteration after uncrush
1 5.5000000e+03 0.000000e+00 0.000000e+00 0s

Solved in 1 iterations and 0.00 seconds
Optimal objective 5.500000000e+03

Pencils
Detroit Boston 50.0
Denver New York 50.0
Denver Seattle 10.0
Pens
Detroit Boston 30.0
Detroit New York 30.0
Denver Boston 10.0
Denver Seattle 30.0

Reference

netflow.py

profile
Brush My Teeth

0개의 댓글