[OR-Tools 스터디] Packing

packing problem의 목적은 고정된 capacity를 container에 주어진 크기의 아이템 세트를 포장하는 최고의 방법을 찾는 것이다.

전형적인 application은 효율적으로 이사 트럭에 박스를 싣는 것이다.

capacity constraint로 인해 종종 모든 물건들을 포장할 순 없다. 이러한 경우, 문제는 container에 적합한 최대 전체 사이즈의 사물 집합을 찾는 것이다. 

 

이것은 packing문제의 많은 종류이다. 가장 중요한 두가지는 knapsack problem과 bin packing이다.

 

Knapsack problems

단순한 knapsack problem에서는 single container이다. 사물들은 사이즈 뿐만아니라 값도 있으며, 목표는 총 값이 최대인 사물의 부분집합들을 포장하는 것이다. 

 

값이 크기와 같은 특별한 경우에 대해, 목표는 포장된 아이템들의 전체 크기를 최대화하는 것이다.

 

OR-Tool은 knapsack problem에 대해 algorithms library에서 몇가지 solver를 제공해준다.

 

이는 또한 knapsack problem의 더 일반적인 버전이다.

여기에 예제 세트가 있다.

• multidimensional knapsack problems : 이 문제에서는 물건들이 무게와 부피와 같이 하나의 물리적인 양보다 더 많은 것들을 가지고 있으며, knapsack은 각각의 양에 대한 capacity(용량)를 가지고 있다. 여기, 차원이라는 용어는 높이, 길이, 너비의 보통 공간 차원으로 필수적으로 언급되지 않는다(=꼭 그것을 지칭하는 것은 아니다). 그러나 몇몇 문제들에서는 공간 차원이 포함되어있는데 이 예시로 직사각형 박스를 직사각형 보관박스에 포장하는 합리적인 방법을 찾는 것과 같은 것이 있다. 
• multiple knapsack problems : 여기는 여러개의 knapsack들이 있으며, 이 문제의 목적은 모든 knapsack들에서 포장된 사물들의 전체 값들을 최대화시키는 것이다. 

단일 knapsack으로 multidimensional problem 혹은 오직 1차원만 있는 multiple knapsack problem이 있을 수도 있다.

 

 

The bin-packing problem

가장 잘 알려진 packing문제 중 하나는 bin-packing으로, 이는 동일한 용량의 multiple container를 가지고 있다. 

multiple knapsack problem과는 다르게, 박스의 수가 정해져있지 않다.

대신, 목표는 모든 사물들을 담을 수 있는 박스의 최소 갯수를 찾는 것이다.

 

여기에 multiple knapsack problem과 bin-packing problem 사이의 차이를 기술해둔 예제가 있다.

회사가 배달트럭들을 가지고 있다고 가정할 때, 트럭 각각은 18,000pound의 무게용량을 가지고 있으며 이동시킬 사물들은 130,000pound이다.

• multiple knapsack : 5개의 트럭을 가지고 있으며 그 트럭에 최대로 올릴 수 있는 무게로 사물들을 싣길 원한다.
• bin packing : 20개의 트럭을 가지고 있으며(이는 모든 사물들을 다 실을 수 있을 정도로 충분함) 모든 사물들을 싣는 트럭을 최소로 사용하고 싶을 때. 

 

reference:

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

포장  |  OR-Tools  |  Google Developers