We develop a branch-and-price algorithm for constructing an optimal product line using partworth estimates from choice-based conjoint analysis. The algorithm determines the specific attribute levels for each multiattribute product in a set of products to maximize the resulting product line's share of choice, i.e., the number of respondents for whom at least one new product's utility exceeds the respondent's reservation utility. Computational results using large commercial and simulated data sets demonstrate that the algorithm can identify provably optimal, robust solutions to realistically sized problems.