Two heuristics are proposed in this paper to solve the problem of constructing an optimal product line using partworth estimates from conjoint analysis. The objective of this NP-hard problem is to choose a level for each attribute to construct a product line so that the line's share-of-choice is maximized. Existing solution approaches include heuristics that have been only tested on small simulated problems and an exact method that requires long run times when tested on a large commercial problem. Computational results demonstrate that one of our heuristics is capable of finding near optimal solution to large simulated and commercial problems in seconds. The performance of the other heuristic fluctuates with the degree of consumer heterogeneity in a sample.