Conjoint analysis is a statistical technique for evaluating market potential for new product(s) by estimating partworth utilities for product attributes. The objective of the share-of-choice problem - a common approach to new product design - is to find the design that maximizes the number of respondents for whom the new product’s utility exceeds a specific hurdle (reservation utility). This paper extends prior work on linear problems to the nonlinear case where cross terms are incorporated into the model, that is, the pair-wise influence on the overall product utility is taken into account. The nonlinear interaction model is very difficult to solve to optimality, so we developed a set of very fast heuristics that make up our new heuristic algorithm. Based on subsets of data from two real data sets provided through a consulting project, the heuristic solution compares favorably to Sawtooth in terms of percentage share of choice and takes a small fraction of the computational time. In addition, we develop a nonlinear binary integer program and its linear equivalent version in AMPL/CPLEX to benchmark the heuristic results.