HorusLP로 최적화 알고리즘 설계

연산 연구 및 볼록 최적화는 수년 동안 광범위한 상용 응용 프로그램을 발견한 응용 수학의 한 분야입니다. 컴퓨팅 성능이 보다 저렴해지고 널리 사용 가능해짐에 따라 연구원들은 더 나은 결정을 내리는 데 도움이 되는 점점 더 정교한 최적화 알고리즘을 구축하기 시작했습니다. 오늘날 운영 연구를 기반으로 하는 애플리케이션은 글로벌 물류의 라우팅에서 에너지 산업의 전력 생산 평활화에 이르기까지 모든 것을 지원합니다.

기본 기술이 복잡해짐에 따라 연구원과 개발자가 보다 생산적으로 작업할 수 있도록 새로운 도구 세트가 만들어졌습니다. AMPL, CVXPY 및 PuLP와 같은 이러한 도구를 통해 개발자는 최적화 알고리즘을 신속하게 정의, 구축 및 실행할 수 있으며 다양한 솔버와 인터페이스할 수 있습니다.

그러나 최적화 기술과 비즈니스 요구 사항이 계속해서 정교해지면서 이러한 도구의 대부분은 거의 동일하게 유지되었으며 산업 요구 사항을 충족할 만큼 빠르게 발전하지 못했습니다. 결과적으로 이러한 알고리즘을 개발, 관리, 디버깅 및 조정하려면 특히 빠르게 움직이는 비즈니스 환경에서 많은 양의 인지 오버헤드가 필요한 경우가 많습니다.

오늘은 알고리즘 개발 워크플로의 아키텍처에 도움이 되는 Python 최적화 라이브러리인 HorusLP를 소개하고자 합니다. 이 도구가 해결하도록 설계된 문제에 대해 이야기한 다음 Python 라이브러리에 대한 간략한 개요를 제공하고 몇 가지 예제 최적화 알고리즘을 구축할 것입니다.

최적화 알고리즘 개발자가 직면한 문제

대부분의 개발자가 직면하는 영구적인 문제 중 하나는 유지 관리가 가능하고 효율적이며 관용적인 소프트웨어를 구축하는 것과 프로젝트의 시간 제약 내에서 제품을 제공하는 것 사이의 균형입니다. 브라우저 기반 애플리케이션, 웹 API 또는 사용자 인증 마이크로서비스에서 작업하는 경우 목표를 달성하는 "올바른" 방법과 "빠른" 방법 사이에는 종종 절충점이 있습니다. 제품 복잡성이 증가함에 따라 이러한 고유한 절충안이 더욱 두드러집니다.

대부분의 분야에서 개발자는 아키텍처에 도움이 되는 프레임워크나 라이브러리를 선택하여 이 문제를 완화할 수 있습니다. 웹 대면 프론트 엔드에서 많은 개발자는 React 또는 Angular를 선택합니다. API 개발의 세계에서 소프트웨어 엔지니어는 Django, ASP.NET MVC 또는 Play 중에서 선택할 수 있습니다. 그러나 겸손한 최적화 알고리즘 개발자의 경우 아키텍처 복잡성을 관리하는 데 도움이 되는 아키텍처 도구가 거의 없습니다. 개발자는 변수, 제약 조건 및 다양한 목표를 스스로 관리해야 합니다. 게다가, 운영 연구 알고리즘은 일반적으로 내성을 찾기가 어려워 문제를 악화시킵니다.

HorusLP의 주요 목적은 최적화 알고리즘 개발을 위한 아키텍처 프레임워크를 제공하는 것입니다. 구조적 일관성을 제공함으로써 프레임워크는 조직을 보다 쉽게 ​​만들고 개발자가 가장 잘하는 일인 알고리즘 구축에 집중할 수 있도록 합니다.

일반적인 최적화 워크플로 과제

OR 알고리즘을 개발할 때 복잡성의 몇 가지 주요 원인이 있습니다.

변수의 복잡성

• 추가 비즈니스 요구 사항을 수용하기 위해 변수를 추가해야 하는 경우가 많으며 나중에 모델 정의 및 보고에 사용하기 위해 변수를 쉽게 추적할 수 없습니다.
• 관련 변수를 그룹화하고 추적해야 하며 이를 관리할 뚜렷한 방법이 없습니다.

제약으로 인한 복잡성

• 다양한 시나리오를 지원하고 디버깅을 수행하려면 제약 조건을 추가 및 제거해야 하지만 제약 조건을 추가하거나 제거할 명확한 위치가 없습니다.
• 제약 조건은 종종 서로 관련/의존하며 관계를 표현하는 자연스러운 방법이 없습니다.

목표의 복잡성

• 객관적인 표현은 여러 구성 요소가 있는 경우 다루기 어려워질 수 있습니다. 다양한 구성 요소에 가중치를 부여하고 비즈니스 요구 사항에 따라 가중치를 조정해야 하는 경우 상황이 악화될 수 있습니다.

디버깅의 복잡성

• 개발 중에 모델의 결과를 쉽게 볼 수 있는 방법은 없습니다. 개발자는 결과를 보기 위해 새 변수와 제약 조건 값을 명시적으로 인쇄해야 합니다. 이로 인해 코드가 중복되고 개발 속도가 느려집니다.
• 제약 조건을 추가하면 모델이 실행 불가능하게 되는 경우 제약 조건으로 인해 모델이 실행 불가능하게 된 이유가 명확하지 않을 수 있습니다. 일반적으로 개발자는 시행착오를 통해 다양한 제약 조건을 제거하고 비호환성을 찾아야 합니다.

HorusLP는 구조, 도구, 모범 사례를 제공하여 개발자 생산성 및 제품 유지 관리 용이성을 개선함으로써 이러한 문제를 보다 쉽게 ​​관리할 수 있기를 희망합니다.

HorusLP 튜토리얼: 최적화 알고리즘 및 API 개요

더 이상 고민하지 않고 HorusLP 라이브러리가 무엇을 할 수 있는지 살펴보겠습니다!

HorusLP는 Python 및 PuLP를 기반으로 하므로 pip를 사용하여 설치하려고 합니다. 명령줄에서 다음을 실행합니다.

 Pip install horuslp pulp

설치가 완료되면 Python 파일을 열어 보겠습니다. 우리는 운영 연구에 대한 이전 기사에서 배낭 문제를 구현할 것입니다.

HorusLP 라이브러리에는 매우 간단한 선언적 API와 상용구가 거의 없습니다. 필요한 클래스와 변수를 가져오는 것으로 시작하겠습니다.

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

모든 변수를 가져왔으면 이 문제에 필요한 변수를 정의해 보겠습니다. 변수 관리자 하위 클래스를 만들고 이진 변수로 채우면 됩니다.

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

이제 변수가 정의되었으므로 제약 조건을 정의해 보겠습니다. 우리는 주요 제약 클래스를 서브클래싱하고 "define" 기능을 구현하여 제약 조건을 생성합니다.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

정의 함수에서 이름으로 필요한 변수를 요청할 수 있습니다. 프레임워크는 변수 관리자에서 변수를 찾아 정의 함수에 전달합니다.

제약 조건이 구현된 후 목표를 구현할 수 있습니다. 간단한 목적이므로 ObjectiveComponent 를 사용합니다.

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

정의 기능은 제약 조건 클래스의 정의 기능과 매우 유사한 설정을 가지고 있습니다. 그러나 제약 조건 표현식을 반환하는 대신 affine 표현식을 반환합니다.

이제 변수, 제약 조건 및 목표가 정의되었으므로 모델을 정의해 보겠습니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

모델을 빌드하기 위해 Problem 클래스의 하위 클래스인 클래스를 만들고 변수, 목표, 제약 조건 및 의미를 지정합니다. 지정된 문제로 문제를 해결할 수 있습니다.

 prob = KnapsackProblem() prob.solve()

해결 후 문제 클래스의 print_results 함수를 사용하여 결과를 인쇄할 수 있습니다. result_variables 클래스를 보고 특정 변수의 값에 액세스할 수도 있습니다.

 prob.print_results() print(prob.result_variables)

스크립트를 실행하면 다음 출력이 표시되어야 합니다.

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

문제 상태, 변수의 최종 값, 목적 값 및 제약 조건 표현식의 값이 표시되어야 합니다. 또한 변수의 결과 값을 사전으로 봅니다.

그리고 거기에 약 35줄의 첫 번째 HorusLP 문제가 있습니다!

다음 예제에서는 HorusLP 라이브러리의 좀 더 정교한 기능을 살펴보겠습니다.

변수 그룹 사용

때로는 변수가 관련되어 있고 논리적 그룹에 속합니다. 배낭 문제의 경우 모든 변수를 개체 그룹에 배치할 수 있습니다. 변수 그룹을 사용하도록 코드를 리팩토링할 수 있습니다. 다음 튜토리얼에서 참조할 것이므로 이전 섹션의 코드를 저장하십시오!

import 문을 다음과 같이 변경합니다.

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

이제 다음과 같이 배낭 변수 선언도 변경해야 합니다.

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

첫 번째 인수는 변수 그룹의 이름이고 두 번째 변수는 해당 그룹 내의 변수 이름 목록입니다.

이제 제약 조건과 목적 정의를 변경해야 합니다. 개별 이름을 묻는 대신 변수 그룹에 대해 질문할 것입니다. 변수 그룹은 키가 이름이고 값이 변수인 사전으로 전달됩니다. 제약 조건 및 목적 정의를 다음과 같이 변경합니다.

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

이제 동일한 문제 정의를 사용하고 명령을 실행할 수 있습니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

출력에 다음이 표시되어야 합니다.

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

여러 제약 관리

단일 제약 조건이 있는 모델은 비교적 드뭅니다. 여러 제약 조건으로 작업할 때 모든 제약 조건을 한 곳에 모아 쉽게 추적하고 관리할 수 있도록 하는 것이 좋습니다. HorusLP는 이를 자연스럽게 만듭니다.

예를 들어, 모델이 배낭에 카메라를 추가하도록 하면 결과가 어떻게 달라지는지 확인하려고 한다고 가정해 보겠습니다. 우리는 추가적인 제약을 구현하고 그것을 우리의 문제 정의에 추가할 것입니다.

첫 번째 자습서에서 구현한 모델로 돌아갑니다. 다음 제약 조건을 추가합니다.

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

모델에 제약 조건을 추가하려면 다음과 같이 문제 정의에 제약 조건을 추가하기만 하면 됩니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

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

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

stdout에 인쇄되는 새 제약 조건과 변경된 최적 변수 값이 표시되어야 합니다.

종속 제약 조건 및 제약 조건 그룹 관리

제약 조건은 서로 종속되어 있거나 논리적으로 동일한 그룹에 속하기 때문에 종종 서로 관련됩니다.

예를 들어, 변수 집합의 절대값 합계를 제한하는 제약 조건을 설정하려면 먼저 의도한 변수 간의 절대값 관계를 표현하는 제약 조건을 지정한 다음 절대값 한계를 지정해야 합니다. 때로는 변수 간의 특정 관계를 표현하기 위해 변수 그룹에 유사한 제약 조건을 적용해야 합니다.

이러한 그룹화를 표현하기 위해 제약 정의의 종속 제약 기능을 사용할 수 있습니다. 종속 제약 조건 기능을 사용하는 방법을 보려면 이전 문제의 SizeConstraint 를 다음과 같이 리팩터링하십시오.

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

이제 종속 제약 조건이 자동으로 구현되는지 테스트하기 위해 문제 정의에서 MustHaveItemConstraint 를 제거해 보겠습니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

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

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

MustHaveItemConstraint 가 구현된 것 같습니다! 종속 제약 조건을 사용할 수 있는 방법에 대한 보다 복잡한 예는 자습서 끝부분에 있는 스태핑 예를 참조하십시오.

여러 가중 목표 관리

종종 최적화 알고리즘을 개발하는 동안 여러 부분으로 구성된 객관적인 표현을 접하게 됩니다. 실험의 일환으로 알고리즘을 원하는 결과로 편향시키기 위해 다양한 객관적 구성 요소의 가중치를 변경할 수 있습니다. CombinedObjective 는 이것을 표현하는 깨끗하고 간단한 방법을 제공합니다.

입상과 사이다를 선택하기 위해 알고리즘을 편향시키고 싶다고 가정합니다. CombinedObjective 를 사용하도록 이전 섹션의 코드를 리팩토링해 보겠습니다.

먼저 다음과 같이 CombinedObjective 클래스를 가져옵니다.

 from horuslp.core import CombinedObjective

다음과 같이 독립적인 목적 구성 요소를 구현할 수 있습니다.

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

이제 CombinedObjective 를 구현하여 가치 목표와 사이다/피규어 목표를 결합할 수 있습니다.

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

이제 문제 정의를 다음과 같이 변경해 보겠습니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

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

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

출력은 결합된 목적 값, 각 목적 구성 요소의 값, 가중치 및 물론 모든 제약 조건 값의 개요를 설명합니다.

호환되지 않는 제약 조건 찾기

알고리즘을 개발할 때 종종 실행 불가능한 모델에 부딪힙니다. 모델이 복잡한 경우 모델이 갑자기 실행 불가능한 이유를 파악하는 것이 어려울 수 있습니다. HorusLP에는 이러한 경우에 도움이 되는 편리한 도구가 있습니다.

제약 조건을 추가하고 다음 제약 조건 세트로 끝났다고 가정합니다.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

우리는 배낭에 있는 항목의 총 크기에 대한 몇 가지 제약 조건, 사이다를 배낭에 넣어야 하는 제약 조건, 카메라가 배낭에 있어야 하는 것과 그렇지 않은 것을 요구하는 호환되지 않는 제약 집합이 있습니다. (물론 실제 알고리즘에서 제약 조건은 일반적으로 명확하지 않으며 복잡한 변수 관계 및 제약 조건을 포함합니다.)

또한 제약 조건이 다음과 같은 방식으로 그룹화되어 감지가 더 어려워진다고 가정합니다.

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

다음은 문제 정의입니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

문제를 실행하면 다음 결과가 표시됩니다.

 KnapsackProblem: Infeasible

안 돼! 우리는 무엇을해야합니까? 대부분의 도구를 사용하는 경우 잠재적으로 충돌할 수 있는 제약 조건을 하나씩 좁히는 어려운 디버깅 세션을 시작해야 합니다. 다행히 HorusLP에는 비호환성 검색 기능이 있어 비호환성 제약 조건을 더 빨리 좁힐 수 있습니다. 비호환성 검색 기능을 사용하는 가장 간단한 방법은 다음과 같이 print_results 호출을 변경하는 것입니다.

 prob.print_results(find_infeasible=True)

간단합니다! 코드를 실행하면 이제 다음과 같은 출력이 표시됩니다.

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

엄청난! 이제 MustHaveItemConstraint 가 실행 불가능의 원인이 아니며 문제가 CombinedConstraints1 및 CombinedConstraints2 로 인한 것임을 확인했습니다.

이는 우리에게 약간의 정보를 제공하지만 결합된 제약 조건 사이에는 4개의 종속 제약 조건이 있습니다. 네 가지 제약 조건 중 호환되지 않는 제약 조건을 식별할 수 있습니까? 네. 다음과 같이 print_results 호출을 수정하십시오.

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

이렇게 하면 실행 불가능성 검색이 종속 제약 조건을 확장하여 실행 불가능성의 원인에 대한 훨씬 더 세부적인 그림을 얻을 수 있습니다. 이것을 실행하면 다음 출력이 표시되어야 합니다.

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

매번 깊은 실행 불가능성 검색을 실행하고 싶은 유혹이 있지만 많은 수의 총 제약 조건이 있는 현실적인 문제의 경우 깊은 실행 불가능성 검색은 리소스 집약적이고 시간이 많이 소요될 수 있습니다. 따라서 가능성을 좁히기 위해 기본 실행 불가능성 검색을 실행하고 수동 조사를 수행한 후 더 작은 하위 집합에 대해 심층 실행 불가능성 검색을 실행하는 것이 가장 좋습니다.

데이터 파일에서 알고리즘 구축

모델을 구축할 때 모든 제약 조건과 변수를 하드 코딩할 수 있는 여유는 거의 없습니다. 종종 우리 프로그램은 입력 데이터에 따라 모델을 변경할 수 있을 만큼 충분히 유연해야 합니다. 하드 코딩된 입력 대신 다음 JSON에서 배낭 문제를 작성하려고 한다고 가정합니다.

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

제약 조건과 목표에 대해 구현하는 "정의" 기능에 대한 kwargs의 지원에 의존하여 이를 수행할 수 있습니다.

간단한 배낭 문제(튜토리얼의 섹션 1에서 구현한 문제)에서 코드를 수정해 보겠습니다. 먼저 JSON 문자열을 파일에 넣습니다. 물론 일반적으로 외부 소스에서 읽지만 단순성을 위해 모든 것을 하나의 파일에 보관하겠습니다. 코드에 다음을 추가합니다.

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

또한 우리 프로그램이 그것을 구문 분석할 수 있는지 확인합시다. import 문에 다음을 추가합니다.

 Import json

이제 다음과 같이 변수 설정 코드를 수정해 보겠습니다.

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

이렇게 하면 JSON의 각 항목에 대한 변수를 정의하고 적절하게 이름을 지정합니다.

제약 조건과 목적 정의를 다음과 같이 변경해 보겠습니다.

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

특정 변수 대신 **kwargs 를 요청하여 define 함수는 이름별로 모든 변수를 포함하는 사전을 얻습니다. 제약 조건 정의 함수는 사전에서 변수에 액세스할 수 있습니다.

참고: 변수 그룹의 경우 첫 번째 수준이 그룹 이름이고 두 번째 수준이 변수 이름인 중첩된 사전이 됩니다.

나머지는 매우 간단합니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

이 프로그램을 실행하면 다음 출력이 표시되어야 합니다.

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

HorusLP에서 사용자 정의 메트릭 정의

때때로 디버깅 및 보고 목적을 위해 목표 또는 제약 조건으로 직접 표현되지 않는 사용자 지정 메트릭을 구축합니다. HorusLP에는 사용자 지정 메트릭을 간단하게 지정할 수 있는 기능이 있습니다.

이전 섹션의 모델이 배낭에 얼마나 많은 과일을 넣었는지 추적하고 싶다고 가정합니다. 이를 추적하기 위해 사용자 정의 메트릭을 정의할 수 있습니다. Metrics 기본 클래스를 가져오는 것으로 시작하겠습니다.

 From horuslp.core import Metric

이제 맞춤 측정항목을 정의해 보겠습니다.

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

보시다시피 정의된 인터페이스는 제약 조건 및 목적 컴포넌트 클래스의 인터페이스와 매우 유사합니다. 지금까지 튜토리얼을 따랐다면 이것은 상당히 익숙할 것입니다.

이제 문제 정의에 메트릭을 추가해야 합니다. 여기서 인터페이스는 제약 조건 정의와 매우 유사합니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

이것을 실행하면 다음 출력이 표시되어야 합니다.

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

하단에 인쇄된 과일의 수를 볼 수 있습니다.

더 복잡한 문제 해결하기: 두 개의 배낭

조금 더 복잡한 예를 살펴보겠습니다. 배낭 하나 대신 가방과 여행 가방이 있다고 가정합니다. 또한 내구성이 있는 것과 깨지기 쉬운 두 가지 종류의 물체가 있습니다. 더 보호 기능이 있는 여행 가방은 깨지기 쉬운 물건과 내구성 있는 물건을 모두 담을 수 있습니다. 반면 가방에는 내구재만 담을 수 있습니다. 항목에 대한 데이터가 다음 JSON으로 제공된다고 가정합니다.

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

이것이 어떻게 모델을 변경하는지 봅시다. 모델이 상당히 다를 것이기 때문에 백지 상태로 시작하겠습니다. 문제 설정부터 시작합니다.

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

이제 변수를 설정해 보겠습니다. 가능한 모든 항목/컨테이너 조합에 대해 이진 변수를 설정합니다.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

이제 여행 가방과 가방 모두에 대한 무게 제한을 구현하려고 합니다.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

이제 우리는 약간 더 복잡한 제약 조건(항목이 여행 가방과 가방에 모두 들어가지 않도록 하는 제약 조건)을 구현해야 합니다. 즉, "in suitcase" 변수가 1이면 "in the bag" 변수는 0이어야 하며 그 반대의 경우도 마찬가지입니다. 물론 항목이 어느 컨테이너에도 없는 경우를 허용하고 싶습니다.

이 제약 조건을 추가하려면 모든 내구성 항목을 반복하고 "in the suitcase" 변수와 "in the bag" 변수를 찾고 이러한 변수의 합이 1보다 작다고 주장해야 합니다.

HorusLP에서 매우 쉽게 종속 제약 조건을 동적으로 정의할 수 있습니다.

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

이제 제약 조건이 정의되었으므로 목표를 빌드해 보겠습니다. 목표는 컨테이너에 있는 모든 항목에서 얻은 모든 값의 단순 합계입니다. 따라서:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

또한 몇 가지 사용자 지정 메트릭을 정의하여 가방과 여행 가방에 얼마나 많은 무게가 실렸는지, 여행 가방 무게 중 내구재와 깨지기 쉬운 물건에서 나온 무게를 한 눈에 확인할 수 있습니다.

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

이제 모든 부분이 완료되었으므로 문제를 인스턴스화하고 모델을 실행해 보겠습니다.

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

이것을 실행하면 stdout에 다음 출력이 표시되어야 합니다.

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

따라서 카메라, 안경, 사과, 바나나는 총 15개의 무게 단위에 대해 여행 가방에 들어가고 피규어, 뿔, 레더맨은 모두 총 17개의 무게 단위로 가방에 들어갑니다. 상품의 총 가치는 32 가치 단위로 나옵니다. 흥미롭게도 가방에 내구재를 모두 담을 수 있는 충분한 용량이 있었기 때문에 가방에 내구재가 하나도 들어 있지 않았습니다.

더 크고 현실적인 시나리오: 인력 충원 문제

HorusLP 튜토리얼에서 여기까지 왔다면 축하합니다! 이제 HorusLP를 사용하는 방법에 대한 좋은 아이디어가 생겼습니다.

그러나 우리가 작업한 모든 예제는 지금까지 배낭 문제의 순열이었고 일부 요구 사항과 매개 변수는 약간 비현실적입니다. HorusLP가 보다 현실적인 문제를 해결할 수 있는 방법을 보기 위해 함께 문제를 하나 더 해결해 보겠습니다. 이전 Toptal 기사의 후반부에 설명된 인력 문제를 해결해 보겠습니다.

시간의 이익을 위해 우리는 모델의 최종 버전(개인 갈등, 노동 규정 및 임시 근로자 수당 포함)으로 곧장 갈 것이지만 초기의 더 간단한 모델의 구현은 GitHub에서도 사용할 수 있습니다.

이제 문제를 설정하여 시작하겠습니다.

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees 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 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

이제 변수를 정의해 보겠습니다. 이 경우에는 작업자가 교대 근무를 해야 하는지 여부를 결정하는 이진 변수와 각 교대에 대해 고용하는 도트라키의 수를 결정하는 정수 변수가 있습니다.

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

이제 모든 교대 근무에 충분한 인력을 배치해야 하는 제약 조건을 구현해 보겠습니다.

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

이제 특정 사람들이 서로 작업하는 것을 방지하는 제약 조건을 구현해야 합니다.

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

마무리

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. 곧 소식을 들을 수 있기를 바랍니다!