Akçakuş and Mišić

Exact Logit-Based Product Design

Exact Logit-Based Product Design

İrem Akçakuş UCLA Anderson School of Management, University of California, Los
Angeles, California 90095, United States,
<EMAIL_ADDRESS>Velibor V. Mišić UCLA Anderson School
of Management, University of California, Los Angeles, California 90095, United
States<EMAIL_ADDRESS>
The share-of-choice product design (SOCPD) problem is to find the product, as
defined by its attributes, that maximizes market share arising from a
collection of customer types or segments. When customers follow a logit model
of choice, the market share is given by a weighted sum of logistic
probabilities, leading to the logit-based share-of-choice product design
problem. At first glance, this problem appears hopeless: one must optimize an
objective function that is neither convex nor concave, over an exponentially-
sized discrete set of attribute combinations. In this paper, we develop an
exact methodology for solving this problem based on modern integer, convex and
conic optimization. At the heart of our methodology is the surprising result
that the logit-based SOCPD problem can be exactly reformulated as a mixed-
integer convex program. Using both synthetic problem instances and instances
derived from real conjoint data sets, we show that our methodology can solve
large instances to provable optimality or near optimality in operationally
feasible time frames.

new product development; choice modeling; conjoint analysis; integer
programming; convex optimization.

##  1 Introduction

Consider the following canonical marketing problem. A firm has to design a
product, which has a collection of attributes, and each attribute can be set
to one of a finite set of levels. The product will be offered to a collection
of customers, which differ in their preferences and specifically, in the
utility that they obtain from different levels of different attributes. What
product should the firm offer – that is, to what level should each attribute
be set – so as to maximize the share of customers who choose to purchase the
product? This problem is referred to as the share-of-choice product design
(SOCPD) problem, and has received a significant amount of attention in the
marketing science research literature.

The SOCPD problem is a challenging problem for several reasons. First, since a
product corresponds to a combination of attribute levels, the number of
candidate products scales exponentially with the number of attributes, and can
be enormous for even a modest number of attributes. This, in turn, renders
solution approaches based on brute force enumeration computationally
cumbersome. Second, it is common to represent customers using discrete choice
models that are built on the multinomial logit model. Under this assumption of
customer behavior, the problem becomes more complex, because the purchase
probability under a logit choice model is a nonlinear function of the product
design’s utility that is neither convex nor concave. Finally, product design
problems in real life settings may also often involve constraints, arising
from engineering or other considerations, which can further constrain the set
of candidate products.

In this paper, we consider the logit-based SOCPD problem. In this problem, the
firm must design a product that maximizes the expected number of customers who
choose to purchase a product, where customers are assumed to follow logit
models of choice, and the probability of a customer purchasing a product is
given by a logistic response function (i.e., the function
$f(u)=e^{u}/(1+e^{u})$). We propose an exact solution methodology for this
problem that is based on modern integer, convex and conic optimization. To the
best of our knowledge, this is the first exact solution methodology for the
logit-based SOCPD problem.

We make the following specific contributions:

  1. 1.

We formally define the logit-based SOCPD problem. We show that this problem is
NP-Hard in general. Surprisingly, we prove that this problem can be exactly
reformulated as a mixed-integer convex programming (MICONVP) problem. Our
reformulation here relies on a useful characterization of logit probabilities
as being the optimal solutions to a representative agent problem, in which an
agent chooses the probability of selecting two alternatives so as to maximize
a regularized expected utility.

  2. 2.

We propose two specialized solution methods for this problem. The first
approach involves further reformulating our MICONVP using conic constraints,
leading to a mixed-integer conic programming problem that can be solved using
cutting-edge solvers for such problems (such as Mosek). The second approach is
a constraint generation procedure that adds constraints corresponding to
gradient-based linear approximations of the principal nonlinear convex
constraint in our MICONVP problem, thereby allowing the problem to be solved
as a mixed-integer linear program using well-established commercial solvers
such as Gurobi and CPLEX.

  3. 3.

We consider two extensions of our base problem. In the first extension, we
show how our optimization model can be readily modified for the optimization
of expected profit when the profit of a product is a linear function of its
attributes. In the second extension, we consider the problem of optimizing the
geometric mean of the purchase probability across the customer types. For this
latter extension, we prove that the relative performance gap between the
resulting solution and the optimal solution of our original problem can be
bounded in terms of the probability distribution of the customer types and the
ratio between the lowest and highest purchase probabilities attainable by any
product design over all of the customer types. We additionally show how the
geometric mean maximization problem can also be formulated as a MICONVP
problem, via a logarithmic transformation.

  4. 4.

We demonstrate the practical tractability of our approach using synthetic
problem instances, as well as a set of problem instances derived from real
conjoint data sets.

The rest of this paper is organized as follows. Section 2 provides a review of
the related literature. Section 3 provides a formal definition of the logit-
based SOCPD problem, and our exact reformulation of the problem as a MICONVP
problem. Section 4 presents our two solution approaches based on mixed-integer
conic programming and gradient-based constraint generation. Section 6 presents
the results of our numerical experiments. Lastly, in Section 7, we conclude.
With some exceptions, all proofs are relegated to the electronic companion.

##  2 Literature Review

We divide our literature review according to four subsets: the single product
design literature; the product line design literature; the representative
agent model literature; and lastly, the broader optimization literature.

#### Single product design:

Product design has received significant attention in the marketing science
community; we refer readers to Schmalensee and Thisse (1988) and Green et al.
(2004) for overviews of this topic. The majority of papers on the SOCPD
problem assume that customers follow a deterministic, first-choice model,
i.e., they purchase the product if the utility exceeds a “hurdle” utility, and
do not purchase it otherwise. Many papers have proposed heuristic approaches
for this problem; examples include Kohli and Krishnamurti (1987, 1989) and
Balakrishnan and Jacob (1996). Other papers have also considered exact
approaches based on branch-and-bound (Camm et al. 2006) and nested partitions
(Shi et al. 2001). Other work has also considered approaches to product design
that integrate engineering and marketing criteria (Luo et al. 2005, Besharati
et al. 2006).

The main difference between our work and the majority of the prior work on the
product design problem is the use of a logit-based share-of-choice objective
function. As stated earlier, when the share-of-choice is defined as the sum of
logit probabilities, the SOCPD problem becomes a discrete nonlinear
optimization problem, and becomes significantly more difficult than the SOCPD
problem when customers follow first-choice/max-utility models. To the best of
our knowledge, our approach is the first approach for obtaining provably
optimal solutions to the SOCPD problem when customers follow a logit model.

#### Product line design:

Besides the product design problem, a more general problem is the product line
design (PLD) problem, where one must select several products so as to either
maximize the share-of-choice, the expected profit or some other criterion. A
number of papers have considered the PLD problem under a first-choice model of
customer behavior, where customers deterministically select the product with
the highest utility; examples of such papers include McBride and Zufryden
(1988), Kohli and Sukumar (1990), Wang et al. (2009), Belloni et al. (2008)
and Bertsimas and Mišić (2019). Besides the first-choice model, several papers
have also considered the PLD problem under the (single-class) multinomial
logit model (see, e.g., Chen and Hausman 2000, Schön 2010). Other work has
also considered objective functions corresponding to a worst-case expectation
over a family of choice models (Bertsimas and Mišić 2017) and the integration
of marketing and engineering considerations (Luo 2011). Our paper differs from
this literature in that it focuses on the selection of a single product, and
the objective function has the form of a weighted sum of logit probabilities.

#### Representative agent model:

Our MICONVP formulation is based on a characterization of logit probabilities
as solutions of a concave maximization problem where the decision variables
correspond to the choice probabilities and the objective function is the
entropy-regularized expected utility. This concave maximization problem is an
example of a representative agent model, and has been studied in a number of
papers in the economics and operations management literatures (Anderson et al.
1988, Hofbauer and Sandholm 2002, Feng et al. 2017). The goal of our paper is
not to contribute directly to this literature, but rather to leverage one such
result so as to obtain an exact and computationally tractable reformulation of
the logit-based SOCPD problem. To the best of our knowledge, the
representative agent-based characterization of logit probabilities has not
been exploited in optimization-based modeling in marketing before; we believe
that this characterization could potentially be useful in other contexts
outside of product design.

#### Optimization literature:

Lastly, we comment on the relation of our paper to the general optimization
literature. Our paper contributes to the growing literature on mixed-integer
convex and mixed-integer conic programming. In the optimization community,
there has been an increasing interest in developing general solution methods
for this class of problems (see, for example, Lubin et al. 2018, Coey et al.
2020) as well as understanding what types of optimization problems can and
cannot be modeled as mixed-integer convex programs (Lubin et al. 2017). At the
same time, mixed-integer convex and mixed-integer conic programming have been
used in a variety of applications, such as power flow optimization (Lubin et
al. 2019), robotics (Liu et al. 2020), portfolio optimization (Benson and
Sağlam 2013), joint inventory-location problems (Atamtürk et al. 2012) and
designing battery swap networks for electric vehicles (Mak et al. 2013).

Outside of this literature, we note that a couple of prior papers have
considered the problem of designing a product to maximize the share-of-choice
under a mixture of logit models. The first is the paper of Udell and Boyd
(2013) considers the sum of sigmoids optimization problem, which is an
optimization problem where the objective function is a sum of sigmoid
(S-shaped) functions; the logistic response function $f(u)=e^{u}/(1+e^{u})$ is
a specific type of sigmoid function. The paper of Udell and Boyd (2013)
develops a general purpose branch-and-bound algorithm for solving this problem
when the decision variables are continuous. Our paper differs from that of
Udell and Boyd (2013) in that our paper is focused specifically on an
objective that corresponds to a sum of logistic response functions, and the
main decision variables of our formulation are binary variables, indicating
the presence or absence of certain attributes. In addition, our formulation is
an exact reformulation of the problem into a mixed-integer convex problem,
which can then be solved directly using a commercial mixed-integer conic
solver (such as Mosek) or can be solved with a cutting plane approach
implemented with an ordinary mixed-integer linear programming solver (such as
Gurobi). In contrast, the approach of Udell and Boyd (2013) requires one to
solve the problem using a custom branch-and-bound algorithm.

The second is the paper of Huchette and Vielma (2017), which develops a mixed-
integer linear programming formulation for general nonconvex piecewise linear
functions. As an example of the application of the framework, the paper
applies the framework to the problem of deciding on continuous product
attributes to maximize a logit-based share-of-choice objective, which involves
approximating the logistic response function $f(u)=e^{u}/(1+e^{u})$ using a
piecewise linear function. As with our discussion of Udell and Boyd (2013),
our formulation differs in that it is exact, and that the attributes are
discrete rather than continuous.

Besides Udell and Boyd (2013) and Huchette and Vielma (2017), our paper is
also related to the recent paper of Kohli et al. (2019), which considers the
problem of estimating lexicographic rules from choice data. The paper
formulates this problem as a nonlinear optimization problem, where one models
the utility of each attribute as a random variable and chooses deterministic
components of these random utilities so as to maximize the expected number of
nonreversals (comparisons that are consistent with the choice data). While
this is a nonconvex optimization problem, the paper shows that one can obtain
a tractable approximate formulation by maximizing the geometric mean of the
probability of a nonreversal, and develops a bound on the performance of this
solution with respect to the original expected value objective. Our
consideration of the geometric mean-based product design problem in Section
5.2 draws inspiration from Kohli et al. (2019). However, aside from this high-
level similarity, the formulations we present are different from those in
Kohli et al. (2019). In addition, the performance guarantee that we establish
(Theorem 5.2) differs from the guarantee presented in Kohli et al. (2019); the
guarantee in Kohli et al. (2019) is a post-hoc bound, which requires one to
know the optimal solution of the geometric mean problem in order to compute
the approximation factor. In contrast, our guarantee in Theorem 5.2 is an a
priori guarantee that can be calculated before one solves the geometric mean
product design problem, and requires a different proof technique.

Lastly, we note that our paper also contributes to a growing literature on
optimization models where the objective function to be optimized is obtained
from a predictive model or a machine learning model. Some examples include
work on optimizing objective functions obtained from tree ensemble models
(such as random forests; see Ferreira et al. 2016, Mišić 2020) and neural
networks (Anderson et al. 2020).

##  3 Model

We begin by formally defining our model in Section 3.1, and then presenting
our transformation of the problem into a mixed-integer convex program in
Section 3.2.

###  3.1 Problem definition

We assume that there are $n$ binary attributes. We assume the product design
is described by a binary vector $\mathbf{a}=(a_{1},\dots,a_{n})$, where
$a_{i}$ denotes the presence of attribute $i$. While we formulate the problem
in terms of binary attributes, we note that this is without loss of
generality, as we can formulate an attribute with $M$ levels into $M-1$ binary
attributes. We let $\mathcal{A}\subseteq\\{0,1\\}^{n}$ denote the set of
feasible attribute vectors.

We assume that there are $K$ different segments or _customer types_. Each
customer type is associated with a nonnegative weight $\lambda_{k}$, which is
the fraction of customers who belong to that type/segment, or alternatively
the probability that a customer belongs to that type/segment; note that we
always have that $\sum_{k=1}^{K}\lambda_{k}=1$. Each customer type is also
associated with a partworth vector
$\boldsymbol{\beta}_{k}=(\beta_{k,1},\dots,\beta_{k,n})\in\mathbb{R}^{n}$,
where $\beta_{k,i}$ is the partworth of attribute $i$. In addition, we let
$\beta_{k,0}\in\mathbb{R}$ denote the constant part of the customer’s utility.
Given a candidate design $\mathbf{a}\in\mathcal{A}$, the customer’s utility
for the product is given by

$u_{k}(\mathbf{a})=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i}.$

We assume that each customer type is choosing between our product design
corresponding to the vector $\mathbf{a}$, and an outside/no-purchase option.
Without loss of generality, we fix the utility of the outside option to zero.
This assumption is not restrictive, as choice probabilities under the logit
model are unaffected when all of the utilities are adjusted by a constant. In
particular, an equivalent representation (one that would lead to the same
choice probabilities) is to specify the utility of the product as
$\sum_{i=1}^{n}\beta_{k,i}a_{i}$ and the utility of the no-purchase option as
$-\beta_{k,0}$. As a result, the constant term $\beta_{k,0}$ effectively
captures the utility of the no-purchase option.

We assume that each customer type chooses to buy or not buy the product
according to a multinomial logit model. Thus, given
$\mathbf{a}\in\mathcal{A}$, the customer chooses to purchase the product with
probability $\exp(u_{k}(\mathbf{a}))/(1+\exp(u_{k}(\mathbf{a})))$ and chooses
the outside option with probability $1/(1+\exp(u_{k}(\mathbf{a})))$.

With these definitions, the logit-based share-of-choice product design problem
can then be defined as

$\underset{\mathbf{a}\in\mathcal{A}}{\text{maximize}}\sum_{k=1}^{K}\lambda_{k}\cdot\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}.$
(1)

The objective function of this problem can be thought of as the share or
fraction of all customers who choose to purchase the product, or the
(unconditional) probability that a random customer chooses to purchase the
product.

Our first major theoretical result is that problem (1) is theoretically
intractable.

###### Theorem 3.1

Problem (1) is NP-Hard.

This result (see Section 8.1 for the proof) follows by reducing the MAX 3SAT
problem, a well-known NP-Complete problem, to problem (1). Notwithstanding
Theorem 3.1, it is unreasonable to expect problem (1) to be easy: it is an
optimization problem over a discrete feasible region, with a nonlinear
objective function that is neither convex nor concave. In the next section, we
turn our attention to solving this problem using mathematical programming.

###  3.2 Mixed-Integer Convex Programming Formulation

As discussed in Section 3.1, problem (1) is a challenging optimization
problem. Surprisingly, it turns out that this problem can be reformulated as a
mixed-integer convex programming (MICP) problem; that is, a problem of the
form

$\displaystyle\underset{\mathbf{x}}{\text{minimize}}$
$\displaystyle\mathbf{c}^{T}\mathbf{x}$ (2a) subject to
$\displaystyle\mathbf{x}\in\mathcal{X},$ (2b) $\displaystyle
x_{i}\in\mathbb{Z},\ l_{i}\leq x_{i}\leq u_{i},\quad\forall i\in I,$ (2c)

where $\mathbf{x}\in\mathbb{R}^{n}$ is the decision variable,
$\mathcal{X}\subseteq\mathbb{R}^{n}$ is a closed convex set,
$I\subseteq\\{1,\dots,n\\}$ is the subset of the decision variables restricted
to take integer values, and $l_{i}$ and $u_{i}$ are lower and upper bounds on
each integer variable. In what follows, we show how to obtain this
formulation.

We begin by first presenting some related background on the representative
agent model. In the representative agent model, an agent is faced with $M$
alternatives. Each alternative $m\in\\{1,\dots,M\\}$ is associated with a
utility $\pi_{m}$. The agent must choose the probability $x_{m}$ with which
each alternative will be selected; we let $\mathbf{x}=(x_{1},\dots,x_{M})$ be
the probability distribution over the $M$ alternatives. The agent seeks to
maximize his adjusted expected utility, where the adjustment is achieved
through a convex regularization function $V(\mathbf{x})$. The representative
agent model is then the following optimization problem:

$\displaystyle\underset{\mathbf{x}}{\text{maximize}}$
$\displaystyle\sum_{i=1}^{m}\pi_{m}x_{m}-V(\mathbf{x})$ (3a) subject to
$\displaystyle\sum_{m=1}^{M}x_{m}=1,$ (3b) $\displaystyle x_{m}\geq
0,\quad\forall\ m\in\\{1,\dots,M\\}.$ (3c)

Since the function $V(\cdot)$ is a convex function, the above problem is a
concave maximization problem. By carefully choosing the function $V$, the
optimal solution of this problem – the probability distribution $\mathbf{x}$ –
can be made to coincide with choice probabilities under different choice
models. In particular, it is known that the function
$V(\mathbf{x})=\sum_{i=1}^{n}x_{i}\log(x_{i})$ gives choice probabilities
corresponding to a multinomial logit model (Anderson et al. 1988).

For our problem, the specific instantiation of the representative agent model
that we are interested in is one corresponding to the choice of the $k$th
customer type between our product and the no-purchase option. We let $x_{k,1}$
denote the probability of choosing our product with attribute vector
$\mathbf{a}$, and $x_{k,0}$ denote the probability of choosing the no-purchase
option. Recall that the utility of our product is $u_{k}(\mathbf{a})$, and the
utility of the no-purchase option is 0. The representative agent model for
this customer type can thus be formulated as

$\displaystyle\underset{x_{k,0},x_{k,1}}{\text{maximize}}$ $\displaystyle
u_{k}(\mathbf{a})\cdot x_{k,1}+0\cdot
x_{k,0}-x_{k,1}\log(x_{k,1})-x_{k,0}\log(x_{k,0})$ (4a) subject to
$\displaystyle x_{k,1}+x_{k,0}=1,$ (4b) $\displaystyle x_{k,1},x_{k,0}\geq 0.$
(4c)

We now show two key properties of this problem. First, we show that the unique
optimal solution $(x^{*}_{k,1},x^{*}_{k,0})$ is exactly the logit choice
probabilities for the two alternatives. Second, we show that the optimal
objective value can be found in closed form.

###### Proposition 3.2

The unique optimal solution $(x^{*}_{k,1},x^{*}_{k,})$ of problem (4) is given
by

$\displaystyle x^{*}_{k,1}$
$\displaystyle=\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))},$
$\displaystyle x^{*}_{k,0}$
$\displaystyle=\frac{1}{1+\exp(u_{k}(\mathbf{a}))}.$

In addition, the optimal objective value is $\log(1+\exp(u_{k}(\mathbf{a})))$.

#### Proof:

First, we note that this problem has a unique optimal solution since the
objective function is strictly concave and the feasible region is a convex
set.

To find the optimal solution, we formulate the Lagrangean of this problem:

$\mathcal{L}(x_{k,1},x_{k,0},\mu)=u_{k}(\mathbf{a})x_{k,1}+0x_{k,0}-x_{k,1}\log(x_{k,1})-x_{k,0}\log(x_{k,0})+\mu(x_{k,1}+x_{k,0}-1)$

The partial derivatives of $\mathcal{L}$ with respect to $x_{k,1},x_{k,0},\mu$
are

$\displaystyle\frac{\partial}{\partial
x_{k,1}}\mathcal{L}(x_{k,1},x_{k,0},\mu)=u_{k}(\mathbf{a})-\log(x_{k,1})-1+\mu,$
(5) $\displaystyle\frac{\partial}{\partial
x_{k,0}}\mathcal{L}(x_{k,1},x_{k,0},\mu)=0-\log(x_{k,0})-1+\mu,$ (6)
$\displaystyle\frac{\partial}{\partial\mu}\mathcal{L}(x_{k,1},x_{k,0},\mu)=x_{k,1}+x_{k,0}-1.$
(7)

The first-order conditions that must be satisfied by an optimal solution of
this problem are that all three partial derivatives are equal to zero. Thus,
at optimality, the first order conditions for $x_{k,1}$ and $x_{k,0}$ give us
that

$\displaystyle x^{*}_{k,1}=\exp(u_{k}(\mathbf{a}))\cdot\exp(\mu-1),$ (8)
$\displaystyle x^{*}_{k,0}=\exp(\mu-1).$ (9)

Using the condition that $x_{k,1}+x_{k,0}-1=0$ or equivalently
$x_{k,1}+x_{k,0}=1$, we get

$\displaystyle\exp(u_{k}(\mathbf{a}))\cdot\exp(\mu-1)+\exp(\mu-1)=1$

which implies that $\exp(\mu-1)=1/(\exp(u_{k}(\mathbf{a}))+1)$. Substituting
this into the expressions for $x^{*}_{k,1}$ and $x^{*}_{k,0}$, we obtain that

$\displaystyle
x^{*}_{k,1}=\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1},$
$\displaystyle x^{*}_{k,0}=\frac{1}{\exp(u_{k}(\mathbf{a}))+1}.$

To verify the objective value of this optimal solution, we have

$\displaystyle
u_{k}(\mathbf{a})x^{*}_{k,1}+0x^{*}_{k,0}-x^{*}_{k,1}\log(x^{*}_{k,1})-x^{*}_{k,0}\log(x^{*}_{k,0})$
$\displaystyle=u_{k}(\mathbf{a})\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}-\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}\cdot\log\left[\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}\right]$
$\displaystyle\phantom{=}-\frac{1}{\exp(u_{k}(\mathbf{a}))+1}\cdot\log\left[\frac{1}{\exp(u_{k}(\mathbf{a}))+1}\right]$
$\displaystyle=u_{k}(\mathbf{a})\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}-\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}\cdot
u_{k}(\mathbf{a})+\frac{\exp(u_{k}(\mathbf{a}))}{\exp(u_{k}(\mathbf{a}))+1}\cdot\log(1+\exp(u_{k}(\mathbf{a})))$
$\displaystyle\phantom{=}+\frac{1}{1+\exp(u_{k}(\mathbf{a}))}\cdot\log(1+\exp(u_{k}(\mathbf{a})))$
$\displaystyle=\log(1+\exp(u_{k}(\mathbf{a}))),$

which completes the proof. $\square$

Using this result, we can now proceed with the formulation of our SOCPD
problem. We first make the following assumption on the structure of the set
$\mathcal{A}$. The set $\mathcal{A}$ can be written as
$\mathcal{A}=\\{\mathbf{a}\in\\{0,1\\}^{n}\mid\mathbf{C}\mathbf{a}\leq\mathbf{d}\\}$
for some choice of $\mathbf{C}\in\mathbb{R}^{m\times n}$ and
$\mathbf{d}\in\mathbb{R}^{m}$, where $m\in\mathbb{Z}_{+}$. Assumption 3.2 just
requires that the set of candidate products $\mathcal{A}$ can be represented
as the set of binary vectors satisfying a finite collection of linear
inequality constraints. This assumption is necessary in order to ensure that
our problem can be formulated as a mixed-integer convex program of finite
size. We note that this assumption is not too restrictive, as many natural
constraints can be expressed in this way. We provide some examples at the end
of this section.

With a slight abuse of notation, let $u_{k}$ be a decision variable that
denotes the utility of the candidate product $\mathbf{a}$ for customer type
$k$. As before, let $x_{k,1}$ and $x_{k,0}$ denote the probability of customer
type $k$ purchasing and not purchasing the product, respectively. Then, the
optimization problem can be formulated as

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{x}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot x_{k,1}$ (10a) subject to
$\displaystyle x_{k,1}+x_{k,0}=1,\quad\forall k\in\\{1,\dots,K\\},$ (10b)
$\displaystyle
u_{k}x_{k,1}-x_{k,1}\log(x_{k,1})-x_{k,0}\log(x_{k,0})\geq\log(1+\exp(u_{k})),\quad\forall
k\in\\{1,\dots,K\\},$ (10c) $\displaystyle
u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall
k\in\\{1,\dots,K\\},$ (10d) $\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$
(10e) $\displaystyle a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\},$
(10f) $\displaystyle x_{k,1},x_{k,0}\geq 0,\quad\forall k\in\\{1,\dots,K\\}.$
(10g)

We now prove the validity of this formulation.

###### Theorem 3.3

Problem (10) is equivalent to problem (1).

#### Proof:

To show this equivalence, we will show that for every
$\mathbf{a}\in\mathcal{A}$, the solution $(\mathbf{a},\mathbf{u},\mathbf{x})$
where $\mathbf{u}$ and $\mathbf{x}$ are given by

$\displaystyle u_{k}$ $\displaystyle=u_{k}(\mathbf{a}),\quad\forall\ k,$ (11)
$\displaystyle x_{k,1}$
$\displaystyle=\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))},\quad\forall\
k$ (12) $\displaystyle x_{k,0}$
$\displaystyle=\frac{1}{1+\exp(u_{k}(\mathbf{a}))},\quad\forall\ k$ (13)

is the only feasible solution of problem (10) corresponding to $\mathbf{a}$;
stated differently, there is a one-to-one correspondence between product
vectors $\mathbf{a}$ and feasible solutions of problem (10), and by finding a
solution $(\mathbf{a},\mathbf{u},\mathbf{x})$ of problem (10) that maximizes
$\sum_{k=1}^{K}\lambda_{k}\cdot x_{k,1}$ guarantees that $\mathbf{a}$
maximizes
$\sum_{k=1}^{K}\lambda_{k}\cdot\exp(u_{k}(\mathbf{a}))/(1+\exp(u_{k}(\mathbf{a})))$.

Observe that by construction, the solution
$(\mathbf{a},\mathbf{u},\mathbf{x})$ automatically satisfies constraints
(10d), (10g) and (10b). We thus only need to show that it satisfies constraint
(10c). Note that the left-hand side of constraint (10c) is the objective
function of the representative agent model (4), where the utility of the
product is $u_{k}(\mathbf{a})$. By Proposition 3.2, the optimal objective
value of this representative agent model is $\log(1+\exp(u_{k}(\mathbf{a})))$,
which is exactly the right-hand side of constraint (10c). Thus, constraint
(10c) requires that $x_{k,1}$ and $x_{k,0}$ must be chosen to have an
objective value at least as great as the optimal objective value; in other
words, $(x_{k,1},x_{k,0})$ is enforced to be an optimal solution of problem
(4). By Proposition 3.2, we know that the choice of $x_{k,1}$ and $x_{k,0}$ as
in (12) and (13) is an optimal solution of this representative agent problem,
and therefore $x_{k,1}$, $x_{k,0}$ and $u_{k}$ set as in (11) - (13) satisfy
constraint (10c). Moreover, since this solution of the representative agent
problem is unique, there can be no other choice of $x_{k,1}$ and $x_{k,0}$
that will satisfy this constraint. This establishes that given $\mathbf{a}$,
the solution $(\mathbf{a},\mathbf{u},\mathbf{x})$ with $\mathbf{u}$ and
$\mathbf{x}$ as defined in (11) - (13) is the only feasible solution
corresponding to $\mathbf{a}$, and thus that the two problems are equivalent.
$\square$

Theorem 3.3 establishes that problem (10) is equivalent to the original SOCPD
problem (1). The key feature of this formulation is that it no longer
explicitly involves the logit choice probabilities, which are a nonconvex
function of $u_{k}$. We note that this problem is _almost_ a mixed-integer
convex program. In the main nonlinear constraint (10c), the functions
$-x_{k,1}\log(x_{k,1})$ and $-x_{k,0}\log(x_{k,0})$ appearing on the left hand
side are instances of the _entropy function_ $-x\log(x)$ (Boyd and
Vandenberghe 2004) and are concave in $x_{k,1}$ and $x_{k,0}$. Similarly, the
function $\log(1+\exp(u_{k}))$ appearing on the right hand side, which is
known as the _softplus function_ (Mosek ApS 2021a), is a convex function of
$u_{k}$. Thus, this constraint can almost be written in the form
$F(u_{k},\mathbf{x}_{k})\leq 0$, where $F$ is a convex function. The main
obstacle that prevents us from doing this is the bilinear term $u_{k}x_{k,1}$,
which is the product of two decision variables and is not jointly concave in
$u_{k}$ and $x_{k,1}$.

Fortunately, we can use the fact that
$u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i}$ to re-write this bilinear
term as

$\displaystyle u_{k}x_{k,1}$
$\displaystyle=(\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i})x_{k,1}$
$\displaystyle=\beta_{k,0}x_{k,1}+\sum_{i=1}^{n}\beta_{k,i}\cdot
a_{i}x_{k,1}.$

Using the fact that each $a_{i}\in\\{0,1\\}$ and that $0\leq x_{k,1}\leq 1$,
we can now linearize the bilinear terms $a_{i}x_{k,1}$ using a standard
modeling technique from integer programming. In particular, we introduce a
continuous decision variable $y_{k,i}$ for each $k$ and $i$ which corresponds
to the product $a_{i}x_{k,1}$, and a continuous decision variable $w_{k}$
which corresponds to the product $u_{k}x_{k,1}$. This leads to the following
equivalent formulation:

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{w},\mathbf{x},\mathbf{y}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot x_{k,1}$ (14a) subject to
$\displaystyle x_{k,1}+x_{k,0}=1,\quad\forall k\in\\{1,\dots,K\\},$ (14b)
$\displaystyle
w_{k}-x_{k,1}\log(x_{k,1})-x_{k,0}\log(x_{k,0})\geq\log(1+\exp(u_{k})),\quad\forall
k\in\\{1,\dots,K\\},$ (14c) $\displaystyle
u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall
k\in\\{1,\dots,K\\},$ (14d) $\displaystyle
w_{k}=\beta_{k,0}x_{k,1}+\sum_{i=1}^{n}\beta_{k,i}y_{k,i},\quad\forall
k\in\\{1,\dots,K\\},$ (14e) $\displaystyle y_{k,i}\leq x_{k,1},\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (14f) $\displaystyle y_{k,i}\leq
a_{i},\quad\forall k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (14g)
$\displaystyle y_{k,i}\geq a_{i}-1+x_{k,1},\quad\forall k\in\\{1,\dots,K\\},\
i\in\\{1,\dots,n\\},$ (14h) $\displaystyle y_{k,i}\geq 0,\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (14i)
$\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$ (14j) $\displaystyle
a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\},$ (14k) $\displaystyle
x_{k,1},x_{k,0}\geq 0,\quad\forall k\in\\{1,\dots,K\\}.$ (14l)

Note that in the formulation above, when $\mathbf{a}\in\mathcal{A}$, $y_{k,i}$
is forced to take the value of $a_{i}\cdot x_{k,1}$, and $w_{k}$ takes the
value of $u_{k}\cdot x_{k,1}$. Problem (14) is a mixed-integer convex program,
and can be tackled through a number of solution approaches, which we discuss
next (Section 4).

Before continuing, we briefly discuss the modeling capability of the
constraint $\mathbf{C}\mathbf{a}\leq\mathbf{d}$ arising from Assumption 3.2.
The constraint $\mathbf{C}\mathbf{a}\leq\mathbf{d}$ can be used to encode a
variety of requirements on the attribute vectors $\mathbf{a}$ as linear
constraints. For example, if the product has two attributes, where the first
attribute has three levels and the second attribute has four levels, then one
can model the product through the vector
$\mathbf{a}=(a_{1},a_{2},a_{3},a_{4},a_{5})$, where $a_{1}$ and $a_{2}$ are
dummy variables to represent two out of the three levels of the first
attribute and $a_{3},a_{4},a_{5}$ are dummy variables to represent three out
of the four levels of the second attribute. One would then need to enforce the
constraints

$\displaystyle a_{1}+a_{2}\leq 1,$ (15) $\displaystyle a_{3}+a_{4}+a_{5}\leq
1$ (16)

to ensure that at most one out of the variables $a_{1},a_{2}$ is set to 1 and
at most one variable out of $a_{3},a_{4},a_{5}$ is set to 1. This can be
achieved by specifying $\mathbf{C}$ and $\mathbf{d}$ as

$\displaystyle\mathbf{C}=\left[\begin{array}[]{ccccc}1&1&1&0&0\\\
0&0&0&1&1\end{array}\right],\ \mathbf{d}=\left[\begin{array}[]{c}1\\\
1\end{array}\right]$

Beside the ability to represent multi-level attributes, one can use the
constraint $\mathbf{C}\mathbf{a}\leq\mathbf{d}$ to represent design
requirements such as weight and cost; for example, one may be interested in
imposing the constraint

$b_{0}+\sum_{i=1}^{n}b_{i}a_{i}\leq B,$

where $b_{0}$ is the base weight of the product, $b_{i}$ is the incremental
weight added to the product from attribute $i$ and $B$ is a limit on the
overall weight of the product. This constraint can be modeled by specifying
$\mathbf{C}$ and $\mathbf{d}$ as

$\displaystyle\mathbf{C}=\left[\begin{array}[]{cccc}b_{1}&b_{2}&\cdots&b_{n}\end{array}\right],\
\mathbf{d}=\left[B-b_{0}\right].$

##  4 Solution Approaches

In this section, we present two different approaches for solving problem (14).
In Section 4.1, we present a solution approach based on transforming the
mixed-integer convex program (14) into a mixed-integer conic program, thereby
allowing for the problem to be solved by mixed-integer conic solvers such as
Mosek. In Section 4.2, we present a solution approach based on generating
constraints corresponding to the linear underapproximations of the convex
functions appearing in constraint (14c), effectively allowing the problem to
be solved by mixed-integer linear solvers such as Gurobi and CPLEX.

###  4.1 Solution Approach #1: Representation as Mixed-Integer Conic Program

The first approach that we describe for solving problem (14) involves further
reformulating the problem into a mixed-integer conic programming (MICP)
problem. We begin by providing a brief overview of mixed-integer conic
optimization problems, and then present our formulation.

A mixed-integer conic programming problem has the following general form:

$\displaystyle\underset{\mathbf{x}\in\mathbb{R}^{n}}{\text{minimize}}$
$\displaystyle\mathbf{c}^{T}\mathbf{x}$ (17a) subject to
$\displaystyle\mathbf{A}\mathbf{x}-\mathbf{b}\in\mathcal{K},$ (17b)
$\displaystyle x_{i}\in\mathbb{Z},\quad\forall\ i\in\\{1,\dots,I\\},$ (17c)

where $n$ is the dimension of the decision variable, $\mathbf{c}$ is an
$n$-dimensional vector, $\mathbf{b}$ is an $m$-dimensional vector,
$\mathbf{A}$ is an $m$-by-$n$ matrix, $I\leq n$ is the number of integer
variables in the problem and finally, $\mathcal{K}$ is a closed convex cone. A
closed convex cone $\mathcal{K}$ is a closed subset of $\mathbb{R}^{n}$ that
contains all nonnegative combinations of its elements, i.e., a set
$\mathcal{K}$ satisfying the following property:

$\mathbf{y}_{1},\mathbf{y}_{2}\in\mathcal{K}\ \Rightarrow\
\alpha_{1}\mathbf{y}_{1}+\alpha_{2}\mathbf{y}_{2}\in\mathcal{K}\ \text{for
any}\ \alpha_{1},\alpha_{2}\geq 0.$ (18)

While the cone $\mathcal{K}$ can in theory be specified as any set that
satisfies (18), in practice, it is common to model $\mathcal{K}$ as a
Cartesian product of a collection of cones drawn from the set of standard
cones. An example of a standard cone is the the cone
$\mathcal{K}_{\geq}=\\{\mathbf{y}\in\mathbb{R}^{m}\mid\mathbf{y}\geq\mathbf{0}\\}$,
where $\mathbf{0}$ is an $m$-dimensional vector of zeros. This cone is known
as the nonnegative cone, as it corresponds to the nonnegative orthant of
$\mathbb{R}^{n}$. The constraint
$\mathbf{A}\mathbf{x}-\mathbf{b}\in\mathcal{K}_{\geq}$ is equivalent to the
constraint $\mathbf{A}\mathbf{x}\geq\mathbf{b}$, which is just a linear
constraint. Other standard cones include the zero cone, the second order cone,
the exponential cone and the positive semidefinite cone; we refer readers to
Mosek ApS (2021a) for an overview of other standard cones.

Having described mixed-integer conic programming in generality, we now
elaborate on why this representation is valuable. Many mixed-integer convex
programs involve complicated nonlinear functions. Until recently, the method
of choice for tackling such problems has been to use mixed-integer nonlinear
programming solvers, which treat these nonlinear functions in a “black-box”
fashion and rely on evaluating these functions and their derivatives to solve
the problem. Often, it turns out that constraints involving these nonlinear
functions can be re-written through additional variables and additional conic
constraints involving standard cones.111A notable recent example of this is
the paper of Lubin et al. (2018), which found that all 194 mixed-integer
convex programming problems in the MINLPLIB2
(http://www.gamsworld.org/minlp/minlplib2/html/) benchmark library could be
represented as mixed-integer conic programs using standard cones. In so doing,
one obtains a mixed-integer conic program, which is then amenable to solution
methods for such problems. This is important because conic programs – problems
of the same form as (17), without the integrality constraint (17c) – are
considered to be among the easiest continuous nonlinear programs to solve: the
theory of numerical algorithms for solving these problems is quite developed,
there are numerous software packages for solving these problems at practical
scale, and there continues to be active development both in the theory and in
software implementations. Solution algorithms for mixed-integer conic programs
are built on top of algorithms for (continuous) conic programs and can exploit
the conic structure. By re-writing our mixed-integer convex program (14) as a
mixed-integer conic program, one is able to use state-of-the-art commercial
solvers such as Mosek (Mosek ApS 2021b), as well as new open-source solvers
such as Pajarito (Coey et al. 2020) to solve the problem.

Thus motivated, we proceed with our reformulation of (14) as a MICP problem.
To do so, we will make use of a standard cone known as the _exponential cone_
, which is defined as

$\mathcal{K}_{\exp}=\\{(r,0,t)\in\mathbb{R}^{3}\mid r\geq 0,t\leq
0\\}\cup\\{(r,s,t)\in\mathbb{R}^{3}\mid s>0,r\geq s\exp(t/s)\\}.$ (19)

The exponential cone is useful precisely because it can be used to represent
the entropy function $x\log(x)$ and the softplus function $\log(1+e^{x})$
which appear in our formulation (14). For the former, the constraint

$t\leq-x\log(x)$ (20)

can be written as the conic constraint

$(1,x,t)\in\mathcal{K}_{\exp}.$

For the latter, the constraint

$t\geq\log(1+\exp(x))$ (21)

can be written by introducing auxiliary variables $v_{1},v_{2}$ and then using
the following set of conic constraints:

$\displaystyle v_{1}+v_{2}\leq 1,$
$\displaystyle(v_{1},1,x-t)\in\mathcal{K}_{\exp},$
$\displaystyle(v_{2},1,-t)\in\mathcal{K}_{\exp}.$

Armed with these two properties, we recall constraint (14c) for a fixed $k$:

$\displaystyle
w_{k}-x_{k,1}\log(x_{k,1})-x_{k,0}\log(x_{k,0})\geq\log(1+\exp(u_{k}))$

We now introduce the auxiliary variables $\theta_{k,1},\theta_{k,0}$ and
$\phi_{k}$, and reformulate this as the following equivalent set of
constraints:

$\displaystyle w_{k}+\theta_{k,1}+\theta_{k,0}\geq\phi_{k},$
$\displaystyle\theta_{k,1}\leq-x_{k,1}\log(x_{k,1}),$
$\displaystyle\theta_{k,0}\leq-x_{k,0}\log(x_{k,0}),$
$\displaystyle\phi_{k}\geq\log(1+\exp(u_{k})).$

We next introduce the auxiliary variables $v_{k,0}$ and $v_{k,1}$ to represent
the softplus function, and re-write the above four constraints as the
following family of conic constraints:

$\displaystyle w_{k}+\theta_{k,1}+\theta_{k,0}\geq\phi_{k},$
$\displaystyle(1,x_{k,1},\theta_{k,1})\in\mathcal{K}_{\exp},$
$\displaystyle(1,x_{k,0},\theta_{k,0})\in\mathcal{K}_{\exp},$ $\displaystyle
v_{k,0}+v_{k,1}\leq 1,$
$\displaystyle(v_{k,1},1,u_{k}-\phi_{k})\in\mathcal{K}_{\exp},$
$\displaystyle(v_{k,0},1,-\phi_{k})\in\mathcal{K}_{\exp}.$

This leads to the following mixed-integer conic programming formulation of our
original problem:

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{v},\mathbf{w},\mathbf{x},\mathbf{y},\boldsymbol{\theta},\boldsymbol{\phi}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot x_{k,1}$ (22a) subject to
$\displaystyle x_{k,1}+x_{k,0}=1,\quad\forall k\in\\{1,\dots,K\\},$ (22b)
$\displaystyle w_{k}+\theta_{k,1}+\theta_{k,0}\geq\phi_{k},\quad\forall
k\in\\{1,\dots,K\\},$ (22c)
$\displaystyle(1,x_{k,1},\theta_{k,1})\in\mathcal{K}_{\exp},\quad\forall
k\in\\{1,\dots,K\\},$ (22d)
$\displaystyle(1,x_{k,0},\theta_{k,0})\in\mathcal{K}_{\exp},\quad\forall
k\in\\{1,\dots,K\\},$ (22e) $\displaystyle v_{k,0}+v_{k,1}\leq 1,\quad\forall
k\in\\{1,\dots,K\\},$ (22f)
$\displaystyle(v_{k,1},1,u_{k}-\phi_{k})\in\mathcal{K}_{\exp},\quad\forall
k\in\\{1,\dots,K\\},$ (22g)
$\displaystyle(v_{k,0},1,-\phi_{k})\in\mathcal{K}_{\exp},\quad\forall
k\in\\{1,\dots,K\\},$ (22h) $\displaystyle
u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall
k\in\\{1,\dots,K\\},$ (22i) $\displaystyle
w_{k}=\beta_{k,0}x_{k,1}+\sum_{i=1}^{n}\beta_{k,i}y_{k,i},\quad\forall
k\in\\{1,\dots,K\\},$ (22j) $\displaystyle y_{k,i}\leq x_{k,1},\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (22k) $\displaystyle y_{k,i}\leq
a_{i},\quad\forall k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (22l)
$\displaystyle y_{k,i}\geq a_{i}-1+x_{k,1},\quad\forall k\in\\{1,\dots,K\\},\
i\in\\{1,\dots,n\\},$ (22m) $\displaystyle y_{k,i}\geq 0,\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (22n)
$\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$ (22o) $\displaystyle
a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\},$ (22p) $\displaystyle
x_{k,1},x_{k,0}\geq 0,\quad\forall k\in\\{1,\dots,K\\}.$ (22q)

Formulation (22) is attractive because, as mentioned earlier, it is in a form
where it can be solved by mixed-integer conic programming solvers. In our
numerical experiments in Section 6, we use one such solver, Mosek, which as of
2019 supports the exponential cone and mixed-integer problems involving the
exponential cone.

###  4.2 Solution Approach #2: Gradient-Based Constraint Generation

Our second approach for solving this problem is gradient-based constraint
generation. The idea of this approach is to sequentially approximate the
nonlinear convex functions in the formulation (14) using their linear
approximations.

To motivate this approach, we recall a standard property of convex functions.
For any differentiable convex function $f:\mathbb{R}^{n}\to\mathbb{R}$ and any
point $\bar{\mathbf{x}}\in\mathbb{R}^{n}$, the function $f$ is lower-bounded
by the first-order approximation of $f$ at $\bar{\mathbf{x}}$:

$f(\mathbf{x})\geq f(\bar{\mathbf{x}})+\nabla
f(\bar{\mathbf{x}})^{T}(\mathbf{x}-\bar{\mathbf{x}}).$ (23)

A consequence of this property is that the function $f$ can be written as the
pointwise maximum of a family of linear functions, where each linear function
in the family corresponds to the above first-order approximation:

$f(\mathbf{x})=\max_{\bar{\mathbf{x}}\in\mathbb{R}^{n}}\left\\{f(\bar{\mathbf{x}})+\nabla
f(\bar{\mathbf{x}})^{T}(\mathbf{x}-\bar{\mathbf{x}})\right\\}$ (24)

Thus, a convex constraint of the form

$f(\mathbf{x})\leq 0$ (25)

can be written as the constraint

$\max_{\bar{\mathbf{x}}\in\mathbb{R}^{n}}\left\\{f(\bar{\mathbf{x}})+\nabla
f(\bar{\mathbf{x}})^{T}(\mathbf{x}-\bar{\mathbf{x}})\right\\}\leq 0,$ (26)

or equivalently, as

$f(\bar{\mathbf{x}})+\nabla
f(\bar{\mathbf{x}})^{T}(\mathbf{x}-\bar{\mathbf{x}})\leq 0,\quad\forall\
\bar{\mathbf{x}}\in\mathbb{R}^{n}.$ (27)

In formulation (14), the principal constraint which involves a convex,
differentiable function is constraint (14c). We can re-write this constraint
as

$F(w_{k},x_{k,1},x_{k,0},u_{k})\leq 0$ (28)

where

$F(w_{k},x_{k,1},x_{k,0},u_{k})=-w_{k}+x_{k,1}\log x_{k,1}+x_{k,0}\log
x_{k,0}+\log(1+\exp(u_{k})),$ (29)

and the domain of $F$ is

$\mathcal{V}_{k}=\\{(w_{k},x_{k,1},x_{k,0},u_{k})\in\mathbb{R}^{4}\mid
x_{k,1}>0,x_{k,0}>0\\}.$ (30)

The gradient of $F$ is

$\displaystyle\nabla F$ $\displaystyle=\left[\begin{array}[]{c}-1\\\\[2.5pt]
\log x_{k,1}+1\\\\[2.5pt] \log x_{k,0}+1\\\\[2.5pt]
\frac{\exp(u_{k})}{1+\exp(u_{k})}\end{array}\right].$ (35)

The constraint $F(w_{k},x_{k,1},x_{k,0},u_{k})\leq 0$ can therefore be
equivalently re-written as the following family of linear constraints:

$\displaystyle
F(\bar{w}_{k},\bar{x}_{k,1},\bar{x}_{k,0},\bar{u}_{k})+(-1)(w_{k}-\bar{w}_{k})+(\log\bar{x}_{k,1}+1)(x_{k,1}-\bar{x}_{k,1})$
$\displaystyle+(\log\bar{x}_{k,0}+1)(x_{k,0}-\bar{x}_{k,0})+\frac{\exp(\bar{u}_{k})}{1+\exp(\bar{u}_{k})}\cdot(u_{k}-\bar{u}_{k})$
$\displaystyle\leq 0,$ $\displaystyle\quad\quad\forall\
(\bar{w}_{k},\bar{x}_{k,1},\bar{x}_{k,0},\bar{u}_{k})\in\mathcal{V}_{k}.$ (36)

We therefore obtain the following formulation which is equivalent to
formulation (14):

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{w},\mathbf{x},\mathbf{y}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot x_{k,1}$ (37a) subject to
$\displaystyle x_{k,1}+x_{k,0}=1,\quad\forall k\in\\{1,\dots,K\\},$ (37b)
$\displaystyle
F(\bar{w}_{k},\bar{x}_{k,1},\bar{x}_{k,0},\bar{u}_{k})+(-1)(w_{k}-\bar{w}_{k})+(\log\bar{x}_{k,1}+1)(x_{k,1}-\bar{x}_{k,1})$
(37c)
$\displaystyle+(\log\bar{x}_{k,0}+1)(x_{k,0}-\bar{x}_{k,0})+\frac{\exp(\bar{u}_{k})}{1+\exp(\bar{u}_{k})}\cdot(u_{k}-\bar{u}_{k})\leq
0,$ (37d) $\displaystyle\quad\quad\forall\
(\bar{w}_{k},\bar{x}_{k,1},\bar{x}_{k,0},\bar{u}_{k})\in\mathcal{V}_{k},\
k\in\\{1,\dots,K\\},$ (37e) $\displaystyle
u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall
k\in\\{1,\dots,K\\},$ (37f) $\displaystyle
w_{k}=\beta_{k,0}x_{k,1}+\sum_{i=1}^{n}\beta_{k,i}y_{k,i},\quad\forall
k\in\\{1,\dots,K\\},$ (37g) $\displaystyle y_{k,i}\leq x_{k,1},\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (37h) $\displaystyle y_{k,i}\leq
a_{i},\quad\forall k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (37i)
$\displaystyle y_{k,i}\geq a_{i}-1+x_{k,1},\quad\forall k\in\\{1,\dots,K\\},\
i\in\\{1,\dots,n\\},$ (37j) $\displaystyle y_{k,i}\geq 0,\quad\forall
k\in\\{1,\dots,K\\},\ i\in\\{1,\dots,n\\},$ (37k)
$\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$ (37l) $\displaystyle
a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\},$ (37m) $\displaystyle
x_{k,1},x_{k,0}\geq 0,\quad\forall k\in\\{1,\dots,K\\}.$ (37n)

The difference between the new formulation (37) and the original formulation
(14) is that the convex constraint (14c) has been replaced by an infinite
family of linear constraints. Although the new formulation remains difficult
to solve, the key advantage of this formulation is that it is in a form that
is suited to constraint generation. The idea of constraint generation is to
solve problem (37) with constraint (37e) enforced only at a finite set of
points $\bar{\mathcal{V}}_{k}\subset\mathcal{V}_{k}$, to obtain a candidate
solution
$(\bar{\mathbf{a}},\bar{\mathbf{u}},\bar{\mathbf{w}},\bar{\mathbf{x}},\bar{\mathbf{y}})$.
We then test whether this candidate solution satisfies constraint (37e) for
each $k$; by the equivalence (24), it is sufficient to simply evaluate
$F(w_{k},x_{k,1},x_{k,0},u_{k})$ and check whether it is less than or equal to
zero. If it is, we conclude that
$(\bar{\mathbf{a}},\bar{\mathbf{u}},\bar{\mathbf{w}},\bar{\mathbf{x}},\bar{\mathbf{y}})$
satisfies constraint (37e) for customer type $k$. If not, then we add the
$(\bar{w}_{k},\bar{x}_{k,1},\bar{x}_{k,0},\bar{u}_{k})$ to the set
$\bar{\mathcal{V}}_{k}$ and solve the problem again. In this process, if a
solution
$(\bar{\mathbf{a}},\bar{\mathbf{u}},\bar{\mathbf{w}},\bar{\mathbf{x}},\bar{\mathbf{y}})$
satisfies constraint (37e) for all customer types $k$, we conclude that it is
the optimal one.

We comment on two important aspects of this approach. First, this approach is
attractive because it represents the convex constraint
$F(w_{k},x_{k,1},x_{k,0},u_{k})\leq 0$ for each $k$ through a family of linear
constraints, quantified over the finite set $\bar{\mathcal{V}}_{k}$. Thus, the
problem is a mixed-integer linear program. Such a problem can be solved using
commercial solvers for such problems like Gurobi or CPLEX. Second, in
implementing a constraint generation procedure for solving problem (37), one
can use lazy constraint generation. In traditional constraint generation, one
re-solves problem (37) from scratch using branch-and-bound whenever one
discovers a violated instance of constraint (37e). In lazy constraint
generation, one solves problem (37) using a single branch-and-bound tree, and
checks whether constraint (37e) is satisfied for each integer solution that is
encountered; if a violated instance of constraint (37e) is found, it can then
be added to the current node in the branch-and-bound tree. This type of
approach is potentially more efficient as one does not re-solve the problem
from scratch each time that a violated constraint is added. Indeed, lazy
constraint generation has been used in a number of large-scale applications of
integer programming, such as facility location problems (Fischetti et al.
2017), robust optimization (Bertsimas et al. 2016) and first-choice product
line design (Bertsimas and Mišić 2019).

##  5 Extensions

In this section, we discuss how to extend our base model, which considers the
share-of-choice objective, to two different objective functions: the expected
per-customer profit (Section 5.1) and the geometric mean of the customer
purchase probability (Section 5.2).

###  5.1 Extension to Expected Profit Maximization

While our final mixed-integer convex program (14) corresponds to the share-of-
choice objective, it turns out that it is straightforward to generalize the
model so as to optimize a profit-based objective. In particular, suppose that
the marginal profit of a design $\mathbf{a}$ is given by a function
$R(\mathbf{a})$ defined as

$R(\mathbf{a})=r_{0}+\sum_{i=1}^{n}r_{i}a_{i}.$

In other words, the profit $R(\mathbf{a})$ is a linear function of the binary
attributes. One can model various types of profit structures with this
assumption. For example, if all of the attributes correspond to non-price
features that affect the cost of the product, then one can set $r_{0}$ to be
the price of the product (a positive quantity), and each $r_{i}$ to be the
marginal incremental cost of attribute $i$ (a negative quantity).

With this assumption, the logit-based expected profit product design problem
can be written as

$\underset{\mathbf{a}\in\mathcal{A}}{\text{maximize}}\quad
R(\mathbf{a})\cdot\left[\sum_{k=1}^{K}\lambda_{k}\cdot\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\right].$
(38)

Using similar steps as for the SOCPD problem, one can derive the following
bilinear formulation with a bilinear objective function:

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{x}}{\text{maximize}}$
$\displaystyle R(\mathbf{a})\cdot\left[\sum_{k=1}^{K}\lambda_{k}\cdot
x_{k,1}\right]$ (39a) subject to
$\displaystyle\text{constraints~{}\eqref{prob:bilinear_x_unitsum} -
\eqref{prob:bilinear_x_nonnegative}}.$ (39b)

For the objective function, observe that we can re-write it as

$\displaystyle R(\mathbf{a})\cdot\left[\sum_{k=1}^{K}\lambda_{k}\cdot
x_{k,1}\right]$
$\displaystyle=\left(r_{0}+\sum_{i=1}^{n}r_{i}a_{i}\right)\cdot\left[\sum_{k=1}^{K}\lambda_{k}\cdot
x_{k,1}\right]$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\cdot\left[r_{0}x_{k,1}+\sum_{i=1}^{n}r_{i}\cdot
a_{i}x_{k,1}\right].$

Notice that this last expression includes terms of the form $a_{i}x_{k,1}$,
which we can already represent through the variables $y_{k,i}$ introduced for
problem (14). Problem (38) can therefore be exactly reformulated as the
following mixed-integer convex program:

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{w},\mathbf{x},\mathbf{y}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot\left[r_{0}x_{k,1}+\sum_{i=1}^{n}r_{i}\cdot
y_{k,i}\right]$ (40a) subject to constraints (14b) - (14l). (40b)

Thus, the expected profit product design problem can be handled through the
same formulation as problem (14), only with a modified objective function.

###  5.2 Extension to Geometric Mean Maximization

To motivate this approach, recall that the logit-based SOCPD problem (1)
involves maximizing the fraction of customers who purchase a product. This
objective function is formulated as the weighted sum of the logit
probabilities of each customer purchasing the product. An alternate way of
understanding this objective is that it is the weighted arithmetic mean of the
logit probabilities of the customer types.

Instead of formulating the objective of our product design problem as an
arithmetic mean, we will instead consider formulating the problem using the
geometric mean. This leads to the following optimization problem:

$\underset{\mathbf{a}\in\mathcal{A}}{\text{maximize}}\prod_{k=1}^{K}\left[\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\right]^{\lambda_{k}}.$
(41)

In other words, rather than trying to optimize the weighted arithmetic mean of
the purchase probabilities, this problem seeks to optimize the weighted
geometric mean of the purchase probabilities, where the weights indicate the
relative proportion of each customer type in the population.

This formulation is interesting to consider because it provides a lower bound
on the optimal value of problem (1).

###### Proposition 5.1

Let $Z^{*}_{AM}$ and $Z^{*}_{GM}$ be the optimal objective values of problems
(1) and (41), respectively. Then $Z^{*}_{AM}\geq Z^{*}_{GM}$.

#### Proof:

Let $\mathbf{a}$ be the optimal solution of problem (41). We have that

$\displaystyle Z^{*}_{GM}$
$\displaystyle=\prod_{k=1}^{K}\left[\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\right]^{\lambda_{k}}$
$\displaystyle\leq\sum_{k=1}^{K}\lambda_{k}\cdot\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}$
$\displaystyle\leq Z^{*}_{AM},$

where the first step follows by the arithmetic-geometric mean inequality and
the second step by the definition of $Z^{*}_{AM}$ as the optimal objective
value of (1). $\square$
Thus, by solving problem (41), we obtain a lower bound on problem (1); by
evaluating the objective value of the optimal solution of (41) within problem
(1), we obtain an even stronger lower bound. The solution of the geometric
mean problem (41) can be used as an approximate solution of the arithmetic
mean problem (1).

We can further analyze the approximation quality of the solution of problem
(41) with regard to the original problem. With a slight abuse of notation, let
us use $\mathbf{x}=(x_{1},\dots,x_{K})$ to denote the vector of purchase
probabilities for the $K$ different customer types, and let us use
$\mathbf{x}(\mathbf{a})$ to denote the vector of purchase probabilities for a
given product $\mathbf{a}\in\mathcal{A}$:

$\mathbf{x}(\mathbf{a})=(x_{1}(\mathbf{a}),\dots,x_{K}(\mathbf{a}))=\left(\frac{\exp(u_{1}(\mathbf{a}))}{1+\exp(u_{1}(\mathbf{a}))},\dots,\frac{\exp(u_{K}(\mathbf{a}))}{1+\exp(u_{K}(\mathbf{a}))}\right).$

Let us also use $\mathcal{X}$ be the set of achievable customer choice
probabilities, given by

$\mathcal{X}=\left\\{\mathbf{x}\in[0,1]^{K}\mid
x_{k}=\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\ \text{for
some}\ \mathbf{a}\in\mathcal{A}\right\\}.$ (42)

Given a vector of choice probabilities $\mathbf{x}$, we use the function
$f:\mathcal{X}\to\mathbb{R}$ to denote the weighted arithmetic mean of
$\mathbf{x}$, with the weights
$\boldsymbol{\lambda}=(\lambda_{1},\dots,\lambda_{K})$:

$f(\mathbf{x})=\sum_{k=1}^{K}\lambda_{k}x_{k}.$ (43)

Similarly, we use $g:\mathcal{X}\to\mathbb{R}$ to denote the weighted
geometric mean of $\mathbf{x}$:

$g(\mathbf{x})=\prod_{k=1}^{K}x_{k}^{\lambda_{k}}.$ (44)

Thus, in terms of these two functions, the original logit-based SOCPD problem
can be written as $\max_{\mathbf{a}\in\mathcal{A}}f(\mathbf{x}(\mathbf{a}))$,
while the geometric mean problem (41) can be written as
$\max_{\mathbf{a}\in\mathcal{A}}g(\mathbf{x}(\mathbf{a}))$. We then have the
following guarantee on the performance of any solution of the geometric mean
problem (41) with respect to the objective of the original logit-based SOCPD
problem (1).

###### Theorem 5.2

Let $L$ and $U$ be nonnegative numbers satisfying $L\leq x_{k}(\mathbf{a})\leq
U$ for all $k\in\\{1,\dots,K\\}$ and $\mathbf{a}\in\mathcal{A}$. Let
$\mathbf{a}^{*}\in\arg\max_{\mathbf{a}\in\mathcal{A}}f(\mathbf{x}(\mathbf{a}))$
be a solution of the arithmetic mean problem, and
$\hat{\mathbf{a}}\in\arg\max_{\mathbf{a}\in\mathcal{A}}g(\mathbf{x}(\mathbf{a}))$
be a solution of the geometric mean problem. Then the geometric mean solution
$\hat{\mathbf{a}}$ satisfies

$f(\mathbf{x}(\hat{\mathbf{a}}))\geq\frac{1}{\sum_{k=1}^{K}\lambda_{k}\left(\frac{U}{L}\right)^{1-\lambda_{k}}}\cdot
f(\mathbf{x}(\mathbf{a}^{*})).$

The proof of Theorem 5.2 (see Section 8.2 of the ecompanion) follows by
finding constants $\underline{\alpha}$ and $\overline{\alpha}$ such that
$\underline{\alpha}f(\mathbf{x})\leq
g(\mathbf{x})\leq\overline{\alpha}g(\mathbf{x})$ for any vector of
probabilities $\mathbf{x}$, and then showing that a solution
$\hat{\mathbf{a}}$ that maximizes $g(\mathbf{x}(\cdot))$ must be within a
factor $\underline{\alpha}/\overline{\alpha}$ of the optimal objective of the
arithmetic mean problem. Theorem 5.2 is valuable because it provides some
intuition for when a solution $\hat{\mathbf{a}}$ obtained by solving the
geometric mean problem (41) will be close in performance to the optimal
solution of the original (arithmetic mean) problem (1). In particular, the
factor $\Gamma$ defined as

$\Gamma=\underline{\alpha}\,/\,\overline{\alpha}=\frac{1}{\sum_{k=1}^{K}\lambda_{k}\left(\frac{U}{L}\right)^{1-\lambda_{k}}}$

is decreasing in the ratio $U/L$. Recall that $U$ is an upper bound on the
highest purchase probability that can be achieved for any customer type, while
$L$ is similarly a lower bound on the lowest purchase probability that can be
achieved for any customer type. When the ratio $U/L$ is large, it implies that
there is a large range of choice probabilities spanned by the set of product
designs $\mathcal{A}$. On the other hand, when $U/L$ is small, then the range
of choice probabilities is smaller. Thus, the smaller the range of choice
probabilities spanned by the set $\mathcal{A}$ is small, the closer we should
expect the geometric mean solution to be in performance to the optimal
solution of the arithmetic mean problem. Figure 1 visualizes the dependence of
the factor $\Gamma$ on $U/L$ when $\boldsymbol{\lambda}$ is assumed to be the
discrete uniform distribution and $K$ is varied.

Figure 1: Plot of the approximation factor $\Gamma$ as a function of the ratio
$U/L$, for different values of $K$. Note that $\boldsymbol{\lambda}$ is
assumed to be the uniform distribution, i.e.,
$\boldsymbol{\lambda}=(1/K,\dots,1/K)$.

In addition to the ratio $U/L$, the factor $\Gamma$ is also affected by
$\boldsymbol{\lambda}$. It can be verified that the factor $\Gamma$ is
minimized when the customer type distribution is uniform, i.e.,
$\boldsymbol{\lambda}=(1/K,\dots,1/K)$. In addition, it can also be verified
that when $\boldsymbol{\lambda}$ is such that $\lambda_{k}=1$ for a single
customer type (and $\lambda_{k^{\prime}}=0$ for all others), the factor
$\Gamma$ becomes 1. Thus, the more “unbalanced” the customer type distribution
$\boldsymbol{\lambda}$ is, the closer the geometric mean solution should be in
performance to the optimal solution of the arithmetic mean problem.

We will see in our numerical experiments that the solution of problem (41) is
often significantly better than the lower bound of Theorem 5.2.

Lastly, with regard to the bounds $U$ and $L$, we note that these can be found
easily. In particular, for each customer type $k$, one can compute
$u_{k,\max}=\max_{\mathbf{a}\in\mathcal{A}}u_{k}(\mathbf{a})$ and
$u_{k,\min}=\min_{\mathbf{a}\in\mathcal{A}}u_{k}(\mathbf{a})$, which are the
highest and lowest utilities that one can attain for customer type $k$; for
many common choices of $\mathcal{A}$ this should be an easy problem. (For
example, if $\mathcal{A}$ is simply $\\{0,1\\}^{n}$, we can find $u_{k,\max}$
by setting to 1 those attributes for which $\beta_{k,i}>0$ and setting to 0
all other attributes; $u_{k,\min}$ can be found in a similar manner). One can
then compute $L$ and $U$ as

$\displaystyle U$
$\displaystyle=\max_{k=1,\dots,K}\frac{\exp(u_{k,\max})}{1+\exp(u_{k,\max})},$
$\displaystyle L$
$\displaystyle=\min_{k=1,\dots,K}\frac{\exp(u_{k,\min})}{1+\exp(u_{k,\min})}.$

We now turn our attention to how one can solve problem (41). While problem
(41) is still a challenging nonconvex problem, it is possible to transform it
into a mixed-integer convex problem. To do so, we consider taking the
logarithm of the objective function of (41):

$\displaystyle\log\prod_{k=1}^{K}\left[\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\right]^{\lambda_{k}}$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\log\left(\frac{\exp(u_{k}(\mathbf{a}))}{1+\exp(u_{k}(\mathbf{a}))}\right)$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\cdot\left(u_{k}(\mathbf{a})-\log(1+\exp(u_{k}(\mathbf{a})))\right).$

This transformation is useful because the logarithm function is monotonic, so
any solution that maximizes the logarithm of the objective function maximizes
the objective function itself. This leads to the following mixed-integer
convex program:

$\displaystyle\underset{\mathbf{a},\mathbf{u}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot\left(u_{k}-\log(1+\exp(u_{k}))\right)$
(45a) subject to $\displaystyle
u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall\
k\in\\{1,\dots,K\\},$ (45b) $\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$
(45c) $\displaystyle a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\}.$
(45d)

This problem can be solved using a similar gradient-based constraint
generation approach as the one described in Section 4.2. Alternatively, as in
Section 4.1, one can also translate this problem into a mixed-integer conic
program using the exponential cone, leading to the following formulation:

$\displaystyle\underset{\mathbf{a},\mathbf{u},\mathbf{v},\mathbf{t},\boldsymbol{\phi}}{\text{maximize}}$
$\displaystyle\sum_{k=1}^{K}\lambda_{k}\cdot t_{k}$ (46a) subject to
$\displaystyle u_{k}=\beta_{k,0}+\sum_{i=1}^{n}\beta_{k,i}a_{i},\quad\forall\
k\in\\{1,\dots,K\\},$ (46b) $\displaystyle t_{k}+\phi_{k}\leq
u_{k},\quad\forall\ k\in\\{1,\dots,K\\},$ (46c) $\displaystyle
v_{k,1}+v_{k,0}\leq 1,\quad\forall\ k\in\\{1,\dots,K\\},$ (46d)
$\displaystyle(v_{k,1},1,u_{k}-\phi_{k})\in\mathcal{K}_{\exp},\quad\forall\
k\in\\{1,\dots,K\\},$ (46e)
$\displaystyle(v_{k,0},1,-\phi_{k})\in\mathcal{K}_{\exp},\quad\forall\
k\in\\{1,\dots,K\\},$ (46f) $\displaystyle\mathbf{C}\mathbf{a}\leq\mathbf{d},$
(46g) $\displaystyle a_{i}\in\\{0,1\\},\quad\forall i\in\\{1,\dots,n\\}.$
(46h)

While problem (45) and problem (46) bear some resemblance to their
counterparts (14) and (22), they differ in that the choice probabilities
$x_{k,1}$ and $x_{k,0}$ do not explicitly appear. More importantly, they do
not involve any linearization of bilinear terms of the form $x_{k,1}\cdot
a_{i}$. These differences are important because they make problems (45) and
(46) much easier to solve than (14) and (22).

##  6 Numerical Experiments

In this section, we present the results of our numerical experiments. Section
6.1 presents the results of our experiments with synthetically generated
problem instances, while Section 6.2 presents the results of our experiments
with instances derived from real conjoint datasets. All of our numerical
experiments are implemented in the Julia technical computing language, version
1.5 (Bezanson et al. 2017) using the JuMP package (Julia for Mathematical
Programming; see Dunning et al. 2017), and executed on a 2017 Apple MacBook
Pro with a 3.1GHz Intel i7 quad core CPU and 16GB of memory.

###  6.1 Experiments with synthetic instances

In our first set of numerical experiments, we test our approaches on
synthetically generated problem instances. We generate these instances as
follows. For a fixed number of binary attributes $n$ and number of customer
types $K$, we randomly generate the partworth $\beta_{k,i}$ by drawing an
independent uniformly distributed random number in the interval $[-10,+10]$
for each customer type $k$ and attribute $i$. For the intercept $\beta_{k,0}$
of the utility function, we assume that there are three competitive offerings
$\mathbf{a}^{\prime},\mathbf{a}^{\prime\prime},\mathbf{a}^{\prime\prime\prime}$
which are drawn independently and uniformly at random from $\\{0,1\\}^{n}$,
and thus the value of $\beta_{k,0}$ is computed as

$\beta_{k,0}=-\log\left(\exp(u_{k}(\mathbf{a}^{\prime}))+\exp(u_{k}(\mathbf{a}^{\prime\prime}))+\exp(u_{k}(\mathbf{a}^{\prime\prime\prime})\right).$
(47)

We assume that the probability $\lambda_{k}$ of each customer type $k$ is set
to $1/K$. We vary $n\in\\{10,20,30\\}$ and $K\in\\{10,20,30,40\\}$. For each
combination of $n$ and $K$, we generate 5 replications. We do not impose any
additional constraints on the set of feasible product vectors, i.e., we omit
the constraint $\mathbf{C}\mathbf{a}\leq\mathbf{d}$ from the formulations. We
compare the mixed-integer conic program (22) solved via Mosek (indicated by
MICP), the gradient-based constraint generation method (formulation (37))
implemented in Gurobi (indicated by GCG) and the geometric mean problem (46)
solved via Mosek (indicated by GM). For MICP and GCG, we impose a 1 hour
computation time limit.

Table 1 shows the results. The first three columns report the objective value
of the three methods, with respect to the logit-based share-of-choice
objective. The next two columns report the optimality gap, which is the
relative difference $(\mathrm{UB}-\mathrm{LB})/\mathrm{UB}$, where UB is the
best upper bound found by Mosek/Gurobi, while LB is the objective value of the
best product vector found by Mosek/Gurobi) for the MICP and GCG methods. The
subsequent column reports the achieved approximation gap of the GM solution,
which is the ratio of the difference between the objective of the GM solution
and the best objective of any of the three solution methods, and the best
objective over the three methods. The last three columns report the
computation time required of each of the three methods. Each row corresponds
to a combination of $n$ and $K$, and all performance metrics are averaged over
the 5 replications.

|  | Objective Value | Gap (%) | Computation Time (s)
---|---|---|---|---
$n$ | $K$ | GCG | MICP | GM | GCG | MICP | GM | GCG | MICP | GM
10 | 10 | 0.591 | 0.591 | 0.422 | 0.0 | 0.0 | 31.9 | 1.1 | 1.0 | 3.0
10 | 20 | 0.478 | 0.478 | 0.282 | 0.0 | 0.0 | 39.8 | 0.6 | 2.4 | 0.1
10 | 30 | 0.456 | 0.456 | 0.314 | 0.0 | 0.0 | 32.0 | 0.9 | 4.3 | 0.2
10 | 40 | 0.391 | 0.391 | 0.233 | 0.0 | 0.0 | 40.3 | 1.4 | 6.3 | 0.2
20 | 10 | 0.752 | 0.752 | 0.501 | 0.0 | 0.0 | 34.0 | 5.3 | 12.8 | 0.1
20 | 20 | 0.682 | 0.682 | 0.509 | 0.0 | 0.0 | 27.1 | 32.4 | 70.1 | 0.2
20 | 30 | 0.529 | 0.529 | 0.341 | 0.0 | 0.0 | 36.0 | 149.3 | 360.1 | 0.3
20 | 40 | 0.477 | 0.477 | 0.295 | 0.0 | 0.0 | 38.0 | 504.8 | 636.5 | 0.3
30 | 10 | 0.916 | 0.916 | 0.827 | 0.0 | 0.0 | 10.0 | 30.3 | 104.0 | 0.1
30 | 20 | 0.761 | 0.761 | 0.586 | 0.0 | 6.6 | 24.5 | 1524.4 | 2992.3 | 0.3
30 | 30 | 0.668 | 0.681 | 0.445 | 15.8 | 17.2 | 36.2 | 3600.0 | 3600.7 | 0.3
30 | 40 | 0.538 | 0.536 | 0.325 | 30.3 | 31.9 | 40.5 | 3600.0 | 3600.6 | 0.4
Table 1: Results for numerical experiment with synthetic data.

From Table 1, we can see that for $n\leq 20$, most of the instances can be
solved to complete optimality by MICP or GCG within the 1 hour time limit. For
$n=30$, the instances become more challenging, and their difficulty increases
as $K$ increases; for $K=10$ and $K=20$, GCG and MICP are in general able to
solve the problems to optimality within the one hour time limit, while for
$K=30$ and $K=40$, both methods terminate with a suboptimal solution, with an
average optimality gap of roughly 15-17% (for $K=30$) and an average
optimality gap of roughly 30-32% (for $K=40$). For the GM method, we can see
that it obtains solutions of modest quality with an approximation gap ranging
between 10 and 40%. For these instances, the factor of $\Gamma$ (cf. Theorem
5.2) is in general extremely small (less than $10^{-11}$, which would
correspond to an approximation gap of close to 100%) because for each customer
type it is possible to achieve utilities that are significantly smaller and
greater than zero; our results thus show that the GM method is able to achieve
significantly better solutions. In addition, the computation time required for
GM is a fraction of the time required by the other methods.

###  6.2 Experiments with instances based on real conjoint datasets

In our second set of numerical experiments, we test our approaches using
instances built with logit models estimated from real conjoint datasets. We
use four different data sets: timbuk2, a dataset on preferences for laptop
bags produced by Timbuk2 from Toubia et al. (2003) (see also Belloni et al.
2008, Bertsimas and Mišić 2017, 2019, which also use this data set for profit-
based product line design); bank, a dataset on preferences for credit cards
from Allenby and Ginter (1995) (accessed through the bayesm package for R; see
Rossi 2019); candidate, a dataset on preferences for a hypothetical
presidential candidate from Hainmueller et al. (2014); immigrant, a dataset on
preferences for a hypothetical immigrant from Hainmueller et al. (2014). The
high-level characteristics of each dataset are summarized in Table 2 below.

We note that for some of these datasets, the product design problem is of a
more hypothetical nature. For example, for candidate, the problem is to
“design” a political candidate maximizing the share of voters who would vote
for that candidate. Similarly, for immigrant, the problem is to “design” an
ideal immigrant that would maximize the fraction of people who would support
granting admission to such an immigrant. Clearly, it is not possible to
“create” a political candidate or immigrant with certain characteristics.
Despite this, we believe that identifying what an optimal “product” would be
for these data sets, and what share-of-choice such a product would achieve,
would still be insightful. Notwithstanding these concerns, these datasets are
still valuable from the perspective of verifying that our optimization
methodology can solve problem instances derived from real data.

Dataset | Respondents | Attributes | Attribute Levels | $n$
---|---|---|---|---
bank | 946 | 7 | $4\times 4\times 3\times 3\times 3\times 2\times 2$ | 14
candidate | 311 | 8 | $6\times 2\times 6\times 6\times 6\times 6\times 6\times 2$ | 32
immigrant | 1396 | 9 | $7\times 2\times 10\times 3\times 11\times 4\times 4\times 5\times 4$ | 41
timbuk2 | 330 | 10 | $7\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2$ | 15
Table 2: Summary of real conjoint datasets used in Section 6.2. The column
“Attributes” indicates the number of attributes, and “Attribute Levels”
indicates the structure of each attribute (e.g., $2\times 3\times 5$ indicates
that the product has one attribute with two levels, followed by one with three
levels, followed by one with five levels). The column labelled $n$ indicates
the resulting number of binary attributes when the dataset is used to
formulate the logit-based SOCPD problem.

For each data set, we develop two different types of logit models, which we
summarize below.

  1. 1.

_Latent-class logit_ : For each dataset, we estimate a latent-class (LC)
multinomial logit with a finite number of classes $K$. We estimate each model
using a custom implementation of the expectation-maximization (EM) algorithm
(Train 2009). For each dataset, we run the EM algorithm from five randomly
chosen starting points, and retain the model with the lowest log likelihood.
To ensure numerical stability, we impose the constraint
$-10\leq\beta_{k,i}\leq 10$ for each $i$ in the M step of the algorithm. We
vary the number of classes $K$ in the set $\\{5,10,15,20,30,40,50\\}$. Thus,
in the associated logit-based SOCPD instance, each customer class corresponds
to one of the customer types and the customer type probability $\lambda_{k}$
is the class $k$ probability estimated via EM.

  2. 2.

_Hierarchical Bayes_ : For each dataset, we estimate a mixture multinomial
logit (MMNL) model with a multivariate normal mixture distribution using the
hierarchical Bayesian (HB) approach; we use a standard specification with
normal-inverse Wishart second stage priors (see Section 9.2 of the ecompanion
for more details). We estimate this model using Markov chain Monte Carlo
(MCMC) via the bayesm package in R (Rossi 2019). We simulate 50,000 draws from
the posterior distribution of $(\beta_{r,1},\dots,\beta_{r,n})$ for each
respondent $r$, and thin the draws to retain every 100th draw. Of those draws,
we retain the last $J=100$ draws, which we denote as
$(\beta^{j}_{r,1},\dots,\beta^{j}_{r,n})$, where $j\in\\{1,\dots,J\\}$, and we
compute the average partworth vector $(\beta_{k,1},\dots,\beta_{k,n})$ as

$(\beta_{r,1},\dots,\beta_{r,n})=(\frac{1}{J}\sum_{j=1}^{J}\beta^{j}_{r,1},\dots,\frac{1}{J}\sum_{j=1}^{J}\beta^{j}_{r,n}).$
(48)

This approach leads to an estimate of the partworths for each of the
respondents. In the corresponding logit-based SOCPD instance, the number of
customer types $K$ corresponds to the number of respondents, and the
probability of each customer type $k$ is $1/K$.

Before continuing, we note that there may be other approaches for defining a
mixture of logits model. (For example, given an estimate of the mean and
covariance matrix of a normal mixture distribution defining a mixture logit
model, one could sample a set of $K$ partworth vectors and use those as the
set of customer types, with each $\lambda_{k}=1/K$.) We emphasize that our
goal is not to advocate for one approach over another. The estimation
approaches described here are simply for the purpose of obtaining problem
instances that are of a realistic scale and correspond to real data. We note
that our optimization approach is agnostic to how the customer choice model is
constructed and is compatible with any estimation approach, so long as it
results in a finite set of customer types that each follow a logit model of
choice.

For each dataset, we define the set $\mathcal{A}$ to be the set of all binary
vectors of size $n$ that respect the attribute structure of the dataset; in
particular, for attributes that are not binary, we introduce constraints of
the form $\sum_{i\in S}a_{i}\leq 1$ as appropriate (cf. constraints (15) and
(16) in Section 3.2). For immigrant, we also follow Hainmueller et al. (2014)
in not allowing certain combinations of attributes (for example, it is not
possible for a hypothetical immigrant to be a doctor and have only a high
school education). We briefly describe the constraints for immigrant in
Section 9.3 of the ecompanion.

With regard to the no-purchase option, recall from Section 3.1 that the
constant part of each customer’s utility function, $\beta_{k,0}$, can be
thought of as the negative of the utility of the no-purchase option. We assume
that in each problem instance, each customer can choose from three different
competitive offerings which are defined using the same attributes as the
product that is to be designed. This is a standard assumption in the product
design and product line design literature (Belloni et al. 2008, Bertsimas and
Mišić 2017, 2019). For each dataset, we provide the details of the competitive
offerings in Section 9.4 of the ecompanion. The parameter $\beta_{k,0}$ is
then calculated in the same way as for the synthetic instances (see equation
(47)).

Table 3 shows the computation time and the objective value of all of the
different models for all four datasets; the columns containing the results
follow the same structure as Table 1. From this table, we can see that all of
the LC (latent class logit) instances can be solved to complete optimality
within roughly 3 minutes. For the HB instances, MICP and GCG are able to solve
the instances for bank, candidate and timbuk2 within approximately 25 minutes.
With regard to the geometric mean approach, we find that Mosek is able to
solve all of the instances very quickly (within 20 seconds in all cases). In
contrast to the synthetic instances, the geometric mean solution also tends to
perform well, achieving a share-of-choice that is on average only about 14%
below the best solution across all of the instances.

|  |  | Objective Value | Computation Time (s)
---|---|---|---|---
Dataset | Model | $K$ | GCG | MICP | GM | GCG | MICP | GM
bank | LC | 5 | 0.742 | 0.742 | 0.675 | 4.3 | 0.8 | 14.4
| LC | 10 | 0.749 | 0.749 | 0.685 | 0.3 | 1.0 | 0.0
| LC | 15 | 0.752 | 0.752 | 0.682 | 0.5 | 1.0 | 0.1
| LC | 20 | 0.719 | 0.719 | 0.687 | 0.5 | 1.6 | 0.1
| LC | 30 | 0.764 | 0.764 | 0.637 | 1.0 | 2.8 | 0.1
| LC | 40 | 0.757 | 0.757 | 0.665 | 1.3 | 3.6 | 0.1
| LC | 50 | 0.749 | 0.749 | 0.642 | 2.0 | 5.8 | 0.2
| HB | 946 | 0.817 | 0.817 | 0.812 | 380.6 | 373.1 | 2.2
candidate | LC | 5 | 0.626 | 0.626 | 0.509 | 1.4 | 4.8 | 0.0
| LC | 10 | 0.694 | 0.694 | 0.637 | 2.9 | 9.6 | 0.1
| LC | 15 | 0.670 | 0.670 | 0.651 | 4.5 | 13.2 | 0.1
| LC | 20 | 0.705 | 0.705 | 0.574 | 8.2 | 16.3 | 0.1
| LC | 30 | 0.627 | 0.627 | 0.534 | 29.0 | 53.2 | 0.1
| LC | 40 | 0.671 | 0.671 | 0.537 | 31.4 | 89.6 | 0.3
| LC | 50 | 0.710 | 0.710 | 0.680 | 192.0 | 102.5 | 0.4
| HB | 311 | 0.852 | 0.852 | 0.851 | 1581.5 | 452.6 | 0.9
immigrant | LC | 5 | 0.689 | 0.689 | 0.687 | 10.1 | 12.3 | 0.0
| LC | 10 | 0.738 | 0.738 | 0.688 | 5.6 | 14.0 | 0.1
| LC | 15 | 0.726 | 0.726 | 0.393 | 9.4 | 19.5 | 0.1
| LC | 20 | 0.756 | 0.756 | 0.552 | 6.4 | 32.7 | 0.2
| LC | 30 | 0.675 | 0.675 | 0.467 | 14.9 | 52.5 | 0.2
| LC | 40 | 0.724 | 0.724 | 0.344 | 14.6 | 75.7 | 0.2
| LC | 50 | 0.731 | 0.731 | 0.628 | 31.8 | 147.5 | 0.3
| HB | 1396 | 0.836 | 0.865 | 0.846 | 7201.3 | 7053.0 | 4.7
timbuk2 | LC | 5 | 0.519 | 0.519 | 0.510 | 0.2 | 0.9 | 0.0
| LC | 10 | 0.543 | 0.543 | 0.536 | 0.4 | 1.7 | 0.1
| LC | 15 | 0.567 | 0.567 | 0.430 | 0.6 | 2.1 | 0.1
| LC | 20 | 0.557 | 0.557 | 0.556 | 1.0 | 2.7 | 0.1
| LC | 30 | 0.620 | 0.620 | 0.436 | 1.0 | 3.6 | 0.1
| LC | 40 | 0.579 | 0.579 | 0.560 | 2.1 | 5.9 | 0.1
| LC | 50 | 0.628 | 0.628 | 0.446 | 2.0 | 6.2 | 0.2
| HB | 330 | 0.644 | 0.644 | 0.644 | 40.6 | 85.2 | 0.8
Table 3: Results for numerical experiment with real data.

Of the instances in Table 3, the immigrant HB instance appears to be the most
challenging. While Mosek is able to solve the MICP formulation to optimality
within 2 hours, GCG exhausts the 2 hour time limit and returns a suboptimal
solution with an optimality gap of about 12.6%. This performance is likely
because the GCG method needs to add a very large number of constraints due to
the large number of customer types. Moreover, the structure of the partworths
appears to pose some numerical difficulty, as it appears that solutions that
are near-optimal are such that the purchase probabilities are extremely close
to 1 or 0 for a large number of customer types. This can be problematic
because the constraints that GCG adds include terms of the form
$\log(x_{k,1})+1$ and $\log(x_{k,0})+1$ (derivatives of $x_{k,1}\log(x_{k,1})$
and $x_{k,0}\log(x_{k,0})$), which respectively blow up as $x_{k,1}$ and
$x_{k,0}$ approach 0.

In addition to the performance of the different methods, it is also
interesting to examine the optimal solutions. Table 4 visualizes the optimal
solution for the candidate dataset for the LC model with $K=20$ segments. The
table also shows the three outside options/competitive offerings that were
defined for this dataset. In addition, the table also shows the structure of a
heuristic solution, which is obtained by finding the vector $\mathbf{a}$ in
$\mathcal{A}$ that maximizes the average utility, i.e., that maximizes
$\sum_{k=1}^{K}\lambda_{k}u_{k}(\mathbf{a})$.

From this table, we can see that the optimal solution matches some of the
outside options on certain attributes (such as income and profession), but
differs on some (for example, age). In addition, while the optimal solution
does match the heuristic on many attributes, it differs on a couple of key
attributes, namely race/ethnicity (the optimal candidate is Black, while the
heuristic candidate is Asian American) and gender (the optimal candidate is
male, while the heuristic candidate is female). While this may appear to be a
minor difference, it results in a substantial difference in market share: the
heuristic candidate attracts a share of 0.563, while the optimal candidate
attracts a share of 0.705, which is an improvement of 25%. This illustrates
that intuitive solutions to the logit-based product design problem can be
suboptimal, and demonstrates the value of a principled optimization-based
approach to this problem.

Attribute | Outside | Outside | Outside | Optimal | Heuristic
---|---|---|---|---|---
| Option 1 | Option 2 | Option 3 | Solution | Solution
Age: 36 |  |  |  |  |
Age: 45 |  |  |  |  |
Age: 52 |  |  |  |  |
Age: 60 |  |  |  |  |
Age: 68 |  |  |  |  |
Age: 75 |  |  |  |  |
Military Service: Did not serve |  |  |  |  |
Military Service: Served |  |  |  |  |
Religion: None |  |  |  |  |
Religion: Jewish |  |  |  |  |
Religion: Catholic |  |  |  |  |
Religion: Mainline protestant |  |  |  |  |
Religion: Evangelical protestant |  |  |  |  |
Religion Mormon |  |  |  |  |
College: No BA |  |  |  |  |
College: Baptist college |  |  |  |  |
College: Community college |  |  |  |  |
College: State university |  |  |  |  |
College: Small college |  |  |  |  |
College: Ivy League university |  |  |  |  |
Income: 32K |  |  |  |  |
Income: 54K |  |  |  |  |
Income: 65K |  |  |  |  |
Income: 92K |  |  |  |  |
Income: 210K |  |  |  |  |
Income 5.1M |  |  |  |  |
Profession: Business owner |  |  |  |  |
Profession: Lawyer |  |  |  |  |
Profession: Doctor |  |  |  |  |
Profession: High school teacher |  |  |  |  |
Profession: Farmer |  |  |  |  |
Profession: Car dealer |  |  |  |  |
Race/Ethnicity: White |  |  |  |  |
Race/Ethnicity: Native American |  |  |  |  |
Race/Ethnicity: Black |  |  |  |  |
Race/Ethnicity: Hispanic |  |  |  |  |
Race/Ethnicity: Caucasian |  |  |  |  |
Race/Ethnicity: Asian American |  |  |  |  |
Gender: Male |  |  |  |  |
Gender: Female |  |  |  |  |
Table 4: Attributes of outside options, optimal solution and heuristic
solution for candidate LC-MNL model with $K=20$ segments.

##  7 Conclusions

In this paper, we have studied the logit-based share-of-choice product design
problem. While this problem is theoretically intractable, we show how it is
possible to transform this problem into a mixed-integer convex optimization
problem. Our transformation leverages an alternate characterization of logit
choice probabilities arising from the representative agent model, which may be
of utility in other optimization models involving logit models. We propose two
practically viable approaches for solving this problem: one based on further
reformulating the problem as a mixed-integer conic program involving the
exponential cone, which can be directly solved by cutting edge solvers; and
the other based on gradient-based constraint generation, which allows the
problem to be solved as a mixed-integer linear program. We also show how our
methodology can be extended to handle expected profit rather than share-of-
choice, and how our methodology can also be used to optimize the geometric
mean of the purchase probabilities, leading to an approximation algorithm for
the original share-of-choice problem. Lastly, our numerics show how our
approach can obtain high quality solutions to large instances, whether
generated synthetically or from real conjoint data, within reasonable time
limits. To the best of our knowledge, this is the first methodology for
solving the logit-based share-of-choice product design problem to provable
optimality.

The perspective article of Hauser, Tellis, and Griffin (2006), published 15
years ago, predicted that “[with] the advent of more powerful computers,
improved models of situational consumer decision-making processes, greater
understanding of competitive response, and improved optimization algorithms in
operations research, we expect to see a renewed interest in the use of math
programming to inform product design.” Since the publication of that paper,
the science and technology of mixed-integer convex optimization have advanced
tremendously, and new breakthroughs continue to be made. We hope that our
paper will encourage and motivate further exploration of mixed-integer convex
optimization as a methodology in the area of product design, and in marketing
science more generally.

## Acknowledgments

The authors thank the authors of Toubia et al. (2003), Hainmueller et al.
(2014) and Allenby and Ginter (1995) for making their data sets available,
which were used in the experiments in Section 6.2.

## References

  * Allenby and Ginter [1995] G. M. Allenby and J. L. Ginter.  Using extremes to design products and segment markets.  _Journal of Marketing Research_ , 32(4):392–403, 1995.
  * Anderson et al. [2020] R. Anderson, J. Huchette, W. Ma, C. Tjandraatmadja, and J. P. Vielma.  Strong mixed-integer programming formulations for trained neural networks.  _Mathematical Programming_ , pages 1–37, 2020.
  * Anderson et al. [1988] S. P. Anderson, A. De Palma, and J.-F. Thisse.  A representative consumer theory of the logit model.  _International Economic Review_ , pages 461–466, 1988.
  * Atamtürk et al. [2012] A. Atamtürk, G. Berenguer, and Z.-J. M. Shen.  A conic integer programming approach to stochastic joint location-inventory problems.  _Operations Research_ , 60(2):366–381, 2012.
  * Balakrishnan and Jacob [1996] P. V. Balakrishnan and V. S. Jacob.  Genetic algorithms for product design.  _Management Science_ , 42(8):1105–1117, 1996\.
  * Belloni et al. [2008] A. Belloni, R. Freund, M. Selove, and D. Simester.  Optimizing product line designs: Efficient methods and comparisons.  _Management Science_ , 54(9):1544–1552, 2008\.
  * Benson and Sağlam [2013] H. Y. Benson and Ü. Sağlam.  _Mixed-Integer Second-Order Cone Programming: A Survey_ , chapter Chapter 2, pages 13–36.  INFORMS, 2013.  10.1287/educ.2013.0115.  URL https://pubsonline.informs.org/doi/abs/10.1287/educ.2013.0115.
  * Bertsimas and Mišić [2017] D. Bertsimas and V. V. Mišić.  Robust product line design.  _Operations Research_ , 65(1):19–37, 2017.
  * Bertsimas and Mišić [2019] D. Bertsimas and V. V. Mišić.  Exact first-choice product line optimization.  _Operations Research_ , 67(3):651–670, 2019.
  * Bertsimas et al. [2016] D. Bertsimas, I. Dunning, and M. Lubin.  Reformulation versus cutting-planes for robust optimization.  _Computational Management Science_ , 13(2):195–217, 2016.
  * Besharati et al. [2006] B. Besharati, L. Luo, S. Azarm, and P. K. Kannan.  Multi-objective single product robust optimization: An integrated design and marketing approach.  _ASME Journal of Mechanical Design_ , 128(8):884–892, 2006.
  * Bezanson et al. [2017] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah.  Julia: A fresh approach to numerical computing.  _SIAM Review_ , 59(1):65–98, 2017.
  * Boyd and Vandenberghe [2004] S. P. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Camm et al. [2006] J. D. Camm, J. J. Cochran, D. J. Curry, and S. Kannan.  Conjoint optimization: An exact branch-and-bound algorithm for the share-of-choice problem.  _Management Science_ , 52(3):435–447, 2006.
  * Chen and Hausman [2000] K. D. Chen and W. H. Hausman.  Mathematical properties of the optimal product line selection problem using choice-based conjoint analysis.  _Management Science_ , 46(2):327–332, 2000.
  * Coey et al. [2020] C. Coey, M. Lubin, and J. P. Vielma.  Outer approximation with conic certificates for mixed-integer convex problems.  _Mathematical Programming Computation_ , pages 1–45, 2020.
  * Dunning et al. [2017] I. Dunning, J. Huchette, and M. Lubin.  Jump: A modeling language for mathematical optimization.  _SIAM Review_ , 59(2):295–320, 2017.
  * Feng et al. [2017] G. Feng, X. Li, and Z. Wang.  On the relation between several discrete choice models.  _Operations research_ , 65(6):1516–1525, 2017\.
  * Ferreira et al. [2016] K. J. Ferreira, B. H. A. Lee, and D. Simchi-Levi.  Analytics for an online retailer: Demand forecasting and price optimization.  _Manufacturing & Service Operations Management_, 18(1):69–88, 2016.
  * Fischetti et al. [2017] M. Fischetti, I. Ljubić, and M. Sinnl.  Redesigning benders decomposition for large-scale facility location.  _Management Science_ , 63(7):2146–2162, 2017\.
  * Garey and Johnson [1979] M. R. Garey and D. S. Johnson.  _Computers and intractability_.  W. H. Freeman New York, 1979.
  * Green et al. [2004] P. E. Green, A. M. Krieger, and Y. Wind.  _Buyer Choice Simulators, Optimizers, and Dynamic Models_ , pages 169–199.  Springer US, Boston, MA, 2004.
  * Hainmueller et al. [2014] J. Hainmueller, D. J. Hopkins, and T. Yamamoto.  Causal inference in conjoint analysis: Understanding multidimensional choices via stated preference experiments.  _Political analysis_ , 22(1):1–30, 2014.
  * Hauser et al. [2006] J. Hauser, G. J. Tellis, and A. Griffin.  Research on innovation: A review and agenda for marketing science.  _Marketing science_ , 25(6):687–717, 2006.
  * Hofbauer and Sandholm [2002] J. Hofbauer and W. H. Sandholm.  On the global convergence of stochastic fictitious play.  _Econometrica_ , 70(6):2265–2294, 2002.
  * Huchette and Vielma [2017] J. Huchette and J. P. Vielma.  Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools.  _arXiv preprint arXiv:1708.00050_ , 2017.
  * Kohli and Krishnamurti [1987] R. Kohli and R. Krishnamurti.  A heuristic approach to product design.  _Management Science_ , pages 1523–1533, 1987.
  * Kohli and Krishnamurti [1989] R. Kohli and R. Krishnamurti.  Optimal product design using conjoint analysis: Computational complexity and algorithms.  _European Journal of Operational Research_ , 40(2):186–195, 1989.
  * Kohli and Sukumar [1990] R. Kohli and R. Sukumar.  Heuristics for product-line design using conjoint analysis.  _Management Science_ , 36(12):1464–1478, 1990\.
  * Kohli et al. [2019] R. Kohli, K. Boughanmi, and V. Kohli.  Randomized algorithms for lexicographic inference.  _Operations Research_ , 67(2):357–375, 2019.
  * Liu et al. [2020] M. Liu, Z. Pan, K. Xu, and D. Manocha.  New formulation of mixed-integer conic programming for globally optimal grasp planning.  _IEEE Robotics and Automation Letters_ , 5(3):4663–4670, 2020.
  * Lubin et al. [2017] M. Lubin, J. P. Vielma, and I. Zadik.  Mixed-integer convex representability.  _arXiv preprint arXiv:1706.05135_ , 2017.
  * Lubin et al. [2018] M. Lubin, E. Yamangil, R. Bent, and J. P. Vielma.  Polyhedral approximation in mixed-integer convex optimization.  _Mathematical Programming_ , 172(1):139–168, 2018\.
  * Lubin et al. [2019] M. Lubin, Y. Dvorkin, and L. Roald.  Chance constraints for improving the security of ac optimal power flow.  _IEEE Transactions on Power Systems_ , 34(3):1908–1917, 2019.
  * Luo [2011] L. Luo.  Product line design for consumer durables: an integrated marketing and engineering approach.  _Journal of Marketing Research_ , 48(1):128–139, 2011.
  * Luo et al. [2005] L. Luo, P. K. Kannan, B. Besharati, and S. Azarm.  Design of robust new products under variability: Marketing meets design.  _Journal of Product Innovation Management_ , 22(2):177–192, 2005.
  * Mak et al. [2013] H.-Y. Mak, Y. Rong, and Z.-J. M. Shen.  Infrastructure planning for electric vehicles with battery swapping.  _Management Science_ , 59(7):1557–1575, 2013\.
  * McBride and Zufryden [1988] R. D. McBride and F. S. Zufryden.  An integer programming approach to the optimal product line selection problem.  _Marketing Science_ , 7(2):126–140, 1988.
  * Mišić [2020] V. V. Mišić.  Optimization of tree ensembles.  _Operations Research_ , 68(5):1605–1624, 2020\.
  * Mosek ApS [2021a] Mosek ApS.  Mosek modeling cookbook, 2021a.  URL https://docs.mosek.com/MOSEKModelingCookbook.pdf.
  * Mosek ApS [2021b] Mosek ApS.  Mosek optimization suite, 2021b.
  * Rossi [2019] P. E. Rossi.  bayesm: Bayesian inference for marketing/micro-econometrics. r package version 3.1-4, 2019.
  * Schmalensee and Thisse [1988] R. Schmalensee and J.-F. Thisse.  Perceptual maps and the optimal location of new products: An integrative essay.  _International Journal of Research in Marketing_ , 5(4):225–249, 1988.
  * Schön [2010] C. Schön.  On the optimal product line selection problem with price discrimination.  _Management Science_ , 56(5):896–902, 2010.
  * Shi et al. [2001] L. Shi, S. Ólafsson, and Q. Chen.  An optimization framework for product design.  _Management Science_ , 47(12):1681–1692, 2001\.
  * Toubia et al. [2003] O. Toubia, D. I. Simester, J. R. Hauser, and E. Dahan.  Fast polyhedral adaptive conjoint estimation.  _Marketing Science_ , 22(3):273–303, 2003.
  * Train [2009] K. E. Train.  _Discrete choice methods with simulation_.  Cambridge university press, 2009.
  * Udell and Boyd [2013] M. Udell and S. Boyd.  Maximizing a sum of sigmoids.  _Optimization and Engineering_ , pages 1–25, 2013.
  * Wang et al. [2009] X. Wang, J. D. Camm, and D. J. Curry.  A branch-and-price approach to the share-of-choice product line design problem.  _Management Science_ , 55(10):1718–1728, 2009\.

##  8 Omitted proofs

###  8.1 Proof of Theorem 3.1 (NP-Hardness)

To prove this result, we will show that the well-known MAX 3SAT problem can be
reduced to the logit-based SOCPD problem. The MAX 3SAT problem is the problem
of setting a collection of binary variables so as to maximize the number of
clauses, which are disjunctions of three literals, that are satisfied. More
precisely, we have $n$ binary variables, $x_{1},\dots,x_{n}$, and a Boolean
formula $c_{1}\wedge c_{2}\wedge\dots c_{K}$, where the symbol $\wedge$
denotes the “and” operator. Each $c_{k}$ is a disjunction involving three
literals where a literal is one of the binary variables or the negation of one
of the binary variables. For example, a clause could be $x_{1}\vee
x_{4}\vee\neg x_{9}$ where $\vee$ denotes the “or” operator and $\neg$ denotes
the negation; in this example, the clause evaluates to 1 if $x_{1}=1$, or
$x_{4}=1$, or $x_{9}=0$, and evaluates to zero if $x_{1}=0$, $x_{4}=0$ and
$x_{9}=1$. The MAX 3SAT problem is to determine how $x_{1},\dots,x_{n}$ should
be set so that the number of the clauses $c_{1},\dots,c_{K}$ that are true is
maximized.

Given an instance of the MAX 3SAT problem, we show how the instance can be
transformed into an instance of the logit-based SOCPD problem.

In the instance of the logit-based SOCPD problem that we will construct, we
let the number of attributes $n$ be equal to the number of binary variables in
the MAX 3SAT instance, and we let the set of permissible attribute vectors
$\mathcal{A}$ simply be equal to $\\{0,1\\}^{n}$. Each attribute of our
product will correspond to one of the binary variables. We let each customer
type $k$ correspond to one of the $K$ literals, and we set $\lambda_{k}=1/K$.
To aid in defining the partworths of each customer type, we will define the
parameters $p_{L}$ and $p_{U}$ as

$\displaystyle p_{L}$ $\displaystyle=\frac{1}{100K},$ (49) $\displaystyle
p_{U}$ $\displaystyle=1-\frac{1}{100K}$ (50)

and we define the utilities $Q_{L}$, $Q_{U}$ as the inverse of the logistic
response function of each of these:

$\displaystyle Q_{L}$
$\displaystyle=\log\left[\frac{1/(100K)}{1-1/(100K)}\right]$ (51)
$\displaystyle Q_{U}$
$\displaystyle=\log\left[\frac{1-1/(100K)}{1/(100K)}\right].$ (52)

Now, for each customer type $k$, let $J_{k}\in\\{0,1,2,3\\}$ denote the number
of negative literals in the corresponding clause $k$ of the MAX 3SAT instance
(i.e., how many literals of the form $\neg x_{i}$ appear in $c_{k}$). We
define the partworths $\beta_{k,1},\dots,\beta_{k,n}$ of customer type $k$ as
follows:

$\displaystyle\beta_{k,i}$ $\displaystyle=\begin{cases}0&\text{if variable
$x_{i}$ does not appear in any literal of clause $k$},\\\ Q_{U}-Q_{L}&\text{if
the literal $x_{i}$ appears in clause $k$},\\\ Q_{L}-Q_{U}&\text{if the
literal $\neg x_{i}$ appears in clause $k$},\\\ \end{cases}$ (53)

for each $i\in\\{1,\dots,n\\}$, and we define the constant part of the utility
$\beta_{k,0}$ as

$\displaystyle\beta_{k,0}$ $\displaystyle=Q_{L}+J_{k}\cdot(Q_{U}-Q_{L}).$ (54)

The rationale for this choice is that the utility of an attribute vector
$\mathbf{a}$ will be equal to $Q_{L}$ if the attributes are set in a way such
that none of the literals of clause $k$ are satisfied, and will be equal to
$Q_{U}$ or higher if the attributes are set so that the clause is satisfied
(i.e., at least one literal is true). For example, if clause $k$ is
$c_{k}=x_{1}\vee x_{4}\vee\neg x_{9}$, then the corresponding utility function
of customer type $k$ has the form:

$\displaystyle u_{k}(\mathbf{a})$
$\displaystyle=Q_{L}+1\cdot(Q_{U}-Q_{L})+(Q_{U}-Q_{L})a_{1}+(Q_{U}-Q_{L})a_{4}+(Q_{L}-Q_{U})a_{9}$
$\displaystyle=Q_{U}+(Q_{U}-Q_{L})a_{1}+(Q_{U}-Q_{L})a_{4}+(Q_{L}-Q_{U})a_{9}.$

If $a_{1}=1$, $a_{4}=0$ and $a_{9}=1$, the clause evaluates to 1 ($=1\vee
0\vee\neg 1$); the utility is

$\displaystyle u_{k}(\mathbf{a})$ $\displaystyle=Q_{U}+(Q_{U}-Q_{L})\cdot
1+(Q_{U}-Q_{L})\cdot 0+(Q_{L}-Q_{U})\cdot 1$ $\displaystyle=Q_{U}.$

If $a_{1}=0$, $a_{4}=0$, $a_{9}=1$, the clause evaluates to 0 ($=0\vee
0\vee\neg 1$), and the utility is

$\displaystyle u_{k}(\mathbf{a})$ $\displaystyle=Q_{U}+(Q_{U}-Q_{L})\cdot
0+(Q_{U}-Q_{L})\cdot 0+(Q_{L}-Q_{U})\cdot 1$ $\displaystyle=Q_{L},$

as expected.

Lastly, before we verify that this reduction is valid, it is helpful to
introduce some additional notation to model the MAX 3SAT. Given a binary
vector $\mathbf{x}\in\\{0,1\\}^{n}$, we let $g_{k}(\mathbf{x})=1$ if clause
$k$ is satisfied and 0 if clause $k$ is not satisfied. The MAX 3SAT problem
can then be written simply as

$\max_{\mathbf{x}\in\\{0,1\\}^{n}}\sum_{k=1}^{K}g_{k}(\mathbf{x}).$

Given an optimal solution $\mathbf{a}$ to the logit-based SOCPD problem, we
claim that the solution $\mathbf{x}$, which is obtained by setting
$x_{i}=a_{i}$ for each $i\in\\{1,\dots,n\\}$, is an optimal solution of the
MAX 3SAT problem. To see why, suppose that this is not the case. In
particular, suppose that $\tilde{\mathbf{x}}$ is a solution to the MAX 3SAT
problem with a higher number of satisfied clauses, that is,

$\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})>\sum_{k=1}^{K}g_{k}(\mathbf{x}).$

Consider the solution $\tilde{\mathbf{a}}$ to the logit-based SOCPD problem,
where we set $\tilde{a}_{i}=\tilde{x}_{i}$ for each $i$. We will now show that
$\tilde{\mathbf{a}}$ achieves an objective that is strictly higher than that
of $\mathbf{a}$, which will give us the desired contradiction.

To show this, we first need to establish some bounds for the share-of-choice
objective in terms of the MAX 3SAT objective. Let $f(u)=e^{u}/(1+e^{u})$
denote the logistic response function. For the solution $\tilde{\mathbf{a}}$,
we have

$\displaystyle\sum_{k=1}^{K}f(u_{k}(\tilde{\mathbf{a}}))\geq
p_{U}\cdot\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}}).$ (55)

This relationship holds because, by construction of the utility functions
$u_{1},\dots,u_{K}$, if literal $k$ is true for the binary vector
$\tilde{\mathbf{x}}$, then $u_{k}(\tilde{\mathbf{a}})\geq Q_{U}$, and
$f(u_{k}(\tilde{\mathbf{a}}))\geq p_{U}$, as the function $f$ is increasing;
thus, $f(u_{k}(\tilde{\mathbf{a}}))\geq p_{U}g_{k}(\tilde{\mathbf{x}})$ is
satisfied. If the literal $k$ is false for the binary vector
$\tilde{\mathbf{x}}$, then $g_{k}(\tilde{\mathbf{x}})=0$, and
$f(u_{k}(\tilde{\mathbf{a}}))\geq p_{U}g_{k}(\tilde{\mathbf{x}})$ is
automatically satisfied, since $f(u)>0$ for all $u\in\mathbb{R}$.

Similarly, for the solution $\mathbf{a}$, we have

$\displaystyle\sum_{k=1}^{K}f(u_{k}(\mathbf{a}))\leq p_{L}\cdot
K+(1-p_{L})\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x}).$ (56)

By similar logic as (55), this relationship holds because if literal $k$ is
true, then $Q_{L}+(1-Q_{L})\cdot g_{k}(\mathbf{x})=Q_{L}+1-Q_{L}=1$, and
$f(u)<1$ for all $u\in\mathbb{R}$. If literal $k$ is false, then
$u_{k}(\mathbf{a})=Q_{L}$ and $f(u_{k}(\mathbf{a}))=p_{L}$, and
$p_{L}+(1-p_{L})\cdot g_{k}(\mathbf{x})=p_{L}$ (since $g_{k}(\mathbf{x})=0$).

To now show that $\tilde{\mathbf{a}}$ outperforms $\mathbf{a}$ in the logit-
based SOCPD problem, we need to show

$\frac{1}{K}\sum_{k=1}^{K}f(u_{k}(\tilde{\mathbf{a}}))>\frac{1}{K}\sum_{k=1}^{K}f(u_{k}(\mathbf{a})),$

which is equivalent to showing

$\sum_{k=1}^{K}f(u_{k}(\tilde{\mathbf{a}}))-\sum_{k=1}^{K}f(u_{k}(\mathbf{a}))>0.$

We have

$\displaystyle\sum_{k=1}^{K}f(u_{k}(\tilde{\mathbf{a}}))-\sum_{k=1}^{K}f(u_{k}(\mathbf{a}))$
$\displaystyle\geq\left[p_{U}\cdot\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})\right]-\left[p_{L}\cdot
K+(1-p_{L})\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})\right]$
$\displaystyle=p_{U}\cdot\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})-p_{L}\cdot
K-(1-p_{L})\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})$
$\displaystyle=p_{U}\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})+p_{U}\cdot[\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})-\sum_{k=1}^{K}g_{k}(\mathbf{x})]-p_{L}K-(1-p_{L})\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})$
$\displaystyle=(p_{U}+p_{L}-1)\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})+p_{U}\cdot[\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})-\sum_{k=1}^{K}g_{k}(\mathbf{x})]-p_{L}K$
$\displaystyle\geq\underbrace{(p_{U}+p_{L}-1)}_{(a)}\cdot\sum_{k=1}^{K}g_{k}(\mathbf{x})+\underbrace{p_{U}-p_{L}K}_{(b)}$
(57)

where the first inequality follows from (55) and (56), and the second
inequality follows by the fact that
$\sum_{k=1}^{K}g_{k}(\tilde{\mathbf{x}})>\sum_{k=1}^{K}g_{k}(\mathbf{x})$, and
that both quantities are integer valued. We now argue that this last quantity
(57) must be positive. To establish this, we need to show that the quantity
denoted by (a) is nonnegative and the quantity denoted by (b) is positive. To
see why (a) must be nonnegative, recall by how we set $p_{L}$ and $p_{U}$ that

$\displaystyle p_{L}+p_{U}-1$
$\displaystyle=\frac{1}{100K}+1-\frac{1}{100K}-1$ $\displaystyle=0.$

To see why (b) must be positive, we have

$\displaystyle p_{U}-p_{L}\cdot K$
$\displaystyle=1-\frac{1}{100K}-\frac{1}{100K}\cdot K$ $\displaystyle\geq
1-\frac{1}{100}-\frac{1}{100}$ $\displaystyle>0,$

where the inequality follows by the fact that $K$ is a positive integer. Thus,
we have
$\sum_{k=1}^{K}f(u_{k}(\tilde{\mathbf{a}}))-\sum_{k=1}^{K}f(u_{k}(\mathbf{a}))>0$,
which establishes that $\tilde{\mathbf{a}}$ achieves a higher objective than
$\mathbf{a}$. Since this contradicts the optimality of $\mathbf{a}$, it must
be the case that $\mathbf{x}$ is an optimal solution of the MAX 3SAT instance.

Since we have reduced the MAX 3SAT problem to the logit-based SOCPD problem
and the MAX 3SAT problem is an NP-Complete problem [Garey and Johnson, 1979],
it follows that the logit-based SOCPD problem is NP-Hard. $\square$

###  8.2 Proof of Theorem 5.2

Let $\mathbf{x}^{*}=\mathbf{x}(\mathbf{a}^{*})$ and
$\hat{\mathbf{x}}=\mathbf{x}(\hat{\mathbf{a}})$. To prove the result we
proceed in three steps.

Step 1: The first step in our proof is to show that if there exist nonnegative
constants $\overline{\alpha}$ and $\underline{\alpha}$ such that $g$ satisfies

$\underline{\alpha}f(\mathbf{x})\leq
g(\mathbf{x})\leq\overline{\alpha}f(\mathbf{x})$ (58)

for all $\mathbf{x}\in\mathcal{X}$, then $\hat{\mathbf{x}}$ satisfies

$f(\hat{\mathbf{x}})\geq(\underline{\alpha}/\overline{\alpha})\cdot
f(\mathbf{x}^{*}).$ (59)

To establish this, we will first bound the quantity
$f(\mathbf{x}^{*})-f(\hat{\mathbf{x}})$. We have

$\displaystyle f(\mathbf{x}^{*})-f(\hat{\mathbf{x}})$
$\displaystyle=[f(\mathbf{x}^{*})-g(\mathbf{x}^{*})]+[g(\mathbf{x}^{*})-g(\hat{\mathbf{x}})]+[g(\hat{\mathbf{x}})-f(\hat{\mathbf{x}})]$
$\displaystyle\leq
f(\mathbf{x}^{*})-g(\mathbf{x}^{*})+g(\hat{\mathbf{x}})-f(\hat{\mathbf{x}})$
$\displaystyle\leq
f(\mathbf{x}^{*})-\underline{\alpha}f(\mathbf{x}^{*})+\overline{\alpha}f(\hat{\mathbf{x}})-f(\hat{\mathbf{x}})$
$\displaystyle=(1-\underline{\alpha})f(\mathbf{x}^{*})-(1-\overline{\alpha})f(\hat{\mathbf{x}})$
$\displaystyle=(1-\overline{\alpha}+\overline{\alpha}-\underline{\alpha})f(\mathbf{x}^{*})-(1-\overline{\alpha})f(\hat{\mathbf{x}})$
$\displaystyle=(1-\overline{\alpha})(f(\mathbf{x}^{*})-f(\hat{\mathbf{x}}))+(\overline{\alpha}-\underline{\alpha})f(\mathbf{x}^{*})$

where the first step follows by algebra; the second step follows since
$g(\mathbf{x}^{*})\leq g(\hat{\mathbf{x}})$, which is true by the definition
of $\hat{\mathbf{x}}$ as the vector of choice probabilities for an optimal
product $\hat{\mathbf{a}}$ for the function $g(\mathbf{x}(\mathbf{a}))$; the
third step follows by (58); and the remaining steps by algebra.

Observe that by re-arranging the inequality

$f(\mathbf{x}^{*})-f(\hat{\mathbf{x}})\leq(1-\overline{\alpha})(f(\mathbf{x}^{*})-f(\hat{\mathbf{x}}))+(\overline{\alpha}-\underline{\alpha})f(\mathbf{x}^{*})$
(60)

we obtain that

$\overline{\alpha}[f(\mathbf{x}^{*})-f(\hat{\mathbf{x}})]\leq(\overline{\alpha}-\underline{\alpha})f(\mathbf{x}^{*}).$
(61)

Since $\overline{\alpha}$ is nonnegative, dividing through by
$\overline{\alpha}$ we obtain

$f(\mathbf{x}^{*})-f(\hat{\mathbf{x}})\leq\frac{(\overline{\alpha}-\underline{\alpha})}{\overline{\alpha}}f(\mathbf{x}^{*}),$
(62)

and re-arranging, we obtain

$\displaystyle f(\hat{\mathbf{x}})$
$\displaystyle\geq\left[1-\frac{\overline{\alpha}-\underline{\alpha}}{\overline{\alpha}}\right]f(\mathbf{x}^{*})$
$\displaystyle=(\underline{\alpha}/\overline{\alpha})\cdot f(\mathbf{x}^{*}),$

which is the desired result.

Step 2: We now establish explicit values for the constants $\overline{\alpha}$
and $\underline{\alpha}$. Recall that by the arithmetic-geometric mean
inequality, $g(\mathbf{x})\leq f(\mathbf{x})$ for all
$\mathbf{x}\in\mathcal{X}$. Therefore, a valid choice of $\overline{\alpha}$
is 1.

For $\underline{\alpha}$, we proceed as follows. Consider the ratio
$f(\mathbf{x})/g(\mathbf{x})$. For any $\mathbf{x}$, we have

$\displaystyle\frac{f(\mathbf{x})}{g(\mathbf{x})}$
$\displaystyle=\frac{\sum_{k=1}^{K}\lambda_{k}x_{k}}{\prod_{k=1}^{K}x_{k}^{\lambda_{k}}}$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\cdot
x_{k}^{1-\lambda_{k}}\cdot\prod_{k^{\prime}\neq
k}x_{k^{\prime}}^{-\lambda_{k^{\prime}}}$
$\displaystyle\leq\sum_{k=1}^{K}\lambda_{k}\cdot
U^{1-\lambda_{k}}\cdot\prod_{k^{\prime}\neq k}L^{-\lambda_{k^{\prime}}}$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\cdot U^{1-\lambda_{k}}\cdot
L^{-\sum_{k^{\prime}\neq k}\lambda_{k^{\prime}}}$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\cdot U^{1-\lambda_{k}}\cdot
L^{\lambda_{k}-1}$
$\displaystyle=\sum_{k=1}^{K}\lambda_{k}\left(\frac{U}{L}\right)^{1-\lambda_{k}},$

where the first step follows by the definitions of $f$ and $g$; the second by
algebra; the third by the fact that the function $h(x)=x^{1-\lambda_{k}}$ is
increasing in $x$ (since $1-\lambda_{k}\geq 0$), and that the function
$\bar{h}(x)=x^{-\lambda_{k^{\prime}}}$ is decreasing in $x$ (since
$-\lambda_{k}\leq 0$); the fourth by algebra; the fifth by recognizing that
$\sum_{k^{\prime}=1}^{K}\lambda_{k}=1$, which implies that
$\lambda_{k}-1=-\sum_{k^{\prime}\neq k}\lambda_{k^{\prime}}$; and the last by
algebra. This implies that a valid choice of $\underline{\alpha}$ is

$\underline{\alpha}=\frac{1}{\sum_{k=1}^{K}\lambda_{k}\left(\frac{U}{L}\right)^{1-\lambda_{k}}}.$
(63)

Step 3: We conclude the proof by combining Steps 1 and 2. In particular, by
using $\overline{\alpha}=1$ and
$\underline{\alpha}=[\sum_{k=1}^{K}\lambda_{k}\left(U/L\right)^{1-\lambda_{k}}]^{-1}$,
we obtain that

$f(\mathbf{x}(\hat{\mathbf{a}}))\geq\frac{1}{\sum_{k=1}^{K}\lambda_{k}\left(\frac{U}{L}\right)^{1-\lambda_{k}}}\cdot
f(\mathbf{x}(\mathbf{a}^{*})),$

as required. $\square$

##  9 Additional details for numerical experiments

###  9.1 Attributes for real data instances in Section 6.2

Tables 5, 6, 7 and 8 display the attributes and attribute levels for the bank,
candidate, immigrant and timbuk2 datasets, respectively.

Attribute | Levels
---|---
Interest Rate | High Fixed Rate, Medium Fixed Rate,
| Low Fixed Rate, Medium Variable Rate
Rewards | 1, 2, 3, 4
Annual Fee | High, Medium, Low
Bank | Bank A, Bank B, Out of State Bank
Rebate | Low, Medium, High
Credit Line | Low, High
Grace Period | Short, Long
Table 5: Attributes for bank dataset.  Attribute | Levels
---|---
Age | 36, 45, 52, 60, 68, 75
Military Service | Did Not serve, Served
Religion | None, Jewish, Catholic, Mainline Protestant,
| Evangelical Protestant, Mormon
College | No BA, Baptist College, Community College,
| State University, Small College,
| Ivy League University
Income | 32K, 54K, 65K, 92K, 210K, 5.1M
Profession | Business Owner, Lawyer, Doctor,
| High School Teacher, Farmer, Car Dealer
Race/Ethnicity | White, Native American, Black,
| Hispanic, Caucasian, Asian American
Gender | Male, Female
Table 6: Attributes for candidate dataset.  Attribute | Levels
---|---
Education | No Formal, 4th Grade, 8th Grade, High School,
| Two-Year College, College Degree, Graduate Degree
Gender | Female, Male
Origin | Germany, France, Mexico, Philippines, Poland,
| India, China, Sudan, Somalia, Iraq
Application Reason | Reunite With Family, Seek Better Job, Escape Persecution
Profession | Janitor, Waiter, Child Care Provider, Gardener, Financial Analyst,
| Construction Worker, Teacher, Computer Programmer,
| Nurse, Research Scientist, Doctor
Job Experience | None, 1-2 Years, 3-5 Years, 5+ Years
Job Plans | Contract With Employer, Interviews With Employer,
| Will Look For Work, No Plans To Look For Work
Prior Trips to US | Never, Once As Tourist, Many Times As Tourist,
| Six Months With Family, Once Without Authorization
Language | Fluent English, Broken English,
| Tried English But Unable, Used Interpreter
Table 7: Attributes for immigrant dataset.  Attribute | Levels
---|---
Price | $70, $75, $80, $85, $90, $95, $100
Size | Normal, Large
Color | Black, Red
Logo | No, Yes
Handle | No, Yes
PDA Holder | No, Yes
Cellphone Holder | No, Yes
Velcro Flap | No, Yes
Protective Boot | No, Yes
Table 8: Attributes for timbuk2 dataset.

###  9.2 Hierarchical Bayesian model specification

For our hierarchical Bayesian model, we assume that each respondent’s
partworth vector $\boldsymbol{\beta}=(\beta_{1},\dots,\beta_{n})$ is drawn as

$\boldsymbol{\beta}\sim
N(\bar{\boldsymbol{\beta}},\mathbf{V}_{\boldsymbol{\beta}}),$

where $N(\boldsymbol{\mu},\boldsymbol{\Sigma})$ denotes a multivariate normal
distribution with mean $\mu$ and covariance matrix $\boldsymbol{\Sigma}$. The
distributions of the mean $\bar{\boldsymbol{\beta}}$ and covariance matrix
$\mathbf{V}_{\boldsymbol{\beta}}$ are then specified as

$\displaystyle\bar{\boldsymbol{\beta}}\sim
N(\mathbf{0},\alpha\mathbf{V}_{\boldsymbol{\beta}}),$
$\displaystyle\mathbf{V}_{\boldsymbol{\beta}}\sim IW(\nu,\mathbf{V}),$

where $IW(\nu,\mathbf{W})$ denotes an inverse Wishart distribution with
degrees of freedom $\nu$ and scale matrix $\mathbf{W}$. This model
specification is implemented in bayesm, using the rhierBinLogit function. We
use bayesm’s defaults for $\nu$, $\mathbf{V}$ and $\alpha$.

###  9.3 Additional constraints for immigrant dataset

As discussed in Section 6.2, we define $\mathcal{A}$ with some additional
constraints, which we describe here:

  * •

If the immigrant’s profession attribute is set to “doctor”, “research
scientist”, “computer programmer” or “financial analyst”, then the immigrant’s
education attribute is set to “college degree” or “graduate degree”.

  * •

If the immigrant’s profession attribute is set to “teacher” or “nurse”, then
the immigrant’s education attribute is set to “high school”, “two-year
college”, “college degree” or “graduate degree”.

  * •

If the immigrant’s application reason attribute is set to “escape
persecution”, then the country of origin attribute is set to Sudan, Somalia or
Iraq.

  * •

Either the immigrant’s application reason attribute is set to “seek better
job” or the immigrant’s job plan attribute is set to “no plans to work”, but
they cannot both be set in this way.

###  9.4 Competitive offerings for Section 6.2

Tables 9, 10, 11 and 12 display the attributes of the competitive offerings
for the bank, candidate, immigrant and timbuk2 datasets, respectively. We note
that for timbuk2, we follow the same competitive offerings used in other
optimization work that has used this dataset [Belloni et al., 2008, Bertsimas
and Mišić, 2017, 2019].

Attribute | Outside | Outside | Outside
---|---|---|---
| Option 1 | Option 2 | Option 3
Interest Rate: High fixed rate |  |  |
Interest Rate: Medium fixed rate |  |  |
Interest Rate: Low fixed rate |  |  |
Interest Rate: Medium variable rate |  |  |
Rewards: 1 |  |  |
Rewards: 2 |  |  |
Rewards: 3 |  |  |
Rewards: 4 |  |  |
Annual Fee: High |  |  |
Annual Fee: Medium |  |  |
Annual Fee: Low |  |  |
Bank: Bank A |  |  |
Bank: Bank B |  |  |
Bank: Out of state bank |  |  |
Rebate: Low |  |  |
Rebate: Medium |  |  |
Rebate: High |  |  |
Credit Line: Low |  |  |
Credit Line: High |  |  |
Grace Period: Short |  |  |
Grace Period: Long |  |  |
Table 9: Outside options for bank dataset problem instances.  Attribute | Outside | Outside | Outside
---|---|---|---
| Option 1 | Option 2 | Option 3
Age: 36 |  |  |
Age: 45 |  |  |
Age: 52 |  |  |
Age: 60 |  |  |
Age: 68 |  |  |
Age: 75 |  |  |
Military Service: Did not serve |  |  |
Military Service: Served |  |  |
Religion: None |  |  |
Religion: Jewish |  |  |
Religion: Catholic |  |  |
Religion: Mainline protestant |  |  |
Religion: Evangelical protestant |  |  |
Religion Mormon |  |  |
College: No BA |  |  |
College: Baptist college |  |  |
College: Community college |  |  |
College: State university |  |  |
College: Small college |  |  |
College: Ivy League university |  |  |
Income: 32K |  |  |
Income: 54K |  |  |
Income: 65K |  |  |
Income: 92K |  |  |
Income: 210K |  |  |
Income 5.1M |  |  |
Profession: Business owner |  |  |
Profession: Lawyer |  |  |
Profession: Doctor |  |  |
Profession: High school teacher |  |  |
Profession: Farmer |  |  |
Profession: Car dealer |  |  |
Race/Ethnicity: White |  |  |
Race/Ethnicity: Native American |  |  |
Race/Ethnicity: Black |  |  |
Race/Ethnicity: Hispanic |  |  |
Race/Ethnicity: Caucasian |  |  |
Race/Ethnicity: Asian American |  |  |
Gender: Male |  |  |
Gender: Female |  |  |
Table 10: Outside options for candidate dataset problem instances.  Attribute | Outside | Outside | Outside
---|---|---|---
| Option 1 | Option 2 | Option 3
Education: No formal |  |  |
Education: 4th grade |  |  |
Education: 8th grade |  |  |
Education: High school |  |  |
Education: Two-year college |  |  |
Education: College degree |  |  |
Education: Graduate degree |  |  |
Gender: Female |  |  |
Gender: Male |  |  |
Origin: Germany |  |  |
Origin: France |  |  |
Origin: Mexico |  |  |
Origin: Philippines |  |  |
Origin: Poland |  |  |
Origin: India |  |  |
Origin: China |  |  |
Origin: Sudan |  |  |
Origin: Somalia |  |  |
Origin: Iraq |  |  |
Application Reason: Reunite with family |  |  |
Application Reason: Seek better job |  |  |
Application Reason: Escape persecution |  |  |
Profession: Janitor |  |  |
Profession: Waiter |  |  |
Profession: Child care provider |  |  |
Profession: Gardener |  |  |
Profession: Financial analyst |  |  |
Profession: Construction worker |  |  |
Profession: Teacher |  |  |
Profession: Computer programmer |  |  |
Profession: Nurse |  |  |
Profession: Research scientist |  |  |
Profession: Doctor |  |  |
Job Experience: None |  |  |
Job Experience: 1-2 years |  |  |
Job Experience: 3-5 years |  |  |
Job Experience: 5+ years |  |  |
Job Plans: Contract with employer |  |  |
Job Plans: Interviews with employer |  |  |
Job Plans: Will look for work |  |  |
Job Plans: No plans to look for work |  |  |
Prior Trips to U.S.: Never |  |  |
Prior Trips to U.S.: Once as tourist |  |  |
Prior Trips to U.S.: Many times as tourist |  |  |
Prior Trips to U.S.: Six months with family |  |  |
Prior Trips to U.S.: Once without authorization |  |  |
Language: Fluent English |  |  |
Language: Broken English |  |  |
Language: Tried English but unable |  |  |
Language: Used interpreter |  |  |
Table 11: Outside options for immigrant dataset problem instances.  Attribute | Outside | Outside | Outside
---|---|---|---
| Option 1 | Option 2 | Option 3
Price: $70 |  |  |
Price: $75 |  |  |
Price: $80 |  |  |
Price: $85 |  |  |
Price: $90 |  |  |
Price: $95 |  |  |
Price: $100 |  |  |
Size: Large |  |  |
Color: Red |  |  |
Logo: Yes |  |  |
Handle: Yes |  |  |
PDA Holder: Yes |  |  |
Cellphone Holder: Yes |  |  |
Mesh Pocket: Yes |  |  |
Velcro Flap: Yes |  |  |
Protective Boot: Yes |  |  |
Table 12: Outside options for timbuk2 dataset problem instances. (For ease of
comparison, only one level of each binary attribute is shown.)