[OR-Tools 스터디] Linear Optimization

Overview

linear optimization(또는 linear probramming)은 선형 관계에 있는 set으로 모델된 문제에 대해 best solution을 계산해주기 위한 것.

이러한 problem들은 과학, 공학적인 분야에서 많이 발생한다.

("programming"이라는 단어가 계산하는 사람이라는 의미로 잘못 오해되었었다.

여기서 programming은 컴퓨터 언어로 프로그래밍 한다기보다는 "the arrangement of a plan"이 더 적합하다)

 

Tools

구글에서는 LP problem을 풀기위한 방법들을 제공해줌

• MPSolver (이건 OR-Tools 설치가 요구됨)
• Linear Optimization add-on for Google Sheets : spreadsheet에 변수들과 constraint를 입력하면 linear optimization 문제들을 풀어줌 (해당 링크 연결이 오류남)
• Linear Optimization Service in Google Apps Script : 문제를 풀기 위해 함수를 직접 만들어야함. 이 방법의 경우 Glop(google linear optimization)에 의존함. 모든 실수값을 가질 수 있으며, 만약 어떠한 변수가 정수로 제약되어 있는 경우에는 SCIP라는 툴을 사용하면 됨. (해당 링크 연결이 오류남)

 

MPSolver Interface

optimization을 위한 구글의 오픈 소스 소프트웨어인 OR-Tools는 linear programming problem과 mixed integer programminng problem을 풀기 위한 MPSolver wrapper를 제공해준다. 

 

pure integer programming problem을 풀고자 할 때는 CP-SAT solver를 쓰면 된다. (추후 다룰 예정)

 

Examples

MPSolver를 사용하여 풀 수 있는 문제들은 다음과 같다 :

• Solving the Stigler diet problem using Glop
• Solving an LP problem using Glop
• Solving a MIP problem using SCIP
• Solving a bin packing problem using SCIP
• Solving an assignment problem using CP-SAT
• Using arrays to define a model

Common tasks

다음의 section은 LPs와 MIPs를 푸는 것과 관련된 common task를 묘사해둔 것이다.

 

Time limits

#아래의 코드는 Glop를 사용하여 문제를 풀 때 15ms의 시간 제약을 거는 방법을 보여준다. 

solver.set_time_limit(15)

 

 

 

Reference : 

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

선형 최적화  |  OR-Tools  |  Google Developers

https://developers.google.com/optimization/lp/mpsolver

MPSolver 인터페이스  |  OR-Tools  |  Google Developers