박사 졸업하고 10년 조금 넘는 세월 동안 논문을 이것저것 썼는데, 그중에서 대단하지는 않지만 과정이 재미있었던 논문이 하나 있다. 별거 아닌 것 같아도 다시 보면 나 혼자 나름 뿌듯해할 수 있는 논문이다. 시작은 이 논문이다.
- Bertsimas, D. and Sim, M., 2003. Robust discrete optimization and network flows. Mathematical programming, 98(1-3), pp.49-71.
2003년에 출판된 논문인데, OR 분야에서는 아주 드물게 1,700회 이상의 인용 수를 자랑하며 로우버스트 옵티미제이션(robust optimization)가 크게 유행하는 데 중요한 역할을 했다. 박사 과정 시절 열심히 읽었던 논문이다.
2009년 여름에 한국 들어가서 여기저기 돌아다니며 술 마시다가 전북대학교 산업공학과의 이태한 교수님을 만나게 되었다. 이런저런 인연으로 연락을 주고받다가, 이태한 교수님께서 2011년에 연구년을 버팔로로 오시게 되었다. 같이 밥 먹고 술 먹고 이런저런 이야기를 같이하다가 로우버스트 옵티미제이션 분야에 둘 다 관심이 있다는 것을 알게 되었고, 또 밥과 술이 쌓이더니 논문을 한 편 같이 썼다.
이태한 교수님이 이 논문 이야기도 해주셨다.
- Park, K.C. and Lee, K.S., 2007. A note on robust combinatorial optimization problem. Management Science and Financial Engineering, 13(1), pp.115-119
『경영 과학과 금융 공학(Management Science and Financial Engineering, MSFE)』은 한국경영과학회에서 발행하던 저널인데, 지금은 폐간되어 『한국경영과학회지(Journal of the Korean Operations Research and Management Science Society)』로 통합되었다. 심지어 저널의 이름도 위 논문이 출판될 때는 ‘경영 과학 국제 저널(International Journal of Management Science)’이었던 것 같은데, 그 이름으로는 검색도 잘 안 된다.
아무튼 이런저런 사연에다가 미국에서 대학원 교육을 받은 나는 아무래도 잘 모를 수 밖에 없던 논문이었다. 위 논문의 제2 저자이신 이경식 교수님은 현재 서울대학교 산업공학과에 계시는데, 이태한 교수님과는 박사과정을 같은 연구실에서 마쳤다. 그래서 이태한 교수님께서 위 논문을 알고 계셨던 것.
벌치마스와 심의 2003년 논문에는 어떤 문제를 n+1번 풀면 로우버스트 옵티미제이션 문제의 최적화를 구할 수 있다는 내용이 들어있다. 박경철과 이경식의 2007년 논문에서는 그 숫자를 n+1-\Gamma번만 풀면 된다는 것을 보였다. 물론 \Gamma값에 따라 다르지만, 어쨌든 계산량이 조금 줄어든다. 작지만 재미있는 결과이다.
이태한 교수님께서 말씀하시길 자기가 그냥 계산하다 보니 계산을 한 번 더 줄일 수 있다는 것을 발견했다고 하셨다. 그러니까 n-\Gamma. 이걸 어디다가 출판하기도 그렇고 해서 그냥 본인만 알고 계신다고 했다. 그러다가 이태한 교수님은 전북대학교로 돌아가셨고, 나는 여전히 버팔로에서 빙판길을 운전하며 살았다.
2013년 어느 날 구글 스콜라가 다음 논문을 알려주었다. ‘Robust Optimization’을 알림 키워드로 설정해 두었기 때문이다.
- Álvarez-Miranda, E., Ljubić, I. and Toth, P., 2013. A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems. 4OR, 11(4), pp.349-360.
4OR은 분기별 운영 연구 저널(Quarterly Journal of Operations Research)의 줄임말로 벨기에, 프랑스, 이탈리아의 OR 학회가 연합해서 발간하는 저널이다. 그러니까 MSFE 마냥 로컬 오스카 저널이다. 이 논문에는 이런저런 다른 결과도 있지만, 주로 위에 말한 계산을 n+2-\Gamma번만 하면 된다는 내용이었다.
박경철과 이경식의 2007년 논문보다 하나 더 많네? 심지어 박경철과 이경식의 2007년 논문을 모르고 있다. 해외에서는 검색도 잘 안 되고, 구하기도 어려운 한국 학회에서 발행하는 저널이어서 그랬던 것 같다.
한국 학자가 한국 학회 저널에 발행한 논문의 결과가 무시당한 것 같은 마음도 들고 이태한 교수님의 n-\Gamma 아이디어를 논문으로 제출하면 좋겠다는 생각이 들어서 이태한 교수님의 아이디어를 토대로 내가 그것의 응용한 내용을 덕지덕지 더럽게 붙여서 같은 저널 4OR에 제출했다. 물론 박경철과 이경식의 2007년 논문을 인용(cite)했다.
결과는 거부(Reject) 및 재제출(resubmit). 심사평을 살펴보니 대체로 논문 내용이 더럽다…는 내용이었다. 그러니까 하나의 아이디어로 잘 정리가 되지 않았다는 것. 사실 이태한 교수님의 아이디어에 내가 덕지덕지 더럽게 붙인 내용은 필요 없는 부분이었다. 그렇다고 계산 한 번 줄이는 내용으로 논문을 마무리하기에는 좀 부족해 보여서 고민이 많았다. 그래서 일단 버려두었다.
어느 날 버팔로에서 자동차 엔진오일도 갈고 점검도 받기 위해서 자동차 딜러샵에 딸린 정비소를 방문했다. 두어 시간 딜러샵에서 공짜 커피도 마시고 쿠키도 먹으면서 밀린 일을 처리하다가, 이 논문을 어찌해야 할까 ‘어쩌지 어쩌지’를 반복하면서 머리를 싸매고 있던 중, 새로운 발견을 했다.
논문을 깔끔하게 쓰기 위해서 더러운 것들 정리하다 보니 \lceil \frac{n-\Gamma}{2} \rceil + 1 번으로 계산량을 줄일 수 있다는 것을 발견한 것이다. 그러니까 대략 계산량을 반으로 줄일 수 있다는 것. 덕지덕지 붙였던 것 다 떼어내고 새로운 결과로 정리해서 다시 제출했고 논문은 출판되었다.
- Lee, T. and Kwon, C., 2014. A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty. 4OR, 12(4), pp.373-378.
이 내용들을 다 정리해보면 다음 표와 같다.
별 내용은 없지만 아무튼 개인적으로는 흥미로운 과정 끝에 발견한 것이라 이 논문에 애착이 조금 있다. 아마 수학이나 과학하시는 분들께는 일상적으로 발생하는 일일 것 같다. 논문 내용을 바탕으로 줄리아 패키지(Julia Package)도 만들었다.
역시 큰 의미는 없는 소프트웨어다.
이 글을 쓰느라 알바레즈 미란다 외의 2013년 논문을 다시 살펴보는데, 제2 저자의 이름이 눈에 들어왔다. 이바나 류비치(Ivana Ljubić). 작년 INFORMS 학회에서 내가 조직했던 세션에 무턱대고 이메일 보내 초청했던 분이다. 바일레벌 옵티미제이션(Bilevel optimization) 및 여러 디스크릿 옵티미제이션(discrete optimization) 문제로 잘 알려진 분이시다. 재밌다. 이 바닥 아주 좁고 세상 돌고 도는구나.
세 줄 요약
- 밥도 먹고 술도 먹다 보면 논문도 쓴다.
- 더러운 것은 청소하자.
- 뭐라도 하다 보면 될 때가 있다.
원문: 잡생각 전문 블로그
