OR Tools 이용해서 1D Bin Packing Problem 풀어보기

빈 포장 문제(Bin Packing Problem)란 n개의 아이템(Item)을 m개의 빈(상자)에 효과적으로 채워 넣는 문제입니다.

이 문제의 목적은 주어진 아이템들을 가능한 한 적은 수의 빈에 담아 최대한 효율적으로 공간을 활용하는 것입니다.

각 아이템은 특정한 무게 정보를 가지고 있으며, 각 빈은 허용 가능한 최대 무게를 가지고 있습니다.

빈 포장 문제에서는 아이템의 총 무게가 빈의 최대 무게를 초과하지 않도록 하는 것이 중요한 제약 조건입니다.

이 문제는 여러 분야에서 발생할 수 있는 자원 할당 문제의 한 유형으로, 물류, 제조, 컴퓨터 과학 등 다양한 응용 분야에 적용됩니다.

빈 포장 문제는 유사한 문제인 배낭 문제(Knapsack Problem)와 비교할 수 있습니다.

배낭 문제는 1개의 배낭에 최대의 이익을 얻기 위해 아이템을 선정하는 문제인 반면, 빈 포장 문제는 사용 가능한 빈이 여러 개인 점에서 차이가 있습니다.

Solver 설정

solver = pywraplp.Solver.CreateSolver('SCIP')
Python
복사

MIP(혼합 정수 프로그래밍)를 위해 기본적으로 제공되는 SCIP 이용하여 생성합니다.

Decision variable 설정

X = [[solver.IntVar(0, 1, '') for j in range(num_bins)] for i in range(num_items)]

# X[i][j] = 1 if item i is packed in bin j.
for i in data['items']:
    for j in data['bins']:
        X[i][j] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

# Y[j] = 1 if bin j is used.
Y = [solver.IntVar(0, 1, '') for j in range(num_bins)]
for j in data['bins']:
    Y[j] = solver.IntVar(0, 1, 'y[%i]' % j)
Python
복사

의사 결정 변수 X는 0과 1의 값을 갖는 정수형(Integer) 변수로,

아이템과 빈(bin) 간의 매핑 관계를 정의하는 2차원 배열로 설정됩니다.

정수형 의사 결정 변수를 정의할 때는 solver.IntVar() 함수를 사용하여 구현할 수 있습니다.

또 다른 의사 결정 변수 Y는 역시 0과 1의 값을 갖는 정수형 변수로, 특정 빈이 사용되면 1, 사용되지 않으면 0의 값을 갖도록 설정됩니다.

Y 변수는 나중에 목적 함수에서 최소 비용을 계산할 때 빈의 사용 여부를 반영하는 데 사용됩니다.

Constraint 설정

# Each item must be in exactly one bin.
for i in data['items']:
    binSum = 0
    for j in data['bins']:
        binSum = binSum + X[i][j]
    solver.Add(binSum == 1)

# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
    binCapaSum = 0
    for i in data['items']:
        binCapaSum = binCapaSum + X[i][j] * data['weights'][i]
    solver.Add(binCapaSum <= Y[j] * data['bin_capacity'])
Python
복사

Bin Packing Problem을 해결하기 위해서는 두 가지 제약 조건(Constraint)을 정의해야 합니다.

첫 번째 제약 조건은 각 아이템이 정확히 하나의 빈(bin)에 적재되어야 한다는 것입니다.

즉, 아이템은 나누어 여러 빈에 넣을 수 없으며, 반드시 하나의 빈에만 할당되어야 합니다.

두 번째 제약 조건은 각 빈의 용량(Capacity)을 초과하는 적재가 허용되지 않는다는 것입니다.

각 빈에는 허용 가능한 최대 무게가 설정되어 있으며, 빈에 적재된 아이템들의 무게 합이 이 최대 용량을 초과하지 않도록 제약이 설정됩니다.

이 두 제약 조건을 통해 빈에 적재되는 아이템의 무게를 고려하여 최적의 배치를 찾을 수 있습니다.

Objective Function 설정

costSum = 0
for j in data['bins']:
    costSum = costSum + Y[j]

# Objective: minimize the number of bins used.
solver.Minimize(costSum)
Python
복사

모든 아이템을 빈(bin)에 적재하면서 사용되는 빈의 수를 최소화해야 하므로,

목적 함수(Objective Function)는 사용되는 빈의 개수를 비용(cost)으로 정의하고, 이 비용을 최소화하는 것을 목표로 설정합니다.

최소화를 정의하기 위해서는 solver.Minimize() 함수를 사용하여 구현할 수 있습니다.

전체 프로그램 소스

from ortools.linear_solver import pywraplp

def main():
    data = makeInput()
    solver = pywraplp.Solver.CreateSolver('SCIP')

    num_items = len(data['items'])
    num_bins = len(data['bins'])

    X = [[solver.IntVar(0, 1, '') for j in range(num_bins)] for i in range(num_items)]

    # Variables
    # X[i][j] = 1 if item i is packed in bin j.
    for i in data['items']:
        for j in data['bins']:
            X[i][j] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

    # Y[j] = 1 if bin j is used.
    Y = [solver.IntVar(0, 1, '') for j in range(num_bins)]
    for j in data['bins']:
        Y[j] = solver.IntVar(0, 1, 'y[%i]' % j)

    # Constraints
    # Each item must be in exactly one bin.
    for i in data['items']:
        binSum = 0
        for j in data['bins']:
            binSum = binSum + X[i][j]
        solver.Add(binSum == 1)

    # The amount packed in each bin cannot exceed its capacity.
    for j in data['bins']:
        binCapaSum = 0
        for i in data['items']:
            binCapaSum = binCapaSum + X[i][j] * data['weights'][i]
        solver.Add(binCapaSum <= Y[j] * data['bin_capacity'])

    costSum = 0
    for j in data['bins']:
        costSum = costSum + Y[j]

    # Objective: minimize the number of bins used.
    solver.Minimize(costSum)

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        num_bins = 0
        for j in data['bins']:
            if Y[j].solution_value() == 1:
                bin_items = []
                bin_weight = 0
                for i in data['items']:
                    if X[i][j].solution_value() > 0:
                        bin_items.append(i)
                        bin_weight += data['weights'][i]
                if bin_items:
                    num_bins += 1
                    print('Bin number', j)
                    print('  Items packed:', bin_items)
                    print('  Total weight:', bin_weight)

def makeInput():
    data = {}
    weights = [500, 300, 200, 300, 300, 200, 400, 400, 200, 200, 300]
    data['weights'] = weights
    data['items'] = list(range(len(weights)))
    data['bins'] = data['items']
    data['bin_capacity'] = 1000
    return data

if __name__ == '__main__':
    main()
Python
복사

결과는 아래와 같습니다.

Bin number 0
  Items packed: [0, 1, 2]
  Total weight: 1000
Bin number 1
  Items packed: [3, 4, 5, 8]
  Total weight: 1000
Bin number 2
  Items packed: [6, 7, 9]
  Total weight: 1000
Bin number 3
  Items packed: [10]
  Total weight: 300
Python
복사

Keyword: Logistics Optimization, 물류 최적화, Linear Programming, Mixed Integer Programming, Google OR Tools

Reference:

[1] The Bin Packing Problem by Google, https://developers.google.com/optimization/pack/bin_packing, Creative Commons Attribution 4.0 License