[OR-Tools 스터디] Minimum Cost Flows

max flow problem과 밀접하게 관련되어있는 것이 minimum cost(min cost) flow problem이다. 

이는 그래프 상의 각 호가 그것들을 가로질러서 수송되는 material에 대한 단위 비용을 가진다. 

이 문제는 최소 전체 비용의 흐름을 찾기 위한 것이다.

 

min cost flow problem은 또한 특별한 노드들을 가지고 있는데, 이 노드는 공급 노드 혹은 수요 노드라고 불린다. 

이들은 max flow problem에서 source와 sink와 유사하다.

material은 공급 노드에서 수요 노드로 수송된다. 

• 공급 노드에서, 양수의 양인 공급은 flow에 추가하는 것이다. 예로, 공급은 노드의 생산을 표현할 수 있다. 
• 수요 노드에서, 음수의 양인 수요는 flow에서 제외된다. 예로, 수요는 노드에서 소비를 표현할 수 있다. 

편의상, 우리는 공급 혹은 수요 노드말고 모든 노드들이 0의 공급(즉, 공급이 없는 것)을 가진다고 가정하자.

 

아래의 그래프는 min cost flow 문제를 보여준다. 호들은 숫자의 쌍이 적혀있다 : 첫번째 숫자는 capacity이고 두번째 숫자는 비용을 의미한다.

노드 옆에 있는 괄호 안 숫자는 공급 혹은 수요들을 표현한다. 노드 0은 공급이 20인 공급 노드를 의미하며, 노드 3과 4는 수요 노드들로, 이들은 수요 -5와 -15를 가지고 있다. 

 

 

import numpy as np
from ortools.graph.python import min_cost_flow

def MinimumCostFlow():
    #declare the solver
    #이 문제를 풀기 위해, SimpleMinCostFlow solver를 사용한다.
    smcf = min_cost_flow.SimpleMinCostFlow()

    #define the data
    #문제에 대한 데이터를 정의하는 부분. 여기서는 시작 노드, 끝나는 노드, capacity, 그리고 단위 비용들에 대한 총 4가지 배열들이 존재한다.
    #다시, 배열들의 길이는 그래프에서 호들의 수이다.
    start_nodes = np.array([0,0,1,1,1,2,2,3,4])
    end_nodes = np.array([1,2,2,3,4,3,4,4,2])
    capacities = np.array([15,8,20,4,10,15,4,20,5])
    unit_costs = np.array([4,4,2,2,6,1,3,2,3])

    #각 노드에 해당하는 공급들의 배열
    supplies = [20, 0, 0, -5, -15]

    #Add the arcs
    #각 시작 노드와 끝나는 노드들에 대해, 우리는 AddArcWithCapacityAndUnitCost 메소드를 사용하여 주어진 capacity와 단위 비용으로 시작 노드와 끝나는 노드까지의 호를 만든다.
    #solver의 SetNodeSupply 메소드는 노드들에 대해 공급의 벡터를 생성해준다.
    #Add arcs, capacities and costs in bulk using numpy
    all_arcs = smcf.add_arcs_with_capacity_and_unit_cost(
        start_nodes, end_nodes, capacities, unit_costs
    )

    #add supply for each nodes
    smcf.set_nodes_supply(np.arange(0, len(supplies)), supplies)

    #invoke the solver
    #모든 호들은 정의가 되었고, 남은 것들은 solver를 invoke하는 것과 결과를 출력하는 것이다.
    #find the min cost flow
    status = smcf.solve()

    if status != smcf.OPTIMAL:
        print('There was a issue with the min cost flow input.')
        print(f'Status: {status}')
        exit(1)
    print(f'Minimum cost : {smcf.optimal_cost()}')
    print('')
    print(' Arc      Flow / Capacity Cost')
    solution_flows = smcf.flows(all_arcs)
    costs = solution_flows * unit_costs
    for arc, flow, cost in zip(all_arcs, solution_flows, costs):
        print(
            f'{smcf.tail(arc):1} -> {smcf.head(arc)}   {flow:3}     /{smcf.capacity(arc) : 3}     {cost}'
        )
MinimumCostFlow()

 

Reference:

https://developers.google.com/optimization/flow/mincostflow

최소 비용 흐름  |  OR-Tools  |  Google Developers