이차계획법에 기반한 소파 이동 문제의 상한선 개선

Improving Upper Bound for the Moving Sofa Problem Based on Quadratic Programming

소파 이동(moving sofa) 문제는 직각의 모서리를 끼고 있는 폭이 1인 복도를 통과할 수 있는 최대 단면적 소파를 찾는 이산기하 분야의 문제로, 1966년 Moser에 의해 제시된 이후 아직 미해결 문제로 남아 있다. 현재까지 알려진 최대 단면적의 최대 하한은 1992년 Gerver에 의해 발견된 2.2195...이고 최소 상한은 2018년 Kallus & Romik에 의해 증명된 2.37이다. 최소 상한 2.37이 다소 느슨한 것으로 보이는 반면에 최대 하한 2.2195...을 향상할 여지가 작다는 실험적 근거가 제시되었는데, 본 연구에서는 이 점에 주목하여 상한을 Gerver의 최대 하한에 좀 더 근접하도록 낮추었다. 이를 위해 기하학적 분기 한정법(geometric branch-andbound)과 이차계획법(quadratic programming)에 기반한 최적화 알고리즘을 구성하고, 알고리즘의 효율적 탐색을 위해 다양한 기하학적 성질을 증명하였다. 약한 기하학적 가정하에서, 제안한 최적화 알고리즘을 이용하여 개선된 상한 2.3361을 Kallus & Romik에 비해 훨씬 짧은 계산시간으로 얻었다.

The moving sofa problem is a problem in discrete geometry that involves finding a shape with the maximum area that can pass through a right-angled corner in a hallway with unit width, and has remained an open problem since it was posed by Moser in 1966. The largest lower bound on the maximum area known to date is 2.2195..., found by Gerver in 1992, and the smallest upper bound is 2.37, proved by Kallus and Romik in 2018. While the minimum upper bound of 2.37 appears to be somewhat loose, experimental evidence suggests that there is little room for improvement in the largest lower bound of 2.2195.... In this study, we aim to lower the upper bound to be closer to Gerver’s maximum lower bound. For this purpose, we construct an optimization algorithm based on geometric branch-and-bound and quadratic programming, and prove various geometric properties for efficient search of the algorithm. Under a reasonable geometric assumption, the proposed optimization algorithm obtains an improved upper bound of 2.3361 with much shorter computation time than Kallus and Romik.