[OR-Tools 스터디] Maximum Flows

따르는 섹션에서는, maximum flow(max flow) 문제의 예시를 보여준다.

 

A max flow example

이 문제는 아래 그래프에 의해 정의되는데, 이는 transportation network를 표현한다.

 

우리는 노드 0(source)에서 노드 4(sink)로 material을 수송하길 원한다. 

호 옆에 있는 숫자들은 그들의 capacity를 나타낸다. - 호의 capacity는 고정된 시간 안에 이를 가로질러서 수송할 수 있는 최대 양을 의미한다. 

capacity들은 문제에서 constraint들이다. 

 

flow는 따르는 flow conservation rule을 만족시키는 각 호에 양수를 부여하는 것이다.

 

최대 flow 문제는 전체 네트워크의 흐름의 양의 합이 가능한 크도록 하는 흐름을 찾는 것이다. 

 

따르는 섹션에서는 source (0)에서 sink (4)까지의 최대 흐름을 찾는 프로그램을 보여준다.

 

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

def MaximumFlows():
    #여기서는 SimpleMaxFlow solver를 사용함
    smf = max_flow.SimpleMaxFlow()

    #define the data
    #시작 노드, 마지막 노드, 호의 capacity로 3개의 배열로 문제의 그래프를 정의할 수 있다.
    #각 i에 대해 i번째 호는 start_nodes[i]에서 end_nodes[i]로 가게되며, 이것의 capacity는 capacities[i]에 의해 주어진다.
    #다음 섹션에서는 이 데이터들을 사용하여 호를 어떻게 만들 것인지를 보여준다.

    start_nodes = np.array([0,0,0,1,1,2,2,3,3])
    end_nodes = np.array([1,2,3,2,4,3,4,2,4])
    capacities = np.array([20,30,10,40,30,10,20,5,20])

    #add the arcs
    #각 시작 노드와 마지막 노드에 대해, AddArcWithCapacity 메소드를 사용하여 주어진 capacity로 시작 노드에서 마지막 노드로의 호를 만든다.
    all_arcs = smf.add_arcs_with_capacity(start_nodes, end_nodes, capacities)

    #invoke the solver
    #모든 호들이 정의되었으며, solver 호출과 결과 출력만 남았다.
    #Solve()method로 호출할 것이며, 이때 source(0)과 sink(4)를 제공해준다.
    #즉, 노드0과 노드4 사이의 최대 흐름을 찾는다.
    status = smf.solve(0, 4)

    if status != smf.OPTIMAL:
        print('There was an issue with the max flow input.')
        print(f'Status: {status}')
        exit(1)
    print('Max flow:', smf.optimal_flow())
    print('')
    print(' Arc     Flow/Capacity')
    solution_flows = smf.flows(all_arcs)
    for arc, flow, capacity in zip(all_arcs, solution_flows, capacities):
        print(f'{smf.tail(arc)} / {smf.head(arc)}   {flow:3}  / {capacity:3}')
    print('Source side min-cut:', smf.get_source_side_min_cut())
    print('Sink side min-cut:', smf.get_sink_side_min_cut())

MaximumFlows()

 

Reference : 

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

최대 흐름  |  OR-Tools  |  Google Developers