Bubosang Problem as a Mixed Binary Quadratic Problem : The Uncapacitated Case

Abstract

부보상 문제는 비순환 유향 그래프 상에서 출발, 도착 마디를 잇는 경로와 그 경로 상의 흐름을 결정하는 문제이다. 부보상은 도시 1에서 n까지 이동하면서 각 도시를 경유하 거나 지나치며, 경유하는 도시에서만 상품을 매매할 수 있지만 이동 거리와 상품량에 따른 비용 또한 지불해야 한다. 이 때, 부보상은 자신의 수익, 즉 총 상품의 판매량에서 얻는 수익과 지불 비용의 차를 최대화하고자 한다. 본 연구에서는 용량 제약이 없는 경우만을 다루며 기존 부보상 문제를 혼합이진이차문제으로 재모형화하여 분지절단법 으로 문제를 푼다. 이 때 목적 함수를 볼록화하고 연속 완화시켜 얻을 수 있는 상한을 비교하기 위해 여러 볼록화 방법들을 비교하고 비교실험한 결과 또한 제시한다.

Bubosang Problem is a problem set on a directed acyclic graph path concerning both the path and multi-commodity flow decisions. A merchant travels from city 1 through n, either transiting through a city and trading products or passing by the city to the next city on his route. He wants to choose the path and trading product quantity to maximize his net profit which is defined by the difference between the total sales revenue and the traveling cost. The scope of the study considers only the uncapacitated case. In this study, we reformulate BP into a mixed binary quadratic problem to employ the branch-and-cut algorithm to solve the problem. Specifically, we compare the upper bound obtained through the continuous relaxation and convexification of the objective by studying different convexification methods. Computational results of the comparison are also provided.