혼합 정수 프로그래밍: 전산 의사 결정 가이드

최적의 결정을 내리기 위해 컴퓨터를 사용하는 과학인 운영 연구는 소프트웨어의 많은 영역에서 사용되고 적용되었습니다. 몇 가지 예를 들자면, 물류 회사는 A 지점에서 B 지점으로 가는 최적의 경로를 결정하는 데 사용하고, 전력 회사는 이를 사용하여 전력 생산 일정을 결정하고, 제조 회사는 이를 사용하여 공장에 대한 최적의 인력 패턴을 찾습니다.

오늘 우리는 가상의 문제를 살펴봄으로써 운영 연구의 힘을 탐구할 것입니다. 특히 MIP(Mixed Integer Programming)를 사용하여 가상 공장에 대한 최적의 직원 배치 패턴을 결정합니다.

운영 연구 알고리즘

예제 문제를 살펴보기 전에 운영 연구의 몇 가지 기본 개념을 살펴보고 오늘 사용할 도구를 이해하는 것이 좋습니다.

선형 계획법 알고리즘

선형 계획법은 목표와 제약 조건이 선형 방정식 시스템으로 표현되는 수학적 모델에서 최상의 결과를 결정하는 데 사용되는 연산 연구 기법입니다. 선형 계획법 모델의 예는 다음과 같습니다.

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

우리의 매우 간단한 예에서 최적의 결과는 5이고 a = 2 및 b = 3임을 알 수 있습니다. 이것은 다소 사소한 예이지만 수천 개의 변수와 수백 개의 제약 조건을 사용하는 선형 계획법 모델을 상상할 수 있습니다. .

좋은 예는 의사 코드에서 아래와 같이 끝날 수 있는 투자 포트폴리오 문제일 수 있습니다.

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

손이나 시행 착오로 해결하기가 다소 복잡하고 어려울 것입니다. 운영 연구 소프트웨어는 이러한 문제를 신속하게 해결하기 위해 여러 알고리즘을 사용합니다. 기본 알고리즘에 관심이 있다면 여기에서 심플렉스 방법과 내부 포인트 방법에 대해 배우는 것이 좋습니다.

정수 프로그래밍 알고리즘

정수 프로그래밍은 일부 또는 모든 변수가 정수 값이 되도록 추가로 허용하는 선형 프로그래밍과 같습니다. 이것이 처음에는 크게 개선되지 않은 것처럼 보일 수 있지만 선형 계획법만으로는 해결되지 않은 많은 문제를 해결할 수 있습니다.

그러한 문제 중 하나는 배낭 문제로, 할당된 값과 가중치가 있는 항목 집합이 주어지고 배낭에 들어갈 수 있는 가장 높은 값의 항목 조합을 찾도록 요청받습니다. 선형 계획법 모델은 이 문제를 해결할 수 없습니다. 품목을 배낭에 넣을 수 있는지 여부를 표현할 방법이 없지만 품목의 일부를 배낭에 넣을 수는 없기 때문입니다. 모든 변수는 연속형입니다. 변하기 쉬운!

예시 배낭 문제에는 다음 매개변수가 있을 수 있습니다.

MIP 모델은 다음과 같습니다.

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

이 경우 최적의 솔루션은 a=0, b=1, c=0, d=1이며 전체 항목의 값은 17입니다.

오늘 우리가 해결할 문제는 공장의 직원이 교대 근무를 하도록 일정을 잡을 수도 있고 안 할 수도 있기 때문에 정수 프로그래밍이 필요합니다. 간단하게 하기 위해 이 공장에서는 직원의 2/3를 근무 일정으로 지정할 수 없습니다.

정수 프로그래밍을 가능하게 하기 위해 여러 수학적 알고리즘이 사용됩니다. 기본 알고리즘에 관심이 있다면 여기에서 절단 평면 알고리즘과 분기 및 경계 알고리즘을 공부하는 것이 좋습니다.

예제 문제: 스케줄링

문제 설명

오늘 우리는 공장 직원의 문제에 대해 알아볼 것입니다. 공장 관리인으로서 우리는 인건비를 최소화하기를 원하지만 생산 수요를 충족시키기 위해 모든 교대조에 대해 충분한 적용 범위를 보장하고자 합니다.

다음과 같은 인력 수요가 있는 5교대 근무가 있다고 가정합니다.

그리고 다음 작업자가 있다고 가정합니다.

문제를 단순하게 유지하기 위해 가용성과 비용이 유일한 관심사라고 잠시 가정해 보겠습니다.

우리의 도구

오늘의 문제에서는 CBC라는 오픈 소스 분기 및 절단 소프트웨어를 사용할 것입니다. Python용으로 널리 사용되는 운영 연구 모델링 라이브러리인 PuLP를 사용하여 이 소프트웨어와 인터페이스합니다. 여기에 대한 정보를 찾을 수 있습니다.

PuLP를 사용하면 매우 Pythonic한 방식으로 MIP 모델을 구성할 수 있으며 기존 Python 코드와 잘 통합됩니다. 이것은 가장 널리 사용되는 데이터 조작 및 분석 도구 중 일부가 Python으로 작성되고 대부분의 상용 운영 연구 시스템은 최적화 전후에 광범위한 데이터 처리가 필요하기 때문에 매우 유용합니다.

PuLP의 단순함과 우아함을 보여주기 위해 이전의 배낭 문제가 PuLP에서 해결되었습니다.

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

이것을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

이제 스케줄링 문제로 넘어갑니다!

솔루션 코딩

우리 솔루션의 코딩은 매우 간단합니다. 먼저 데이터를 정의하려고 합니다.

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

다음으로 모델을 정의하려고 합니다.

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

이제 우리는 결과를 풀고 인쇄하도록 요청합니다!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

코드를 실행하면 다음 출력이 표시되어야 합니다.

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

난이도를 조금 더 높이세요: 추가 제약

이전 모델이 흥미롭고 유용했지만 혼합 정수 프로그래밍의 힘을 완전히 보여주지는 못했습니다. 또한 for 루프를 쉽게 작성하여 모든 교대조에 대해 가장 저렴한 x 근로자를 찾을 수 있습니다. 여기서 x 는 교대 근무에 필요한 근로자 수입니다. MIP를 사용하여 명령형 방식으로 해결하기 어려운 문제를 해결하는 방법을 보여주기 위해 몇 가지 추가 제약 조건을 추가하면 어떤 일이 발생하는지 살펴보겠습니다.

추가 제약

새로운 노동 규정으로 인해 작업자를 2교대 이상 할당할 수 없다고 가정합니다. 증가된 작업을 설명하기 위해 Dothraki Staffing Group의 도움을 구했습니다. Dothraki Staffing Group은 교대당 $40의 비율로 각 교대 근무당 최대 10명의 Dothraki 직원을 공급할 것입니다.

또한 공장 외부에서 진행 중인 대인 관계 갈등으로 인해 Cersei와 Jaime이 Daenerys 또는 Jon과 함께 교대 근무를 할 수 없다고 가정해 보겠습니다. 또한 Jaime과 Cersei는 교대 근무를 함께 할 수 없습니다. 마지막으로, 특히 복잡한 대인 관계를 가진 Arya는 Jaime, Cersei 또는 Melisandre와 같은 교대조에서 일할 수 없습니다.

이 두 가지 새로운 제약 조건과 리소스를 추가한다고 해서 절대적인 수단을 통해 문제를 해결할 수 없는 것은 아니지만 작업자를 특정 교대조로 예약하는 기회 비용을 고려해야 하므로 솔루션이 훨씬 더 어려워집니다.

해결책

그러나 혼합 정수 프로그래밍을 사용하면 훨씬 쉽습니다. 다음과 같이 코드를 수정하면 됩니다.

금지 목록 및 몇 가지 제약 조건을 정의합니다.

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

금지 및 최대 시프트 제약을 구현하기 위한 변수를 채웁니다.

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Dothraki 변수를 추가합니다.

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

또한 교대 및 금지 요구 사항을 계산하기 위해 약간 수정된 루프가 필요합니다.

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

마지막으로 결과를 인쇄하려면 다음을 수행합니다.

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

그리고 우리는 잘 가야합니다. 코드를 실행하면 아래와 같은 출력이 표시되어야 합니다.

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

그리고 금지된 근로자 목록을 존중하고 노동 규정을 준수하며 Dothraki 근로자를 신중하게 사용하는 결과가 있습니다.

결론

오늘 우리는 더 나은 결정을 내리기 위해 혼합 정수 프로그래밍을 사용하는 방법을 살펴보았습니다. 우리는 연산 연구에 사용되는 기본 알고리즘과 기술에 대해 논의하고 혼합 정수 프로그래밍이 실제 세계에서 사용되는 방식을 나타내는 예제 문제를 살펴보았습니다.

이 기사가 운영 연구에 대해 더 많이 배우고 이 기술을 프로젝트에 적용할 수 있는 방법에 대해 생각하는 데 영감을 주었기를 바랍니다. 최적화 알고리즘과 운영 연구의 흥미진진한 세계에서 우리는 빙산의 일각만을 보았습니다.

GitHub에서 이 기사와 관련된 모든 코드를 찾을 수 있습니다. 더 논의하고 싶다면 아래에 의견을 공유하십시오!