OR Tools 이용해서 Minimum Cost Flow 풀어보기

Minimum Cost Flow 문제는 플로우 네트워크를 통해 일정량의 플로우를 송신하는 가장 저렴한 방법을 찾는 최적화 문제입니다.

Minimum Cost Flow 문제에서는 공급 노드와 수요 노드라는 특수한 형태의 노드를 정의해야 합니다. 공급 노드는 물량을 공급할 수 있는 노드를 의미하고, 수요 노드는 수요를 나타내는 노드입니다.

예를 들어, 공장(Plant)과 고객(Customer) 간의 물동량을 시뮬레이션한다고 했을 때, 공장은 공급 노드로, 고객은 수요 노드로 정의할 수 있습니다.

아래 그림에서 예를 들면, 0번 노드에 표시된 15은 공급수량을 의미하며, 3번노드에 표시된 -15는 수요량를 나타냅니다. 노드와 노드를 이어주는 간선에는 Capacity와 Cost를 정의할 수 있습니다.

Solver 설정

solver = min_cost_flow.SimpleMinCostFlow()
Python
복사

OR Tools는 MIP Solver를 제공하여 MIP를 사용할 수 있지만, Minimum Cost Flow 문제를 해결할 때는 OR Tools에서 제공하는 전용 라이브러리인 min_cost_flow를 사용하는 것이 더 적합한 선택입니다.

Network 설정

    for i in range(len(start_nodes)):
        solver.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i], capacities[i], costs[i])
Python
복사

Solver 실행

status = solver.solve()
Python
복사

전체 소스

#ChatGpt로 생성한 소스입니다.
from ortools.graph.python import min_cost_flow

def solve_minimum_cost_flow_4_nodes():
    # Create the minimum cost flow solver
    solver = min_cost_flow.SimpleMinCostFlow()

    # Define the directed graph using an adjacency list
    start_nodes = [0, 0, 1, 2]
    end_nodes = [1, 2, 3, 3]
    capacities = [10, 15, 20, 10]
    costs = [5, 4, 3, 2]

    # Supply/Demand for each node
    supplies = [15, 0, 0, -15]

    # Add the edges to the solver
    for i in range(len(start_nodes)):
        solver.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i], capacities[i], costs[i])

    # Add the supplies/demands
    for i in range(len(supplies)):
        solver.set_node_supply(i, supplies[i])

    # Solve the minimum cost flow problem
    status = solver.solve()
    if status == solver.OPTIMAL:
        print('Minimum cost:', solver.optimal_cost())
        print('\n  Arc    Flow / Capacity  Cost')
        for i in range(solver.num_arcs()):
            if solver.flow(i) > 0:
                cost = solver.flow(i) * solver.unit_cost(i)
                print('%1s -> %1s    %3s  / %3s    %3s' % (
                    solver.tail(i),
                    solver.head(i),
                    solver.flow(i),
                    solver.capacity(i),
                    cost))
    else:
        print('There was an issue with the min cost flow input.')

solve_minimum_cost_flow_4_nodes()
Python
복사

결과는 아래와 같습니다.

Minimum cost: 100

  Arc    Flow / Capacity  Cost
0 -> 1      5  /  10     25
0 -> 2     10  /  15     40
1 -> 3      5  /  20     15
2 -> 3     10  /  10     20
Python
복사

Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools

Reference:

[1] Assignment as a Min cost Flow Problem by Google, https://developers.google.com/optimization/flow/mincostflow