Mathematical Optimization - 수학적 최적화

Mathematical Optimization

수학적 최적화란?

수학적 최적화-mathematical optimization이 무엇인지 설명하는 것으로 포스팅을 시작하겠습니다.

수학적 최적화란?

Objective function에 기반하여 best solution을 찾는 방법

수학적 최적화의 여러 모델들은 일반적으로 반드시 만족해야 하는 constraint와 objective function으로 구성는데요, 여기서 objective function과 constraint란 다음과 같습니다.

Objective function : want to maximize of minimize(또는 거꾸로)
Constraint : condition of problem

간단히 말해서 목적 함수 (Obj function)는 우리가 최대화(또는 최소화)하고 싶은 expression이며 제약조건(Constraint)은 우리가 목적함수를 만족하는 과정에서 고려해야 하는 제약들입니다.

이러한 목적함수와 여러가지 제약조건들을 통하여 우리는 Optimal Solution을 구할 수 있는데요, 이렇게 구한 Optimal Soultion이 유의미한 값을 갖기 위해서는 목적함수와 여러가지 제약조건들이 우리가 해결하고자 하는 문제의 요구사항을 충분히, 정확히 반영해야만 합니다.
따라서, 우리는 수학적 최적화의 algebraic 모델을 구축하기 위해서는 다음과 같은 Step을 통하여 모델을 구축하고자 합니다.

1. a set of variable : 문제에 대한 해결책으로 찾아야하는 미지수
2. a set of constraint : 변수간의 관계로 문제 요구사항을 나타내는 방정식 또는 부등식
3. an objective function : target problem에서 total cost나 profit과 같이 결정된 defined variable의 표햔식

이 과정을 통하여 우리는 비용 최소확 또는 이윤 최대화와 같은 optimal solution을 구할 수 있습니다.

Linear Programming

수학적 최적화에는 여러종류가 있습니다. 그 중 가장 기본이 되는 모델이 바로 Linear Programming입니다!

선형 최적화 문제에서의 목적 함수와 제약 조건은 모두 linear expression입니다. 따라서, 선형 최적화의 가장 큰 특징은 해결하기 쉽다는 것인데요, 바로 아래 선형 최적화 문제의 예시에서 자세히 알려드리도록 할게요!

maximize 15x1 + 18x2 + 30x3
subject to: 2x1 + x2 + x3 <=60
	    x1 + 2x2 + x3 <=60
         	       x3 <=60
               x1, x2, x3 >=0

첫 번째 표현식 [15x1 + 18x2 + 30x3]은 최대화 할 함수를 정의하며, 이것을 objective function이라고 말합니다!
두 번째 표현식은 subject해야하는 조건들이 바로 제약 조건입니다. 여기서, [x1, x2, x3 >=0]는 변수가 음수가 아니게 하는 조건이라 하여 Non-negativity constraint라고 부르기도 합니다. 일반적으로 Optimization Problem을 풀 때 모델의 변수는 음이 아닌 실수로 정의되기 때문에 해당 조건 첨가된 것입니다.

해당 제약 조건들을 더하고 빼는 둥 수학적 계산을 통하여 우리는 여러가지 Solution을 구할 수 있는데요, 실행 가능한 Solution들 중 목적 함수를 최대화하는 value를 바로 Optimum(최적 솔루션)이라고 합니다.
이 문제를 계산해보면 Optmum은 1230이며 x1=10, x2=10, x3=30이라는 값을 구할 수 있습니다.

Optimum을 구하기 위하여 일일이 손으로, 수식으로 계산하는 것은 가능합니다. 매우 귀찮을 뿐. 따라서 우리는, 파이썬의 SCIP모듈을 통하여 이 문제를 해결하는 방법을 알아보겠습니다.

Linear_Programming to SCIP

1. 모듈 install

먼저, SCIP 모듈을 설치해줍시다. 저는 이게 세상 오래걸렸는데요, Conda Prompt를 이용해서 설치를 하려니 pip install 명령어가 오류가 생기더라고요,,, Anaconda를 사용하시는 분들은 아래와 같이 치할 수 있습니다!

conda install -c conda-forge pyscipopt

2. 모듈 import

SCIP 모듈을 불러오고, 이를 model로 정의하여 사용하고자 합니다. 대부분의 Optimization Solver들을 이 모듈을 model로 정의하지만, 여러분이 독고다이의 길을 걷고 싶다! 나는 인싸다! 하시는 분들은 다른 표현으로 사용하셔도 상관없습니다 ㅎㅎ^^77

from pyscipopt import Model

3. Model 선언

다음은 이제, 우리가 사용할 최적화 모델을 만드는 것입니다. Model(pyscipopt)에서 가져온 클래스로 이를 호출할 수 있습니다. 이번 챕터에서 우리는 Linear optimization 모델을 다룰 예정이기에, Simple linear optimization 모델을 사용하도록 하겠으며, Model의 이름을 model이라고 지정하겠습니다.

model = Model('Simple linear optimization')

4. 변수 선언

최적화 문제를 해결하기 위하여 우리는 여러가지 변수를 선언할 것입니다. 변수는 아래와 같이 선언할 수 있습니다.

addVar(name='', vtype='C', lb=0.0, ub=None, obj=0.0, pricedVar = False)

여기서의 name은 변수의 이름, vtype은 변수의 유형, lb는 하한, ub는 상한, obj는 목적함수의 계수, pricedVar은 컬럼 생성을 의미합니다. 여기서 pricedVar은 'Bin packing and cutting stock problems'를 해결할 때 사용되며 이는 추후에 언젠간 설명드리도록 하겠습니다,,ㅎㅎ

좋아요! 그럼 이제, 본격적으로 문제를 해결해 보도록 해요!
변수 x1, x2, x3를 선언해보도록 하겠습니다.

x1 = model.addVar(name='x1', vtype='C', lb=0.0, ub=None, obj=15)

addVar method를 이용하여 변수를 선언할 때 x1처럼 옵션 명을 일일이 입력하여 선언할 수 있습니다. 이것이 기본 선언 방법입니다.
그러나 귀찮습니다. 언제 이걸 일일이 다써 그냥 손으로 풀고 말지.
그래서 우리는 아래와 같이 '이름, 유형, 하한, 상한, 목적함수의 계수'의 순서로 값을 입력하여 변수를 선언할 수 있습니다.

x2 = model.addVar('x2', 'C', 0, None, 18)

그치만 이것도 귀찮습니다. 우리는 최대효율을 이끌어내는 optimization solver입니다. 극한의 이득을 보기 위하여 x3와 같이 반드시 들어가야하는 obj의 계수만을 따로 선언하여 변수를 선언할 수 있습니다.

x3 = model.addVar(obj = 30)

여기서 중요한 것은 바로 default값입니다. 옵션 name의 default는 선언한 변수명이며, vtype은 연속함수를 나타내는 'C'입니다. 또한, lb는 non-negative를 위하여 0.0이, 상한은 정해지지 않은 무한대를 나타내는 None이, 마지막으로 obj는 1이 default값으로 설정되어있습니다. 이를 이용하면 우리 모두 극한의 이득을 취할 수 있으니 꼭 기억해 둡시다!

5. 제약조건(Constraint)선언

제약 조건을 선언해보도록 하겠습니다. 제약조건은

model.addCons(~~~~~ <= ~~~)

으로 선언할 수 있습니다. 한번 해보죵

c1 = model.addCons(2*x1 + x2 + x3 <= 60)
c2 = model.addCons(x1 + 2*x2 + x3 <= 60)
c3 = model.addCons(x3 <= 30)

네, 위의 문제에서 분명 제약 조건이 4개였는데 왜 3개만 선언했냐고 묻고 싶은거 다 앎니다. 사실 귀찮아서요ㅋㅋ
이게 아니고, 마지막 제약 조건은 분명 non-negativity constraint로 각각의 변수가 음수가 되지 않도록 걸어준 제약조건 이었습니다. 그러나 우리는 이미 변수를 선언할 때, 하한을 0으로 제약해두었기 때문에 이를 생략할 수 있는 것입니다. 그치만 여기서 더 축약할 수 있습니다. 바로

c3 = model.addCons(x3 <= 30)

이 부분을 생략하는 것인데요, 자세히 보면 여기서의 제약은 x3가 30이하이어야 한다 라고 해석할 수 있습니다. 이는 곧 x3의 상한이 30이라는 것을 의미하는데요. 그렇다면 애당초 변수를 선언할 때,

x3 = model.addVar(up=30, obj = 30)

이렇게 선언을 해준다면, x3는 30초과의 값을 가질 수 없기 때문에 3번째 제약조건 c3를 생략할 수 있습니다. 근데 그냥 씁시다. 나중에 문제 풀때 헷갈립니다. 이렇게 할 수 있다는 것만 알아두시면 좋을 것 같네요!

6. Objective Function 선언

변수도 선언했고, Constraint도 선언을 했으면, 이제 마지막으로 Objective Funcion을 선언하도록 하겠습니다.

setObjective(expression, sense="minimize", clear="true"):

Obj Function은 이렇게 선언할 수 있는데요. expression이 obj function의 식이며 sense가 최대화할지, 최소화할지를 나타냅니다. 마지막으로 clear은 다른 모든 변수의 계수를 0으로 설정한다를 의미합니다. 그럼 이 문제의 Obj Function을 선언하겠습니다.

model.setObjective(15*x1 + 18*x2 + 30*x3, 'maximize')

이번 문제는 Maximize문제이니 sense옵션에 maximize를 선언하였으며, 각 옵션의 이름은 생략하겠습니다. 귀찮아 생략 조아

7. Optimize

네, 다왔습니다. 이제 최적화 버튼만 띡 눌러주면 됩니다.

model.optimize()

띠디디디딕
띵!

8. Optimal value

끝났습니다. 우리(의 컴퓨터)는 이 문제를 풀어버렸는데요. 이를 우리한테 좀 알려줬으면 좋겠습니다. 이 답을 표현하는 방법은 아래와 같습니다.

print("Optimal value :", model.getObjVal())

띠딕 딕

Output
Optimal value : 1230.0

손으로 풀어본 것과 같은 값이 나오네요! 좋습니다.

9. Values

마지막으로 각 변수의 값도 알고 싶습니다. 노트북님 알려주세요 Plz

print("x1 :", model.getVal(x1))
print("x2 :", model.getVal(x2))
print("x3 :", model.getVal(x3))

뚜뚜 띡!

Output
x1 : 10.0
x2 : 10.0
x3 : 30.0

예상대로군요. 나 사실.. 천재였을지도..?

10. 매무리

사실 저는 마무리 말 잘 안씁니다. 귀찮잖아요. 이번에 작성하는 이유는 9번으로 끝나는게 너무 불---편하더라고요. 그래서 마무리 멘토 조지고 가겠습니다.
자 여러분! 오늘은 처음으로 Optimization의 기본 모델 Linear Programming에 대해서 알아 봤습니다.😎 Optimization은 되게 재미있는 분야인 것 같아서 열심히 공부해보고자 하는데요. 제가 아직 하수라 틀린 설명이 있을 수 있을 것 같습니다 😥 틀린 부분 피드백해주시면 반영하도록 하겠습니다! 모두 고생하였고요, 다음 챕터 Integer Programming애서 다시 찾아뵙겠습니다. 다들 뱌뱌😜

Reference

https://scipbook.readthedocs.io/en/latest/intro.html#linear-optimization