Combination Optimization(조합 최적화 연구)
배경
수 많은 케이스들을 더해 각 케이스들을 조합해 목적값을 찾는데 이 때 각 케이스의 금액이 가장 저렴한 케이스를 찾아야 할 때 조합 최적화 방법이 필요합니다.
최적의 조합
연구 과제
먼저 조합을 하려면 조합하기 위한 경우의 수를 찾아내야 합니다.
예를 들어 A, B, C, D 특성이 있다고 하면,
A, B, C 는 조합에 사용될 케이스이고 D 는 가격 특성이라고 하면 A, B, C 의 값 범위는 0~1로 동일하다고 하면 A, B, C 가 합쳐져 만들어지는 케이스를 구해보면,
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
0~1(2개) X 2 X 2 => 8개의 케이스가 생깁니다.
이와 같은 케이스 생성 방법은 Cartesian Product를 활용하여 쉽게 도출할 수 있습니다.
이제 A, B, C 간의 조합을 통해 목적값을 구한다고 생각해 보면,(아래는 목적값)
| A | B | C |
|---|---|---|
| 2 | 2 | 1 |
이 목적값을 구하기 위해 아래와 같은 여러 개의 가능한 조합들이 생깁니다.
| A | B | C |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| A | B | C |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 1 | 1 |
조합은 2개의 행으로 조합될 수도 있고 3개의 행으로 조합될 수도 있습니다. 이번 목적값과 데이터셋에서는 불가하지만 1개의 행으로도 충족하는 상황도 있습니다. 이 때 아래와 같이 D 컬럼이 가격이라고 하고 행 간 조합을 통해 합산된 가격이 가장 저렴한 조합을 찾는다고 해보면,
| A | B | C | D |
|---|---|---|---|
| 0 | 0 | 0 | 5 |
| 0 | 0 | 1 | 3 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 6 |
| 1 | 0 | 1 | 4 |
| 1 | 1 | 0 | 3 |
| 1 | 1 | 1 | 1 |
가격이 위와 같을 경우 위의 조합이 가능할 때 합산 금액은 첫번째는 7, 두번째는 4인데 조합이 가능한 케이스가 2개의 조합뿐이라고 할 때 두번째 조합이 최적의 조합입니다.
| A | B | C | D |
|---|---|---|---|
| 0 | 1 | 0 | 2 |
| 1 | 0 | 1 | 4 |
| 1 | 1 | 1 | 1 |
| A | B | C | D |
|---|---|---|---|
| 1 | 1 | 0 | 3 |
| 1 | 1 | 1 | 1 |
하지만 만약 조합 컬럼 개수가 10개 정도 된다면 그리고 컬럼마다의 값의 범위가 0~9 정도 된다면 Cartesian Product를 통해 10^10개의 조합 재료가 생깁니다. 이 조합 재료의 총 진부분집합(공집합을 제외한 부분집합) 개수는 자그마치 2^10000000000개가 됩니다. 2의 백억승이 되는데 16000승만 되도 이미 5천 자리를 넘어서게 됩니다. 이 같이 모든 조합을 구하는 방식은 조합 방식에 따라 가능, 불가능 여부를 따지게 됩니다.
목적 조합
위와 같이 모든 조합 케이스를 다 만드는 순간 왠만한 프로그램은 멈추거나 몇 일 뒤에 결과가 나는 등 아주 안 좋은 결과를 얻을 수 있습니다.
그래서 위의 그림과 같이 모든 조합을 만들고 목적조합을 찾는게 아닌 역으로 조합의 목적값을 생성하는 방식으로 조합을 만들게 됩니다.
| A | B | C | D |
|---|---|---|---|
| 0 | 0 | 0 | 5 |
| 0 | 0 | 1 | 3 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 6 |
| 1 | 0 | 1 | 4 |
| 1 | 1 | 0 | 3 |
| 1 | 1 | 1 | 1 |
2개 조합으로 생각하면 목적값이 111 이라고 가정하면, 첫행과 마지막행, 그리고 두번째행과 마지막에서 두번째행, ... 이런식으로 가운데까지 조합이 생깁니다.
3개 조합으로 생각하면 첫행과 둘째행과 마지막에서 두번째 행, 첫행과 세번째행과 마지막에서 세번째행, ... 이런식으로 조합이 생깁니다.
위와 같이 목적값에 따라 행열 구조에서 대각선의 일정 규칙을 지닌 조합들을 찾아낼 수 있습니다.
이렇게 하면 모든 조합 케이스를 찾는 말도 안되는 조합 개수를 생성해 목적값 충족하는지 여부를 조합들 하나 하나 계산해 봐야 하는 프로세스를 제외시키고 조합 마다의 가격 비교만 하면 최적의 조합을 찾아낼 수 있습니다.
다른 방법 소개
위의 조합 방법은 Google OR-Tools를 활용해 간단하게 해결할 수도 있습니다.
Google 신의 OR-Tools는 원래 C++로 작성됐는데 python으로 사용 가능하고 선형 계획법, 혼합 정수 계획법, 제약 조건 프로그래밍, 차량 경로 지정 및 관련 최적화 문제를 해결하기 위해 개발한 무료 오픈 소스인데 여기서 cp_model을 활용해 해당 문제들을 해결합니다.
아래는 pandas를 활용한 Cartesian Product로 데이터 셋을 활용하고 랜덤 가격을 적용한 후 Google Ortools의 cp_model을 활용해 간단히 조합 찾아내는 예제를 만들어낸 페이지 예시입니다. 숫자를 입력하고 랜덤 을 누르면 입력한 숫자가 목적값이 되고 랜덤으로 생성된 가격의 최적 조합을 찾아냅니다.(react + fastapi 조합)
현재는 heroku 유료화로 백엔드가 정상동작되지 않아 추후 정상화할 예정
결론
위의 조합을 이용해 bin-packing 화면을 구현하려 했지만 시간도 늦었고 해야될 다른 작업들이 많아(귀찮아서) 하진 않았습니다. 이런 최적 조합을 찾는 방법들은 좀 더 최적화된 방법들을 사람들이 만들어낼 텐데 더욱 좋은 기술들이 나와 세상에 수 많은 최적 조합이 필요한 경우를 가장 효율적으로 해낼 수 있다면 좋을 것 같습니다.
혹시나 내가 최적의 조합을 만드는 알고리즘을 성장시키는데 일조한다면 그 또한 뿌듯할 거 같습니다.