In this paper, we focus on solving the share-of-choice product line problem. Previous contributions to this NP-Hard problem include a series of ever improving heuristics. We present a new algorithm that embeds a column generation procedure within branch-and-bound to obtain exact optimal integer solutions. The initial computational results using large simulated dataset demonstrate that the algorithm is capable of identifying provably optimal solutions very quickly.