[OR-Tools 스터디] The Bin Packing Problem

multiple knapsack 문제와 같이, bin packing 문제 또한 사물들을 bin에 포장하는 것도 포함된다.

그러나 bin packing문제는 다른 목적을 가지고 있다 : 모든 사물들을 넣을 수 있는 가장 최소의 bin 갯수를 찾는 것이다.

 

두 문제 간의 차이를 요약한 것이다 : 

• Multiple knapsack problem : 다양한 용량들로 이루어진 bin의 고정된 갯수들에 사물들의 일부를 포장한다. 따라서 포장된 사물들의 전체 값은 최대화되어야 한다. 
• Bin packing problem : 필수적인 공통의 용량들을 가진 많은 bin들이 제공되었을 때, 모든 사물들을 담을 수 있는 최소한의 갯수를 찾는 것이다. 이 문제에서 사물들은 부여된 값이 없다. 왜냐 ? 목적이 값을 얻는 것은 아니기 때문이다.

다음 예제에서 bin packing problem을 푸는 방법을 보여줄 것이다.

 

Example

이 예제에서, 다양한 무게의 사물들이 공통의 용량을 가진 bin의 집합에 포장되어야한다. 

모든 사물들을 넣기 위한 충분한 bin들이 있다고 가정할 때, 문제는 충분할 수 있는 최소한의 것을 찾는 것이다.

 

따르는 섹션들은 이 문제를 푸는 프로그램이다.

 

이 예제에서는 MPSolver wrapper를 사용하였다. 

 

from ortools.linear_solver import pywraplp
def create_data_model():
    data = {}
    weights= [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
    data['weights'] = weights
    data['items'] = list(range(len(weights)))
    data['bins'] = data['items']
    data['bin_capacity'] = 100
    return data

#여기서는 사물에 값을 부여하지 않는다. bin의 수를 최소화하는 목적에는 값이 포함되어있지 않기 때문이다.

def BinPacking():
    # create the mip solver with the SCIP backend
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        return

    #create the variables
    #x[i, j] = 1 if item i is packed in bin j
    x = {}
    data = create_data_model()
    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 = {}
    for j in data['bins']:
        y[j] = solver.IntVar(0, 1, 'y[%i]' %j)

    #multiple knapsack 예제에서는 bin j에 사물 i를 두었을 경우 x[(i, j)]변수의 배열을 정의하였다.
    #bin packing의 경우 변수의 배열 y[j]도 정의한다. 이때 값은 만약 bin j가 사용된다면 1이다. 그렇지 않으면 0이다.
    # y[j]의 합은 사용된 bin들의 수이다.

    #define the constraints
    #constraints
    #each item must be in exactly one bin
    for i in data['items']:
        solver.Add(sum(x[i, j] for j in data['bins']) == 1)

    #the amount packed in each bin cannot exceed its capacity.
    for j in data['bins']:
        solver.Add(
            sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= y[j] * data['bin_capacity']
        )
    #define the objective
    #objective : minimize the number of bins used
    solver.Minimize(solver.Sum([y[j] for j in data['bins']]))
    # 만약 bin j 를 사용했다면, y[j] 가 1이고 아니라면 0이다. y[j]의 합은 사용된 bin의 숫자이다.
    # objective는 결국 합을 최소화하는 것이다.

    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('Bin number', j)
                    print('  Items packed:', bin_items)
                    print('  Total weight:', bin_weight)
                    print()
        print()
        print('Number of bins used:', num_bins)
        print('Time = ', solver.WallTime(), ' milliseconds')
    else:
        print('The problem does not have an optimal solution.')


BinPacking()

 

Reference : 

https://developers.google.com/optimization/pack/bin_packing

휴지통 포장 문제  |  OR-Tools  |  Google Developers