최적화 문제를 처음 접하다.

첫 메인 업무로 받았지만 백그라운드가 전무했다. 2주 간 학습하며 최적화문제가 무엇인지, 어떤 개념으로 작동하는지, 어떻게 python으로 작성하는지를 내가 알아볼 수 있게 정리할 필요를 느꼈다.

홈쇼핑 회사에선 방송 스케줄링도 중요한 업무로 꼽힌다. 어느 시간에 방송하느냐가 실제로 매출을 크게 좌우하기도 한다. 이번에 내가 맡은 과제는 방송 스케줄링이 잡힌 이후 어느 쇼핑호스트를 배정하는지 결정하는 것이었다. 사실 사람의 경험/감각이 최적화 프로그램 이상으로 괜찮은 결과를 낼 수 있겠지만, 최적화 문제는 앞으로 여러 분야에서 등장할 것으로 예상되다보니 파일럿 프로젝트 성격으로 진행된 것 같다. 앞으로 근로시간 축소에 따른 방송 스텝 배치 최적화 문제도 발생할 것 같고 방송 편성도 최적화 문제로 풀어야할 날이 올 것으로 예상한다.

최적화의 2가지 approach

경우의 수를 제한하는 제약식/목적함수를 최대(최소)화하는 방식이 있다. 대표 스케줄링 문제로 nurse scheduling이 있는데 대체로 제약식 조건을 통해 휴일/3교대 등등 옵션을 고려한다. 이번에 쇼핑호스트 배치 문제는 작성했던 조건이 10가지가 넘었다. 이를 제약식만으로는 작성이 어려운 부분이 있어 목적함수로 쇼핑호스트 적합도라는 지표를 이용했다.

문제 해결 과정

먼저 최적화 툴로 google or-tools/ibm cplex를 검토했다. or-tools는 연산 속도가 비교적 느려서 cplex로 진행했는데, 비용 측면에서도 큰 걱정이 없던 것이 ibm에서 saas로 decision optimization는 cplex와 동일한 알고리즘을 api로 제공하는데 사용료가 10$ 단위다. 본인은 python으로 제약식을 작성했는데 pandas를 활용하여 쉽게 접근할 수 있었다.

api통신을 위해 python 라이브러리 docplex를 써야하는데 고유의 문법이 tensorflow와 유사한 느낌이었다. 실질적으로 문제를 해결하기 위해 필요한 함수는 단 2가지, model.sum과 model.add_constraint 밖에 없었다. 코드의 질은 고려하지 않고 로직을 정확히 적용하는 것만 생각하면 어렵지 않게 접근할 수 있는 것 같다.

이번 경험을 통해 얻은 한 가지 팁이있다면 다양한 조건 간에 상충하는 경우를 쉽게 제약하는 방법이다. binary형태의 target변수를 쓰고 있었기 때문에 조건식이 성립된 확률을 sum/len으로 표현할 수 있었다. 제약식을 적용할 때 sum/len을 기준으로 한다면 부분적으로 제약식을 적용할 수 있었다. 이렇게 다소 열어둠으로서 제약 조건 간의 상충을 방지하고 목적식을 통해 원하는 결과가 나오도록 했다. 중요한 조건은 목적식의 계수를 크게 조정하여 원하는 결과를 얻을 수 있었다.

다음에는

조건식의 priority를 설정하는 메소드는 있으나 실제 어떻게 작동하는지는 모르겠다.

relax 메소드는 제약조건에서 lower bound나 upper bound를 조정하는 것으로 보인다. model var 타입을 적극 활용하는 로직이 더 이해가 잘되고 코드도 쉬울 것 같다.