HorusLP-Gurobi: Gurobi를 위한 고급 최적화 아키텍처

게시 됨: 2022-03-11

최적화 기술이 더욱 정교해짐에 따라 상용 솔버가 업계에서 점점 더 중요한 역할을 하기 시작했습니다. 오픈 소스 솔버와 비교할 때 상용 솔루션은 고급 사전 해결, 웜 시작 및 분산 해결과 같은 복잡한 최적화 모델을 해결하기 위한 더 많은 기능을 가지고 있는 경향이 있습니다.

시장에서 가장 인기 있는 상용 솔버 중 하나는 각각 상용 솔버 공간의 개척자인 Zonghao Gu, Edward Rothberg 및 Robert Bixby의 이름을 따서 명명된 Gurobi입니다. Gurobi는 FCC의 대역폭 할당 프로젝트와 펜실베니아 주립 교도소의 수감자 재배치 프로젝트를 포함하여 최근 역사에서 많은 유명 최적화 프로젝트를 추진했습니다.

오늘 우리는 최적화 모델링을 위한 높은 수준의 선언적 인터페이스를 제공하는 소프트웨어 패키지인 HorusLP가 Gurobi의 API와 통합되어 사용자에게 직관적인 모델링 경험을 제공하는 동시에 Gurobi의 가장 고급 기능을 활용하는 방법을 살펴볼 것입니다.

최적화: 빠른 리프레셔

최적화 또는 연산 연구에 익숙하지 않은 사람들을 위해 최적화는 제약 시스템이 적용되는 방정식 시스템 내에서 변수의 최적 값을 찾는 수학적 기술 모음을 나타냅니다. 위의 문장이 다소 건조하게 들린다면 예를 들어 설명하는 데 도움이 될 것입니다.

15파운드의 운반 용량을 가진 배낭이 있다고 가정합니다. 당신 앞에는 특정한 무게와 금전적 가치가 있는 몇 가지 항목이 있습니다.

  1. 카메라: 무게 2파운드, 가치 $5
  2. 입상: 무게 4파운드, 가치 $7
  3. 사이다: 무게 7파운드, 가격 $2
  4. 경적: 무게 10파운드, 가치 $10.

총 무게는 15lbs 미만으로 유지되지만 값은 최대화되도록 배낭에 넣을 품목을 선택하려고 합니다. (저희가 고가의 물건을 배낭에 집어넣는 이유에 대해 더 많은 맥락이 필요하다면 이야기에 상상력을 사용하는 것이 좋습니다. 좋은 후보 내러티브에는 화재 및 부동산 경매에서 물건을 구하는 것이 포함됩니다. 언급하지 않는 것이 좋습니다.)

문제를 다음 최적화 문제로 공식화할 수 있습니다.

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

이 문제를 공식화하면 최적화 기술을 적용하여 배낭에 넣을 최상의 항목을 찾을 수 있습니다. Python을 사용하여 최적화 문제를 해결하고 핵심 HorusLP API를 사용하여 최적화 문제를 해결하는 방법에 대한 이전 기사에서 솔루션의 예를 찾을 수 있습니다.

기본 수학적 기술은 매우 매력적이지만 이 기사의 범위를 벗어납니다. 더 자세히 알고 싶다면 여기와 여기를 살펴보는 것을 추천합니다. 둘 다 구로비에서 제공한 것입니다.

구로비

초기 최적화 문제는 계산기로 작업하는 수학자 팀에 의해 해결되었지만 오늘날 대부분의 최적화 문제는 솔버라는 특수 소프트웨어를 사용하여 해결됩니다. 대부분의 솔버는 일반적으로 잘 공식화된 선형 및 정수 계획법 문제의 대부분에 대한 솔루션을 찾을 수 있지만 일부 솔버는 다른 것보다 훨씬 더 유능합니다. 그들은 다른 사람들이 풀 수 없는 종류의 문제를 풀거나, 최첨단 수학을 적용하여 문제를 더 빨리 풀거나, 분산 컴퓨터를 사용하여 크고 어려운 문제를 해결할 수 있습니다. 가장 고급 기능은 일반적으로 가장 빠르고 가장 정교한 솔버 구축을 전문으로 하는 회사에서 개발 및 유지 관리하는 상용 솔버에서 제공됩니다.

Gurobi는 금융에서 물류에 이르기까지 다양한 산업 분야에서 운영되는 정부, 학술 기관 및 기업을 포함하여 최적화 커뮤니티의 많은 부분에서 사용되는 상업용 솔버 시장의 리더 중 하나입니다. 속도 면에서 gurobi는 상용 및 오픈 소스 솔버를 판단하는 데 사용되는 여러 벤치마크에서 일관되게 능가합니다.

Gurobi는 또한 Python에서 모델을 빌드할 수 있는 강력한 Python API와 함께 제공됩니다. 이 기능을 통해 모델러는 모델 구성 중에 Python의 모든 유용한 데이터 조작 라이브러리에 액세스할 수 있으므로 프로세스에 큰 도움이 됩니다. gurobi Python API의 데모로 배낭 문제를 모델링하는 방법은 다음과 같습니다.

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

예제를 실행하면 다음 출력이 표시됩니다.

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

호루스LP

HorusLP는 최적화 알고리즘 개발 경험을 기반으로 구축된 최적화 모델링 라이브러리입니다. 현재 사용 가능한 모델링 라이브러리에는 일반적으로 운영 연구의 상용 응용 프로그램에서 발생하는 복잡하고 다면적인 문제 유형을 처리하는 데 필요한 도구가 부족합니다.

대부분의 최적화 라이브러리는 저수준 명령형 인터페이스를 제공하지만 최적화 모델이 더 복잡해짐에 따라 복잡성을 관리하기 위해 더 나은 도구가 필요합니다. HorusLP는 이러한 복잡성을 관리하기 위한 고급 도구를 제공하는 라이브러리입니다. HorusLP는 또한 더 빠른 개발 및 반복을 허용하는 강력한 디버깅 및 보고 도구를 제공합니다.

핵심적으로 HorusLP는 최적화 모델과 관련하여 꼭 필요한 아키텍처를 제공하는 객체 지향 라이브러리입니다. Python 객체 지향 구문을 활용하여 HorusLP 라이브러리는 최적화 모델을 최적화할 수 있는 구조를 제공합니다. 그 결과 분리되고 모듈화되고 읽기 쉬운 코드베이스가 생성됩니다.

코드 샘플이 포함된 핵심 HorusLP 라이브러리에 대한 자세한 소개를 보려면 여기에서 자습서를 찾을 수 있습니다.

HorusLP-구로비 통합

HorusLP의 핵심 API는 최적화 모델 구축을 위한 편리한 고수준 API를 제공하지만, PuLP를 기반으로 구축되어 Gurobi를 솔버로 사용할 수 있지만 Gurobi의 고급 기능 중 일부에 액세스할 수 없습니다.

HorusLP-Gurobi는 Gurobi의 Python API를 사용하여 빌드된 HorusLP API 버전입니다. 이를 통해 사용자는 HorusLP API를 일관되게 유지하면서 Gurobi의 고급 기능에 직접 액세스할 수 있습니다.

HorusLP-Gurobi 개발을 이끄는 핵심 철학 중 하나는 HorusLP 핵심 API와의 일관성이었습니다. HorusLP의 미니멀한 구조를 일관되게 유지함으로써 오픈 소스 솔버 사용자는 Gurobi API를 설치하고 import 문을 전환하여 쉽게 Gurobi 사용으로 전환할 수 있습니다.

간단한 모델의 경우 HorusLP 기반 모델은 단순히 Python API를 명령적으로 사용하는 것보다 더 많은 코드 줄을 사용합니다. 그러나 개발 프로세스가 계속되고 모델이 더 복잡해짐에 따라 HorusLP API의 객체 지향 및 선언적 디자인은 디버깅 및 개발을 쉽게 만들 것입니다. 객체 지향은 또한 모델 정의가 목표, 제약 조건 및 변수 등을 중앙 집중화하고 명확하게 묘사하기 때문에 모델을 더 읽기 쉽게 만듭니다.

더 이상 고민하지 않고 몇 가지 코드 샘플을 살펴보겠습니다!

코드 예

기본 HorusLP API

HorusLP-Gurobi는 API를 일관되게 유지하므로 HorusLP 핵심 자습서의 코드는 가져오기를 간단히 변경하여 이식할 수 있습니다. 그러나 HoruLP-Gurobi를 사용하려면 Gurobi 옵티마이저와 Gurobi의 Python 인터페이스가 설치되어 있는지 확인해야 합니다. 여기에서 연락하면 구로비를 얻을 수 있습니다.

Gurobi를 설치하면 HorusLP-Gurobi로 코딩을 시작할 수 있습니다! 필수 패키지를 설치하여 시작하겠습니다.

 Pip install horuslp horuslp-gurobi

설치가 완료되면 HorusLP-Gurobi를 사용할 수 있습니다! 이전의 예시 배낭 문제를 상기하십시오. HorusLP-Gurobi를 사용하여 다음과 같이 문제를 모델링할 수 있습니다.

먼저 관련 라이브러리를 가져옵니다.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

일부 변수를 정의합니다.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

이제 제약 조건 클래스를 사용하여 제약 조건을 정의할 수 있습니다.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

그런 다음 비슷한 방식으로 목표를 구현할 수 있습니다.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

마지막으로 문제를 정의할 수 있습니다.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

그리고 문제를 인스턴스화하고 solve 함수를 호출합니다. 마법이 일어나는 곳입니다.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

코드를 실행하면 다음 출력이 표시됩니다.

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

첫 번째 부분은 Gurobi 솔버이고 두 번째 부분은 HorusLP의 출력입니다. 보시다시피 알고리즘은 입상과 뿔을 가져갈 것을 권장하며 결과적으로 17달러의 가치가 있는 14파운드의 항목이 생성됩니다.

Gurobi와 함께 HorusLP를 사용하는 이점 중 하나는 많은 정보를 "무료로" 얻을 수 있다는 것입니다. 각 변수의 값, 최종 목표 값, 제약 조건 값 등 일반적으로 개발 과정에서 살펴보고 싶은 많은 정보를 자동으로 계산하여 읽기 쉬운 형식으로 출력합니다.

HorusLP 코어에 대한 이전 기사를 읽은 경우 이것이 거의 동일한 API임을 알 수 있습니다. API를 단순하게 유지하기 위해 HorusLP 코어와 HorsLP-Gurobi의 인터페이스는 동일하며 슈퍼클래스 구현에서 추상화된 솔버 간의 차이점이 있습니다.

따라서 우리는 HorusLP의 소개를 이 간단한 예제로 남겨둘 것입니다. HorusLP의 고급 기능을 보여주는 더 복잡한 예제는 이전 기사에서 찾을 수 있습니다.

구로비 특징

구로비는 복잡한 문제를 해결하기 위한 많은 고급 기능을 제공합니다. 대부분의 기능은 Model 개체를 통해 액세스할 수 있습니다. Gurobi API와의 완전한 호환성을 허용하기 위해 모델 객체는 문제 클래스에서 model 로 쉽게 액세스할 수 있습니다.

예를 들어, 배낭 모델의 MPS 파일을 작성하려면 Gurobi에서 m.write('knapsack.mps') 와 같이 작성할 수 있습니다. HorusLP-Gurobi를 사용하는 동안 간단하게 다음을 수행할 수 있습니다.

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

그리고 작업 디렉토리에 MPS 파일이 표시되어야 합니다.

이 인터페이스를 사용하여 IIS 계산, 콜백 생성 또는 변수 힌트 제공과 같은 고급 Gurobi 기능에 액세스할 수 있습니다.

귀하의 서비스에 고급 Gurobi 기능

오늘 우리는 Gurobi Python API 위에 구축된 HorusLP 라이브러리 버전을 살펴보았습니다. 핵심 HorusLP의 보고 및 디버깅 기능 외에도 이제 Gurobi의 Python API와의 통합을 통해 원활하게 액세스할 수 있는 Gurobi의 모든 고급 기능에 액세스할 수 있습니다.

현재 Gurobi 사용자이거나 Gurobi 최적화 사용에 관심이 있는 사람이라면 HorusLP를 사용해 보시기 바랍니다! GitHub에서 예제 코드를 찾거나 제안을 하거나 HorusLP-Gurobi에 기여할 수 있습니다.