A Geometric Branch-and-Bound Algorithm for the Service Bundle Design Problem

In the service industry, a service provider may sell a collection of service activities as a package, also known as a service bundle. Empirical studies indicate that the customer's ex-post perception of a service bundle depends on not only the utility of each activity but also the sequence of the activities being delivered. The latter can be measured by certain sequence effects, such as the utility of the peak activity, the utility of the end activity, and the trend of utility change over the activities. This phenomenon gives a service provider an opportunity to optimize a service bundle by manipulating the activities and their sequence. Such a service bundle design problem can be formulated as a 0-1 sum-of-ratios problem. To solve the problem, we design a novel geometric branch-and-bound algorithm. The algorithm divides the objective function into several dimensions, and repeatedly strengthens the bounds of each dimension. This enables us to convert the 0-1 sum-of-ratios problem into a series of 0-1 quadratic optimization problems. Computational experiments show that the algorithm can solve the service bundle design problem efficiently