본문 바로가기
  • ̀⁽ᵕ̈⁾ ́

M.S./OR-Tools23

[OR-Tools 스터디] Packing packing problem의 목적은 고정된 capacity를 container에 주어진 크기의 아이템 세트를 포장하는 최고의 방법을 찾는 것이다. 전형적인 application은 효율적으로 이사 트럭에 박스를 싣는 것이다. capacity constraint로 인해 종종 모든 물건들을 포장할 순 없다. 이러한 경우, 문제는 container에 적합한 최대 전체 사이즈의 사물 집합을 찾는 것이다. 이것은 packing문제의 많은 종류이다. 가장 중요한 두가지는 knapsack problem과 bin packing이다. Knapsack problems 단순한 knapsack problem에서는 single container이다. 사물들은 사이즈 뿐만아니라 값도 있으며, 목표는 총 값이 최대인 사물의 부분집.. 2023. 2. 23.
[OR-Tools 스터디] Linear Sum Assignment Solver 이번 섹션에서는 linear sum assignment solver에 대해 기술할 것이다. 이는 단순한 assignment problem을 위한 전문 solver이며, 이는 MIP 혹은 CP-SAT solver보다 더 빠르게 동작할 수 있다. 그러나 MIP와 CP-SAT solver들은 더 광범위한 배열에 대한 문제도 다룰 수 있기에 대부분의 경우, 이들이 최고의 옵션이다. Cost matrix 노동자들과 일의 비용들이 아래 표로 주어졌다. 아래 섹션들에서 linear sum assignment solver를 사용한 assignment problem을 푸는 파이썬 프로그램을 보여준다. import numpy as np from ortools.graph.python import linear_sum_assi.. 2023. 2. 23.
[OR-Tools 스터디] Assignment with Allowed Groups 13명의 노동자가 있으며 이 수는 0~11로 표현한다. 허용되는 그룹들은 다음 작업자 쌍의 조합이다. group1 = [[2, 3], # Subgroups of workers 0 - 3 [1, 3], [1, 2], [0, 1], [0, 2]] group2 = [[6, 7], # Subgroups of workers 4 - 7 [5, 7], [5, 6], [4, 5], [4, 7]] group3 = [[10, 11], # Subgroups of workers 8 - 11 [9, 11], [9, 10], [8, 10], [8, 11]] 허용된 그룹은 그룹1, 2, 3 각각으로부터 한 쌍씩 세 쌍의 조합일 수 있다. 예를들어, [2,3], [6,7], [10,11]의 조합은 [2,3,6,7,10,11]로부터 .. 2023. 2. 23.
[OR-Tools 스터디] Assignment 가장 잘 알려져있는 combinatorial optimization 문제 중 하나는 assignment problem이다. 예제 : 노동자 그룹들이 일련의 일들을 수행할 필요가 있다고 가정하고, 각 노동자들과 일에 있어서 노동자에게 일을 부여하는 것에 비용이 든다. 문제는 총 비용을 최소화하면서 두 명의 작업자가 동일한 일을 수행하지 않고, 각 노동자 별로 최소 하나의 일이 부여되어야한다는 것이다. 이 문제를 아래의 그래프와 같이 표현할 수 있는데, 여기서는 4명의 노동자와 4개의 일이 있다. 각 가장자리에는 노동자 별로 일을 할당하는 모든 가능한 경우의 수를 보여준다. 가장자리의 레이블들은 노동자별로 할당된 일들의 비용이다. 가장자리 부분에 해당하는 assignment는 각각의 노동자들이며, 이들은 적.. 2023. 2. 22.

티스토리툴바