2. Integer Programming - Optimization

Daehyuk·2021년 7월 1일

Operation Research

목록 보기

2/2

Integer Programming

이번에는 Integer Programming에 대해 알아보도록 하겠습니다.
저번 시간에는 Linear Programming에 대해 알아보았는데요, 이번에는 간단한 문제를 예시로 들어 설명해보도록 하겠습니다.

대혁이의 농장에는 닭과 거북이와 문어가 총 32마리가 있으며 이들의 다리의 총합은 80개이다. 거북이와 문어의 최소 개체 수는 몇 마리인가?

이 문제를 보면 어? Linear Programming으로도 구할 수 있는거 아니냐?라고 할 수 있겠는데요. 음... 일단 한번 해보도록 하겠습니다.

mniimize y + z
subject to:  x +  y +  z =32
	    2x + 4y + 8z =80
             x, y, z >=0

이를 계산해 보았을 때, x=29.3333 , y=0, z=2.6667이라는 Optimum Solution을 구할 수 있습니다. 그러나, 여기는 농장입니다. 일반적으로 생각해 보았을 때, 닭 한마리는 튀겨서 치킨으로 만들어버린 뒤 무자비하게 다리를 뜯어서 접시에 두고, 문어 한마리는 3등분을 하여 다리 2개와 3분의 2를 초장에 찍어먹어 버린다면 ~~맛있겠죠.~~
그러나 살아있는 친구들을 무자비하게 학살할 수는 없기에 우리는 Ingeter Solution을 구해야합니다. 따라, 문제는

mniimize y + z
subject to:  x +  y +  z =32
	    2x + 4y + 8z =80
             x, y, z >=0, integer

이렇게 정의해줘야 합니다. 가릿?

그럼, 이 문제 또한 파이썬의 SCIP모듈을 통해서 구해보도록 하겠습니다.

1. Model Import

먼저, 모델을 불러오겠습니다.

model = Model('Simple linear optimization')

호잇

2. 변수 선언

이번에는 변수를 선언하고자 하는데요. 여기서 집중!

x = model.addVar(vtype='I')
y = model.addVar(vtype='I')
z = model.addVar(vtype='I')

저번 Linear Optimization에서의 변수 선언과의 차이점이 보이시나요?? 네, 그렇습니다. 바로 vtype이 I(즉, Integer)라는 것입니다. 닭을 치킨으로 만들~~고싶다~~ 수 없으니 변수의 타입을 I형으로 바꿔주는 것입니다. 변수가 연속하는 숫자일 때는 C, 정수 타입일때는 I, 0과 1의 binary 타입일 경우에는 B을 vtype으로 지정해줍시다. 이 문제에서는 I!

3. 제약 조건

이번에는 제약 조건을 걸어줄게요!

model.addCons(x + y + z == 32, "Heads")
model.addCons(2*x + 4*y + 8*z == 80, "Legs")

저번과는 조금 다르게 선언하였는데요, 저번에는 c1 = ~~~ c2 = ~~~와 같이 제약조건에 이름을 선언해주었습니다. 그러나 이번에는 제약조건 안에 있는 name method를 이용하여 해당 조건의 이름을 선언하였습니다.

4. 목적 함수

우리의 목적은 거북이와 문어의 개체 수를 최소화하는 수를 구하자입니다. ~~난 문어 좋은데 맛있어~~

model.setObjective(y + z, 'minimize')

이번 문제는 최소화하는 수를 구하는 것이기에, sense = 'minimize'를 선언하여 최소화를 구하겠습니다.

5. 최적화(Optimize)

변수 선언 완료.
제약 조건 선언 완료.
목적 함수 선언 완료.
그럼 우리가 할 것은? 최적화 ㄲㄲ

model.optimize()

호잇!

6. Solution

최적화까지 완료했습니다. 노트북님 정답을 알려주십쇼.

if model.getStatus() == "optimal":
    print("Opimal value :", model.getObjVal())
    print("Solution :")
    print("x = ", model.getVal(x))
    print("y = ", model.getVal(y))
    print("z = ", model.getVal(z))
else :
    print('Problem could not be solved to Optimality')

이전과는 조금 다르게 표현하였는데요, 코드를 잘 보세요!

if model.getStatus() == "opimal":

이 부분이 해당 문제가 최적화가 가능한지, 잘 되었는지 나타내는 문장입니다. 이 문제가 불가능한 문제라면 model.getStatus()는 'infeasible'이라는 값을 갖게 됩니다.

7. Code Summary

이 코드들을 한 블럭으로 작성하면

model = Model('Simple linear optimization')
x = model.addVar(vtype='I')
y = model.addVar(vtype='I')
z = model.addVar(vtype='I')
model.addCons(x + y + z == 32, "Heads")
model.addCons(2*x + 4*y + 8*z == 80, "Legs")
model.setObjective(y + z, 'minimize')
model.optimize()
if model.getStatus() == "optimal":
    print("Optimal value :", model.getObjVal())
    print("Solution :")
    print("x = ", model.getVal(x))
    print("y = ", model.getVal(y))
    print("z = ", model.getVal(z))
else :
    print('Problem could not be solved to Optimality')