The Design of Feature‐Limited Demonstration Software: Choosing the Right Features to Include

Abstract

Today, software supports many important tasks in a variety of industries. In the specialized nature of these environments, a common problem faced by software vendors is to correctly signal the true value of a software product to the end users. For example, telecommunications equipment manufacturers design complex software for important functions like provisioning new users in the network. These software products automate various functions that would otherwise need to be done manually. In order to enable potential customers—telecommunications providers—to evaluate and recognize the full value of the product, equipment vendors often provide a free, feature‐limited version of the product to the customer. As the specific features included in the feature‐limited version influence whether the full product is purchased or not, it is essential that the features included in the feature‐limited version be selected judiciously. While the importance of identifying the best set of features has been well recognized, there has been little research to date that systematically addresses this fundamental business decision. This study fills this gap in the literature by providing an objective approach to the design of demonstration software. We illustrate the benefits of our approach through a case study involving the design of a feature‐limited demo for a wireless telecommunications equipment manufacturer.

Keywords

software commercialization decision making under uncertainty expected value of perfect information integer programming and Lagrangian relaxation

Introduction

Software products are typically classified as experience goods (Chellappa and Shivendu 2005), as their value is difficult to estimate before actual use (Nelson 1970). Customers account for the greater uncertainty associated with experience goods by lowering their valuation of such goods (Heiman and Muller 1996). Vendors often circumvent this difficulty by letting consumers “use the software for free under certain limitations such as time and functionality” (Ilan 2001). These free evaluation (or demonstration) versions, typically referred to as demos, allow the customer to experience the product directly, and to estimate the values of the features included in the demo more precisely. A well‐designed demo can significantly reduce the uncertainty associated with the product, and thereby facilitate a more informed purchasing decision on the part of the customer.

This study was motivated by a demo design problem drawn from the telecommunications industry. For telecommunications providers, provisioning—the setup and configuration of equipment to activate telecommunications services with customer information—plays a crucial role in improving efficiency and reducing costs. The degree of automation facilitated by provisioning software is a key driver for these gains, and a good understanding of the capabilities of the features in the software helps discern the extent of benefits that can be realized. The vendors of provisioning software—telecommunications equipment manufacturers—usually signal the value of their product by providing free, feature‐limited versions of their software to potential customers.

The full provisioning software product typically has hundreds of features that can be invoked by the operator (or end user) as needed for the task being performed (e.g., adding new neighbors or auditing the network). The features included in the demo version are available for free, while the remaining features can be accessed only after obtaining a license. The demo helps operators estimate the functionality and the economic impact of the full product by allowing them to try out the features in the demo.

While our work is motivated by a problem from the telecommunications industry, it is important to recognize that this is not an isolated context. Customized, feature‐limited versions of industrial software are popular in other domains, with the enterprise software segment being of particular relevance. They are particularly prevalent in industries that require close interaction between customers and vendors (such as the telecommunications and enterprise systems industries), and vendors in these contexts typically have a good idea of their customers' cost structure. While this is convenient, the approach presented in the study remains applicable even when this is not the case.

Companies like Oracle, Salesforce.com, and SAP use feature‐limited versions of their enterprise software to entice customers into buying the full product. Oracle provides a restricted‐use‐license containing many free features of its software products, with the PeopleSoft Interaction Hub being one example. While the restricted‐use‐license allows free access to some of its features, customers need to buy a full‐use‐license to use it as a full‐feature enterprise portal (Oracle 2012). Feature‐limited versions of software are also prevalent in the software‐as‐a‐service (SaaS) industry. For example, Salesforce.com provides its CRM enterprise software in two feature‐limited editions, Professional and Enterprise. The Enterprise edition contains all the features of the Professional edition, along with some additional features at a higher subscription rate. The customer can access even more features through the Unlimited edition¹ by paying an even higher subscription rate. Along the same lines, SAP provides their Product Stewardship Network software in tiers—a free feature‐limited basic edition and various licensed editions.²

In general, a demo could be feature limited or time limited. The appropriate limitation to impose often depends on the type of software product in question. As time‐limited demos provide the customer with the complete software for a limited period of time, they provide customers the opportunity to estimate the value of every feature in the product. On the other hand, customers may be reluctant to invest the significant amount of time that might be needed to do a comprehensive evaluation of a large software product that they will not have after the evaluation period has expired. This is particularly true in the context of enterprise level software, where a customized feature‐limited demo could substantially reduce the time customers need to spend evaluating its potential benefits. Unlike the consumer sector where time‐limited demos are common (e.g., WinZip), feature‐limited demos are more appropriate for large customized software products that are to be deployed on an enterprise scale. Feature‐limited demos eliminate the possibility of a comprehensive evaluation. However, if the features included in the demo are not too many and have been arrived at judiciously, the customer might be more willing to evaluate the product as they will be able to estimate its value without committing a significant amount of time.

Conceptually, a demo provides a potential customer with a signal of the product's utility. This signal, which is the expected value of the full version over the demo, should influence a customer's willingness to purchase the software product, and therefore, it is crucial that the signal be chosen such that it maximizes the customer's willingness to pay. The key criterion that should determine the signal, and consequently drive the design of feature‐limited demos, is elucidated in a posting on the discussion board The Business of Software,³ which states that, by limiting the features, “you are selling the difference between the trial version and the full version, and you make that difference bigger by disabling some features.” Froberg ( 2015) of freemium.org suggests that the value of features should impact the design—that is, the vendor should “look at what value is created from the customer's perspective with your free and premium products respectively.” We recognize that the vendor has to incorporate the customer's evaluation criterion into their optimization model, and explicitly incorporate this idea into the demo design process.

At a high level, there are some similarities between the demo design problem and the strategy of creating a minimum viable product (MVP) to avoid developing features that customers do not want. However, the problems are fundamentally quite different. In the context of designing a demo, the intent is to reduce the customer's uncertainty and signal to them that the full product has value. In the context of a MVP, the point is to build a minimum set of features that is enough to deploy the product. Once the MVP is deployed, feedback from early adopters is used to decide the direction future versions of the product will take. While the full product in the demo design context is a well established entity with a known set of features that have relatively predictable impacts on a customer's tasks, the full product is a nebulous and evolving object in the case of MVP.

This study makes various contributions, the most important of which are a formal representation of the design of feature‐limited demo as an NP‐complete optimization problem, and fast, effective procedures to solve it. While prior research has investigated strategies for providing demos (e.g., Cheng et al. 2015, Niculescu and Wu 2014), very little research exists that provides a scientific basis for the design of feature‐limited demos.

We first present the customer's problem of estimating the incremental benefit of purchasing the complete software product, given a feature‐limited demo. The benefits could be through productivity gains resulting from the increased efficiency with which a customer can carry out the tasks they need to perform, or from a re‐engineering effect which enables the customer to execute tasks that were not being performed before. We formulate the customer's problem as an integer program, and show that it is easy to solve. Next, we present the vendor's problem of designing the best feature‐limited demo to provide to a specific customer, as a nonlinear integer program. We show that the vendor's problem is NP‐complete in the strong sense, and that state‐of‐the‐art solvers like BARON and CPLEX have difficulty solving realistic versions of the problem. We solve the problem effectively using a fast converging “scenario aggregation” (SA) approach based on Lagrangian decomposition (Guignard and Kim 1987). As solving the problem in situations where the parameter variability is low is observed to be time‐consuming, we develop a continuous version of the problem that exploits the fact that the parameters have low variability. We incorporate the results from the continuous model into an “augmented heuristic” that solves the problem very quickly.

The problems faced by most telecommunications and enterprise systems companies tend to be quite large in terms of the number of features and the number of tasks the features can affect. We have used an example from the telecommunications industry to illustrate that addressing the problem systematically can make a difference, even for small problems. We also conduct several experiments on large versions of the problem to show that the approaches introduced in the study can scale well to solve large problem instances.

As this work is motivated by a problem from the telecommunications industry, we have focused on the problem from the perspective of designing a demo for customized industrial software. This customization can be viewed as being done either for a single customer, or a segment of customers who can be viewed as homogeneous for the purposes of this study, that is, all customers in the segment have similar needs and value their features similarly. However, we also show how the formulation can easily be generalized to fit a multi‐segment context, where a single demo needs to be created across all customer segments. We illustrate how this provides the vendor with a process to estimate the expected benefit of perfectly identifying the segment to which a customer belongs.

The rest of this study is organized as follows. We begin with a brief review of related work in section 2. The customer's problem is introduced in section 3, and the vendor's problem (which incorporates the customer's problem in it) is presented in section 4. A real example of the demo design problem from the telecommunications industry is discussed in section 5. Section 6 shows that problems of industrial scale cannot easily be handled by commercial solvers such as CPLEX and BARON. A heuristic leveraging Lagrangian decomposition is introduced in section 7; this is refined using results from a continuous adaptation of the vendor's problem in section 8 to address the case where the problem parameters have very low variability. A generalized version of the model that can create a single demo across multiple segments of customers is presented in section 9, and section 10 concludes the study.

Literature Review

Consumers make decisions on products to purchase based on the value they expect to gain when using the product (Kreps 1990). In general, products can be classified as experience goods or search goods, where experience goods are distinguished by the consumer's inability to determine the quality of the product attributes before purchase (Nelson 1970). Heiman and Muller ( 1996) note that consumers incorporate this uncertainty into their decision making by lowering their valuation of such goods. They go on to point out that, “in the case of high‐quality products, both consumer and producer have an incentive to reduce the uncertainty about the product's performance” (Heiman and Muller 1996).

In the context of software products, the consumer can utilize descriptions of the product and its features to obtain an estimate of the value of the product. However, as the estimation of these values is inherently difficult, the estimate so obtained may not be a very accurate reflector of actual product value. It is in this context that software vendors often resort to providing an evaluation (or demo) version of the product. If a carefully designed demo is made available, it helps the consumer estimate the value of the full software product more accurately (Li and Gery 2000). Buying a full‐feature version based on a free demo is similar to purchasing an upgraded version based on a basic version. Several factors, such as the obsolescence of an existing product (Mehra et al. 2014) or the cost of upgrading (Bala and Carr 2009), affect a customer's decision to upgrade. Given a demo, the customer can estimate the value of the full software and use that as the basis for making a purchase decision. While there is consensus in the literature on the positive value of demos, there is little research to assist with the configuration and design of demo software. The research that does exist focuses primarily on various aspects of quality uncertainty, and the role of demos in mitigating this uncertainty.

Feature‐limited software can be viewed through the lens of versioning, where a product is vertically differentiated into free and premium versions. Versioning of products using free trials and samples to increase the customer's willingness to pay for the full version has been shown to be an effective strategy for promotions (Lewis and Sappington 1994, Wang and Zhang 2009). Wei and Nault ( 2014) consider the monopolist strategy of selling feature‐limited information goods to customers who differ in individual tastes for quality, and find that any horizontal differentiation favors versioning. In the context of learning by word‐of‐mouth, Niculescu and Wu ( 2014) find that feature‐limited software is optimal when the prior on features not in the demo is either relatively low or high, but not in between. Li and Gery ( 2000) suggest that demos allow customers to make a more informed estimation of a product's true value, thereby reducing the uncertainty faced by the customer. Roberts and Urban ( 1988) argue that by reducing uncertainty, demos help software vendors increase the consumer's perceived value of the product.

While the feature‐limited business model has been around since the 1980s, there has been renewed interest in recent years due to the fact that a large number of internet start‐ups and smartphone app developers have found the model to be very attractive. Seufert ( 2013) shows how a data‐driven approach is best implemented in the development of feature‐limited software. Using case studies of successful feature limited demos, Semenzin et al. ( 2012) suggest that it might be better to make the core features of the software available for free. Lee et al. ( 2013) consider consumer usage, upgrades and referrals to find the value of the demo relative to the premium product. Similarly, freemium.org has a model that uses conversion rate, number of free users, marginal cost per free user and contribution per premium product to decide the optimum mix of free and charged features. However, these approaches are less appropriate in the context of designing customized industrial software, where the customers are few but large, and where vendors usually has a deeper understanding of the tasks being performed by end users.

The Customer's Problem

Given a feature‐limited demo, the customer has to estimate the incremental benefit the complete software product will provide over the demo. This incremental benefit includes the benefit from new tasks that the customer can perform (re‐engineering effect) and from the ability to perform existing tasks more easily (productivity effect).

Terminology and Related Notation

We consider customers who routinely perform a set of tasks. The relevant set of tasks

T

consists of all the tasks that can be performed profitably with the full version of the software. The profit from performing task j without the software is

π_{j}

. We assume that it is not difficult for the customers to estimate

π_{j}

, as the revenue and cost associated with each task j can be estimated quite precisely. If the customer can profitably perform task j without the software,

π_{j}

is positive. On the other hand,

π_{j}

will be negative for those tasks for which the costs exceed the benefits (without the software). The software product increases the efficiency of tasks currently being done (i.e., tasks with

π_{j} > 0

), and potentially enables tasks that are currently too expensive (i.e., tasks with

π_{j} < 0

) to be done profitably. The product is composed of a set of features

F

, that contribute to improving the net benefit of performing the tasks.

The set of features

D \subseteq F

included in the evaluation software by the vendor comprises the demo. Given a demo

D

, the customer experiences the features included in it, and determines the benefit

β_{i j}

from feature

i \in D

to task

j \in T

for each feature included in the demo.

β_{i j}

is the gain in productivity and efficiency over the cost of effort and time to learn the feature. The software provides the customer the ability to perform tasks more efficiently than before, by reducing the cost associated with doing them. This reduction in cost is captured by the

β_{i j}

. Given that the customers can experience these features for as long as needed, it is reasonable to assume that they will arrive at relatively precise values for the

β_{i j}

. However, the

β_{i j}

values cannot be estimated very precisely for features not included in the demo. Consequently, the customer estimates the

β_{i j}

values as

b_{i j}

for all features

i \notin D

, based on the help files and user guides that accompany the software. Existing research suggests that there is reason to expect that

b_{i j}

will be consistently lower than the corresponding

β_{i j}

(Heiman and Muller 1996, Shapiro 1983).

The problem facing the customer is that of identifying the tasks to perform had the complete software product been available, and of estimating the total benefit from performing these tasks. The original total profit, when no software or demo is available, is

Π_{\emptyset} = \sum_{{j \in T | π_{j} > 0}} π_{j}

, while the total profit with the complete software product is denoted

Π_{F}

. A demo allows the customer to better estimate

Π_{F}

using the features included in it. The value of

Π_{F}

estimated by the customer when given a demo

D

is denoted

{\tilde{Π}}_{F}^{D}

, while the value of

Π_{F}

estimated in the absence of a demo is denoted

{\tilde{Π}}_{F}^{\emptyset}

. Note that

{\tilde{Π}}_{F}^{D}

is estimated using the

β_{i j}

values for all features

i \in D

and the

b_{i j}

values for all features

i \notin D

, while

{\tilde{Π}}_{F}^{\emptyset}

is obtained using the estimates

b_{i j}

for all features

i \in F

. As customers tend to underestimate their evaluations in the face of uncertainty, one would expect

{\tilde{Π}}_{F}^{D} \geq {\tilde{Π}}_{F}^{\emptyset}

in general. The demo itself might have intrinsic value, and the profit with just the demo

D

is denoted as

Π_{D}

. If the demo has intrinsic value,

Π_{D}

will be greater than

Π_{\emptyset}

The value of the software product to the customer,

Υ_{F}

, is the incremental profit resulting from the use of the software product, that is,

Υ_{F} = (Π_{F} - Π_{\emptyset})

. The estimated value of the product given a demo

D

{\tilde{Υ}}_{F}^{D} = ({\tilde{Π}}_{F}^{D} - Π_{\emptyset})

. In the absence of a demo, the estimated value of the product is

{\tilde{Υ}}_{F}^{\emptyset} = ({\tilde{Π}}_{F}^{\emptyset} - Π_{\emptyset})

. The intrinsic value of the demo

Υ_{D} = (Π_{D} - Π_{\emptyset})

is the increase in profit as a result of using only the features in

D

; this comprises the re‐engineering benefit from any new tasks enabled by the demo, and the productivity benefit from the increased efficiency in performing currently executed tasks.

The signal Ψ is defined as the gap between the estimated product value and the value of the demo, that is,

Ψ = ({\tilde{Υ}}_{F}^{D} - Υ_{D})

when a demo

D

is provided, and

Ψ = {\tilde{Υ}}_{F}^{\emptyset}

when there is no demo. Note that given a demo

D

, Ψ can also be expressed as

({\tilde{Π}}_{F}^{D} - Π_{D})

. Table 1 summarizes the notation used in this study for easy reference.

Table 1

Relevant Notation

$T$	Set of relevant tasks	${\tilde{Π}}_{F}^{D}$	Customer's estimate of $Π_{F}$ , given demo $D$
$F$	Set of software features	${\tilde{Π}}_{F}^{\emptyset}$	Customer's estimate of $Π_{F}$ , without demo
$π_{j}$	Pre‐software profit from task j	$Π_{D}$	Profit with demo $D$
$D$	Demo ( $\subseteq F$ )	$Υ_{F}$	Incremental profit with software = $(Π_{F} - Π_{\emptyset})$
$β_{i j}$	Benefit from feature i to task j	${\tilde{Υ}}_{F}^{D}$	Estimate of $Υ_{F}$ , given demo $D = ({\tilde{Π}}_{F}^{D} - Π_{\emptyset})$
$b_{i j}$	Customer's estimate of $β_{i j}$	${\tilde{Υ}}_{F}^{\emptyset}$	Estimate of $Υ_{F}$ , without demo = $({\tilde{Π}}_{F}^{\emptyset} - Π_{\emptyset})$
$Π_{\emptyset}$	Total pre‐software profit	$Υ_{D}$	Intrinsic value of demo $D = (Π_{D} - Π_{\emptyset})$
$Π_{F}$	Profit with software	Ψ	The signal $\{\begin{matrix} = ({\tilde{Υ}}_{F}^{D} - Υ_{D}) with demo D \\ = {\tilde{Υ}}_{F}^{\emptyset} without demo \end{matrix}$

An Illustrative Example

Consider the simplified network monitoring software in Figure 1. It has six features, represented by the nodes in the lower part of the figure; that is,

F = {f_{1}, f_{2}, f_{3}, f_{4}, f_{5}, f_{6}}

. Features are viewed from a logical (rather than an implementation) perspective, and we assume that the contribution of any given feature to a task is not dependent on the contributions of the other features. This software allows the customer to potentially perform the two tasks represented at the top of the figure; that is, the task set is

T = {t_{1}, t_{2}}

. Each task has a profit

π_{j}

, as noted in the figure. When the profit from a task is positive (as is the case for task

t_{1}

), that task will be performed even without the software. Any contributions of the software to tasks with positive

π_{j}

will be through productivity impacts. If

π_{j}

is negative (as is the case for task

t_{2}

), it is not cost‐effective for the customer to perform the task without the software. The contribution of the software to tasks with negative

π_{j}

will potentially allow for new tasks to be performed, which is a re‐engineering impact.

Figure 1

Simplified Example

Feature i and task j are connected by an edge if the availability of feature i will improve the profit from task i (by

β_{i j}

). The customer can experience all features included in the demo, and arrive at precise estimates of the

β_{i j}

associated with each. If a feature i is not included in the demo, the customer will have to use the product description to estimate (as

b_{i j}

) its contribution to each task. The values of

β_{i j}

and

b_{i j}

for relevant feature‐task pairs are indicated on the links in the figure. Note that a task could benefit even when a subset of the features relevant to that task is included in the demo.

Prior to the software being considered for evaluation,

π_{1}

was 11 (positive) and

π_{2}

was −17 (negative). Therefore, task

t_{1}

was being performed, while task

t_{2}

was not; the total profit

Π_{\emptyset}

was simply that from task

t_{1}

, that is, 11. Let features

f_{3}

and

f_{4}

(i.e., Traffic Analyzer and Configuration Interface) comprise the demo provided to the customer, that is,

D = {f_{3}, f_{4}}

f_{3}

contributes only to

t_{1}

, while

f_{4}

contributes only toward

t_{2}

. Consequently, the customer will experience the demo and identify the correct values of

β_{31}

and

β_{42}

. For all other feature‐task pairs, the customer estimates the

β_{i j}

b_{i j}

Incorporating Uncertainty: The Scenario Approach

Recall that the customer approximates the

β_{i j}

values associated with the features not in the demo as

b_{i j}

. Based on existing literature (e.g., Heiman and Muller 1996, Shapiro 1983), it is reasonable to assume that

b_{i j}

will be lower than

β_{i j}

(though the models developed in this study do not require this to be the case). The experience‐good nature of software products implies that there is uncertainty in estimating the

β_{i j}

values. To obtain these estimates, customers can refer to user manuals, obtain expert opinions, or contact the vendor for more information. As far as the customer is concerned, we assume that

b_{i j}

is a random draw from

[0, β_{i j}]

, to account for underestimation.

The customer's problem can be viewed as a multi‐period planning problem under uncertainty. The decision to purchase the software has to be made in the first period in the presence of uncertainty. If the product is purchased, the estimated incremental profit is

Ψ = ({\tilde{Υ}}_{F}^{D} - Υ_{D})

as explained earlier. On the other hand, if the product is not purchased, the associated profit is the original profit plus the intrinsic value of the demo.

Given the inherent nonlinearity associated with integer programming, we cannot replace a random quantity (

β_{i j}

) by its expected value. For instance, if expected values we used for

β_{i j}

in the example in section , the customer incorrectly infer that no new tasks will be performed with the new software. This erroneous conclusion hurts both the customer and the vendor. To estimate the value of the full product, customers must first arrive at an estimate of the set of tasks that will be performed with the full set of features. This set of tasks is identified for the sole purpose of arriving at an estimate of product value—if the product is purchased, all

β_{i j}

values will be precisely estimated, and the customer will be able to identify the actual set of tasks that can be performed effectively with the software. The customer's decision problem therefore, is a stochastic program with complete recourse.

One approach to solving stochastic programs is to approximate the uncertainty in the parameters through a set of scenarios with associated probabilities. A scenario can be interpreted as a state of nature, or equivalently, as one possible outcome of the uncertain parameters. In most cases, incorporating all possible scenarios into the decision making process is not practical as the number of scenarios is too large. Consequently, the deterministic equivalent ⁴ is usually approximated by a model involving fewer scenarios. If the number of scenarios used is large enough, the approximation obtained will be of good quality.

In the context of the customer's problem, each scenario s is represented by a random draw

b_{i j}^{s}

from

[0, β_{i j}]

for each

β_{i j}

that needs to be estimated. The customer needs to estimate the likely value of the complete product, given that the

β_{i j}

values are known for each feature i included in the demo

D

, and have been estimated as

b_{i j}^{s}

for each feature not included in the demo. The estimated benefit from doing a specific task j comprises (i) the original profit

π_{j}

, (ii) the improvements

β_{i j}

guaranteed by all features

i \in D

included in the demo, and (iii) the estimated improvements

b_{i j}^{s}

from the features

i \in F \ D

. Given a set

S

of scenarios and probabilities

p^{s}

associated with each scenario

s \in S

, formulation (CS) will provide the incremental value of the product,

{\tilde{Υ}}_{F}^{D} = ({\tilde{Π}}_{F}^{D} - Π_{\emptyset})

, after defining the task selection variable

y_{j}^{s}

, which is 1 if task j is selected for execution under scenario s, and 0 otherwise.

\begin{matrix} (C S) Max {\tilde{Υ}}_{F}^{D} = \sum_{s \in S} p^{s} (\sum_{j \in T} (π_{j} + \sum_{i \in D} β_{i j} + \sum_{i \in F \ D} b_{i j}^{s}) y_{j}^{s} \\ - \sum_{{j \in T | π_{j} > 0}} π_{j}) \end{matrix}

s.t. y_{j}^{s} \in {0, 1} \forall j \in T; \forall s \in S

The objective function coefficient of variable

y_{j}^{s}

comprises (i) the value of performing task j without the software

(π_{j})

, (ii) the contribution to task j of all features

i \in D

included in the demo

(\sum_{i \in D} β_{i j})

, and (iii) the estimated contribution to task j under scenario s of all features

i \in F \ D

that have been left out of the demo

(\sum_{i \in F \ D} b_{i j}^{s})

. The constant term

\sum_{{j \in T | π_{j} > 0}} π_{j}

that is subtracted from the objective function is

Π_{\emptyset}

, the benefit that was being derived from the tasks before the demo became available. It is easy to see that the optimal solution to (CS) will comprise those tasks that will have a positive net benefit after considering all three components of the objective function coefficient, that is, the optimal solution is

y_{j}^{s} = 1 \forall j ∋ (π_{j} + \sum_{i \in D} β_{i j} + \sum_{i \in F \ D} b_{i j}^{s}) > 0

, and

y_{j}^{s} = 0

for all other tasks. Effectively, the estimated net contribution from a newly enabled task j is

(π_{j} + \sum_{i \in D} β_{i j} + \sum_{i \in F \ D} b_{i j}^{s})

, while that from a task that is currently being done is

(\sum_{i \in D} β_{i j} + \sum_{i \in F \ D} b_{i j}^{s})

—for such tasks, the benefit of

π_{j}

was already being generated, and cannot be attributed to the software. The tasks selected by (CS) are those that the customer would expect to perform once the complete version of the software is available. Note that the tasks identified to be performed do not have to be identical across the scenarios, as the intent is to obtain a good estimate of the signal, and not to precisely pinpoint the tasks to be performed with the software. This implies that the decision variables can be defined distinctly for each scenario, and consequently, formulation (CS) decomposes into disconnected subproblems

(C S^{s})

for each scenario s.

\begin{matrix} (C S^{s}) Max {\tilde{Υ}}_{F}^{D s} = \sum_{j \in T} (π_{j} + \sum_{i \in D} β_{i j} + \sum_{i \in F \ D} b_{i j}^{s}) y_{j}^{s} \\ - \sum_{{j \in T | π_{j} > 0}} π_{j} \end{matrix}

s.t. y_{j}^{s} \in {0, 1} \forall j \in T; \forall s \in S

Based on our initial motivation of the telecommunication provisioning problem, we have considered that the customer can perform each task independent of the others. If a task

j_{1}

is dependent on another task

j_{2}

, that is, if task

j_{1}

can only be performed when task

j_{2}

is complete, we need to add a constraint

y_{j_{2}}^{s} \geq y_{j_{1}}^{s}

(C S^{s})

. Given the parameters for a scenario, the customer's problem remains easy—all the customer needs to do is solve

(C S^{s})

to obtain the optimal objective function value

{\tilde{Υ}}_{F}^{D s}

associated with scenario s. Therefore, given the set of enumerated scenarios

S

, and the probabilities

p^{s}

associated with each scenario

s \in S

, the customer can estimate the value of the product as

{\tilde{Υ}}_{F}^{D} = \sum_{s \in S} p^{s} {\tilde{Υ}}_{F}^{D s}

. The probabilities

p^{s}

can be obtained from any distribution that is appropriate in a given context; if the scenarios is equally likely,

p^{s}

is simply

\frac{1}{| S |}

As the demo being considered is a feature‐limited one, the customer has to identify the intrinsic value of the demo and subtract this value from the optimal objective function value of (CS) in order to identify the real benefit from buying the software. The intrinsic value of the demo

Υ_{D}

can be obtained by solving a variant of formulation (CS), where the third term is removed from the objective function coefficient of the

y_{j}^{s}

variables. Now there is no need to consider the scenarios as there is no uncertainty involved.

The Vendor's Problem

The vendor has to design the best feature‐limited demo possible. The best feature‐limited demo will comprise those features that will maximize the value of the signal detected by the customer. The process of identifying the features to include in the best feature‐limited demo has to incorporate in it the customer's evaluation approach. In the previous section, we established that the best way in which the customer can identify the signal is through the scenario approach. The vendor needs to include this process into the design process and therefore, the customer's problem and the vendor's problem are intricately linked together. Identifying the best signal is in the interest of the customer, as is providing a demo that will result in the best signal in the interest of the vendor. To this extent, the objectives of both parties are aligned, and there is no reason for the customer to intentionally use an inferior approach to estimate the signal.

The Discrete Model with Uncertainty: The Scenario Approach

The discrete version of the vendor's problem can be formulated as (VS), after defining the following additional variables—(i)

x_{i}

, which is 1 if feature i is included in the demo, and 0 otherwise, and (ii)

ρ_{j}

, which is the actual benefit to the customer from task j, when only the features included in the demo are considered. For tasks with

(π_{j} + \sum_{i \in F} β_{i j} x_{i}) < 0

, the features included in the demo are not enough to make the task profitable, and therefore, they result in no value being given away. However, when

(π_{j} + \sum_{i \in F} β_{i j} x_{i}) > 0

for any task, the vendor is giving some value of the associated features away for free. To the extent that there may be tasks with

(π_{j} + \sum_{i \in F} β_{i j} x_{i}) < 0

involving some of the same features however, not all of the value associated with the features are being given away. It is also possible for a demo to contain many features, but have no intrinsic value to the customer. The variables

ρ_{j}

capture the value given away toward task j through features included in the demo. When added up over all tasks

j \in T

, the

ρ_{j}

variables give the total profit to the customer from using the demo.

\begin{matrix} (V S) Max Ψ^{V S} = \sum_{s \in S} p^{s} (\sum_{j \in T} (π_{j} + \sum_{i \in F} β_{i j} x_{i} + \sum_{i \in F} b_{i j}^{s} (1 - x_{i})) y_{j}^{s}) - \sum_{j \in T} ρ_{j} \end{matrix}

s.t. ρ_{j} \geq (π_{j} + \sum_{i \in F} β_{i j} x_{i}) \forall j \in T

ρ_{j} \geq 0 \forall j \in T

x_{i} \in {0, 1} \forall i \in F

y_{j}^{s} \in {0, 1} \forall j \in T; \forall s \in S

The objective function maximizes the estimated strength of the signal by taking the expectation over the signals from each of the scenarios. The estimate of the signal obtained by the vendor need not be identical to that obtained by the customer as the scenarios generated by the two parties are likely to be different, and the vendor is constrained in the number of scenarios that can be used when solving formulation (VS). As with the customer's problem, the objective function coefficient of

y_{j}^{s}

has three components—

π_{j}

, the value of performing task j without the software,

\sum_{i \in F} β_{i j} x_{i}

, the contribution to task j of all features

i \in D

included in the demo, and

\sum_{i \in F} b_{i j}^{s} (1 - x_{i})

, the estimated contribution to task j of all features

i \in F \ D

that have been left out of the demo. Constraints 6 and 7 together ensure that all tasks that provide a net benefit with the demo count toward the profit from the demo, and that no task with a negative net benefit is performed. As the customer has the option not to perform task j, the intrinsic value of the demo cannot be negative. This is captured by constraint 7, the non‐negativity constraint on

ρ_{j}

. If the demo has intrinsic (positive) value—that is, if

(π_{j} + \sum_{i \in D} β_{i}) > 0

—

ρ_{j}

will be set to that value, and subtracted from the objective function. The value of the features included has to be greater than

(- π_{j})

before the customer can start benefiting from performing task j. As with the customer's problem, the probability

p^{s}

\frac{1}{| S |}

if the scenarios are equally likely. Depending on the number of scenarios used and the specific values of the

b_{i j}^{s}

that are realized in each scenario, the value of the signal obtained can vary. As the number of scenarios increases however, this variation can be expected to decrease.

The telecommunication problem that motivated this study does not have any dependencies among the features, and we have not incorporated such dependencies into the vendor's problem. However, they can be easily introduced by adding constraints of the form

x_{i_{1}}^{s} \geq x_{i_{2}}^{s}

to (VS), that imply that feature

i_{2}

can contribute only when feature

i_{1}

is also contributing. Depending on the context, it is possible that there could be synergies among features. For example, given two features

i_{1}

and

i_{2}

that contribute to a task j, the benefit to task j from these features need not simply be

(β_{i_{1} j} + β_{i_{2} j})

—there could be a synergistic effect

β_{i_{1} i_{2} j}

that makes the benefit

(β_{i_{1} j} + β_{i_{2} j} + β_{i_{1} i_{2} j})

. If such interactions (whether just pairwise, or at higher orders) exist, the problem to be solved will be significantly more complicated. This is of relevance to the design of the software itself—while the problem context could also be relevant, it goes without saying that software design plays a key role in reducing the effect of such interactions. In the telecommunications context where our problem is from, such synergies were not a concern.

As we are considering customized software where the vendor has a good understanding of the customer's cost structure, we have assumed that it is possible for the vendor to obtain reasonable estimates of a customer's

π_{j}

, and

β_{i j}

parameters. While this may not be possible precisely, it will be possible for the vendor to get a good idea by consulting domain experts, sales managers and others who know the customer well to get good estimates of these parameters. We are only assuming that the vendor has distributional information concerning the value customers have for tasks and for the amount a feature contributes to a particular task. The exact values of these parameters are not known to the vendor. Even if there is some uncertainty in these estimates, the models developed in this study can accommodate it with very minimal modification. Once the distribution of

β_{i j}

is known the vendor can use the customer's scenario selection criteria to estimate the

b_{i j}^{s}

. Assuming that the customer consistently underestimates, the vendor will estimate the

b_{i j}^{s}

from the range

[0, β_{i j}]

. We have assumed that the vendor knows this information with certainty for ease of illustration. In section 5 we discuss the estimation of

π_{j}

and

β_{i j}

in a real‐world case study.

Problem (VS) is a nonlinear integer program, with the product of the

x_{i}

and

y_{j}^{s}

variables introducing the nonlinearity. It can be linearized by introducing variables

z_{i j}^{s}

, which are defined to be 1 when both

x_{i}

and

y_{j}^{s}

are 1, and 0 otherwise—that is,

z_{i j}^{s}

is 1 if (i) feature i is included in the demo, and (ii) task j is selected for execution under scenario s, and 0 otherwise. The linearized version of (VS) is

(V S_{L})

below.

\begin{matrix} (V S_{L}) Max \sum_{s \in S} p^{s} [\sum_{j \in T} ((π_{j} + \sum_{i \in F} b_{i j}^{s}) y_{j}^{s} + \sum_{i \in F} (β_{i j} - b_{i j}^{s}) z_{i j}^{s})] - \sum_{j \in T} ρ_{j} \end{matrix}

s.t. z_{i j}^{s} \leq x_{i} \forall s \in S; \forall i j \in E

z_{i j}^{s} \leq y_{j}^{s} \forall s \in S; \forall i j \in E

z_{i j}^{s} \geq (x_{i} + y_{j}^{s} - 1) \forall s \in S; \forall i j \in E

ρ_{j} \geq (π_{j} + \sum_{i \in F} β_{i j} x_{i}) \forall j \in T

ρ_{j} \geq 0 \forall j \in T

x_{i} \in {0, 1} \forall i \in F

y_{j}^{s} \in {0, 1} \forall j \in T; \forall s \in S

The objective function can be interpreted as follows. For any task j that is selected to be performed in scenario s, the associated benefit is at least equal to

(π_{j} + \sum_{i \in F} b_{i j}^{s})

, which is the total of the original profit and the estimated

b_{i j}^{s}

values. If any feature i that contributes positively to task j is included in the demo, this will result in an extra benefit of

(β_{i j} - b_{i j}^{s})

to task j in scenario s; the total benefit to task j from all features included in the demo is accounted for by the term

\sum_{i \in F} (β_{i j} - b_{i j}^{s}) z_{i j}^{s}

. Note that constraint 13 can be eliminated whenever

β_{i j} \geq b_{i j}^{s}

, and constraints 11 and 12 can be eliminated whenever

β_{i j} < b_{i j}^{s}

. As the customer will underestimate the parameter values in general, the former situation is more likely to occur in reality than the latter.

The feature inclusion decisions

x_{i}

connect the scenarios together, and consequently,

(V S_{L})

cannot be decomposed into easier subproblems. The vendor's problem is NP‐complete in the strong sense as shown in Proposition 1 (proof in Appendix A), and the nonlinearity introduced by the product of the

x_{i}

and

y_{j}^{s}

variables only adds to the difficulty.

Proposition 1

The vendor's problem is NP‐complete in the strong sense.

As the vendor's problem is NP‐complete, the number of scenarios the vendor chooses to use will play a key role in its solvability from a practical perspective, with the vendor's problem taking longer to solve as the number of scenarios increases. While it is feasible (and realistic) for the customer to generate thousands of scenarios (given that the customer's problem is not NP‐complete), this is not an option for the vendor. Ideally, the number of scenarios used by the vendor has to be small enough to ensure solvability and large enough to ensure that the optimal demo stays relatively unchanged if

(V S_{L})

is solved multiple times (with different scenarios in each run).

One characteristic of the optimal demo is that the effective re‐engineering benefit signaled by any feature included in the demo will exceed the productivity benefits given away as a result of this feature being part of the demo. This is because the signal is obtained as the difference between the estimated value of the software given the demo, and the value that is given away through the demo. Consequently, if a feature gives away more than it helps improve the value of the signal, a better signal can obtained by removing this feature from the demo.

Case Study: 3G Wireless Network Provisioning Software

As mentioned earlier, this work is motivated by a feature‐limited demo design problem encountered by a major wireless telecommunications equipment manufacturer. In this section, we analyze a small version of the problem they encounter, and show that a systematic approach can help even with small problems.

A typical 3G wireless network consists of base‐stations deployed across a geographical region controlled centrally by a base station controller. Once a network is deployed, the network operator only needs to manage the network.

WiNetPro is a free feature‐limited software developed by the company to automate several network operator functions for a telecommunications service provider. This helps the operators get familiar with its functions and enables them to make an informed decision on the purchase of the complete, licensed version. The company assigned features into their demo in an ad‐hoc manner based on intuition about customer requirements and feature functionalities. Our model identifies an optimum mix of features that provides a better signal to the customer. Specific names have been altered and the model simplified for the purpose of illustrating the case study.

Figure 2a gives the technical overview of how the software operates. The Wireless Telecommunications Network Manager represents the wireless network that is currently under operation. All configuration data of the network is stored here. In order to automate configuration value changes, the operator would extract and upload all the system data from the network manager to WiNetPro. WiNetPro also has the provision to take configuration change instructions or recommendation from an external source. The External Performance Tuning Software takes as input performance data of the network and makes parameter change recommendations to WiNetPro. The operator would then use WiNetPro to automate various functions such as Neighbor list changes or backhaul reconfigurations. The software would in turn generate configuration value change scripts which can be downloaded to the network manager so that they can be run on the network at a convenient time.

Figure 2

WiNetPro Overview and Configuration

Features

Figure 2b is an adapted version of a much larger version of WiNetPro's features‐task network. There are 4 tasks consisting of 11 subtasks. Task 1 consists of three subtasks

t_{1.1}

t_{1.2}

, and

t_{1.3}

that together form the functionality of neighbor list management which updates all reciprocal neighbors with a new cell. Task 2 consists of four subtasks that are used for parameter auditing. Task 3 and 4 consists of two subtasks each of which perform the function of backhaul reconfiguration. There are 16 features, two of which contribute to more than one subtask.

The list of features to include in the demo were originally chosen in an ad‐hoc manner. The intention was to select one basic feature from the set of features contributing to a task. The demo consists of features

f_{1.1}, f_{2.1}, f_{3.1 . 1}, f_{4.1 . 2}

, and

f_{4.2 . 1}

. The remaining features are available only in the premium version. The justification in the Neighbor list management set is to make feature

f_{1.1}

(Update 1 Cell with 1 Neighbor) into a basic feature so that the operator has a flavor of the functionality, but can only add one neighbor to a cell at a time. Although this functionality automates a key function, it has to be manually repeated several times to integrate a new base station fully into the network. There are premium features (

f_{1.2}

and

f_{1.3}

) that provide the next level of automation to run these commands on multiple nodes and to scan and identify the neighbors to be added.

Case Study Optimization

We solved the problem in CPLEX to identify the set of features to include in the demo version of this simplified WiNetPro software. The average values of the parameters

π_{j}

and

β_{i j}

provided in the Tables 2 and 3 are obtained from consultations with the project managers of the company. The negative value for

π_{t_{4.1}}

indicates that the task cannot be performed manually without the help of the features

f_{4.1 . 1}

f_{4.1 . 2}

, and

f_{4.1 . 3}

. Similarly, a π value of −∞ for tasks

t_{2.1}

t_{2.2}

t_{2.3}

, and

t_{2.4}

indicates that these tasks cannot be performed even if the complete software product was available.

Table 2

Average Values of

π_{j}

in $1000s

	$t_{1.1}$	$t_{1.2}$	$t_{1.3}$	$t_{2.1}$	$t_{2.2}$	$t_{2.3}$	$t_{2.4}$	$t_{3.1}$	$t_{3.2}$	$t_{4.1}$	$t_{4.2}$
$π_{j}$	1.542	4.625	4.625	−∞	−∞	−∞	−∞	5	5	−6.25	463.25

Table 3

Average Values of

β_{i j}

in $1000s

	t _1.1	$t_{1.2}$	$t_{1.3}$	$t_{2.1}$	$t_{2.2}$	$t_{2.3}$	$t_{2.4}$	$t_{3.1}$	$t_{3.2}$	$t_{4.1}$	$t_{4.2}$
$f_{1.1}$	0.094
$f_{1.2}$		0.094
$f_{1.3}$			0.281
$f_{2.1}$				0.934
$f_{2.2}$					0.875
$f_{2.3}$						0.875
$f_{2.4}$							0.875
$f_{3.1 . 1}$								1.875
$f_{3.1 . 2}$								1.875
$f_{3.2 . 1}$									1.875
$f_{3.2 . 2}$									1.875
$f_{4.1 . 1}$										9.2
$f_{4.1 . 2}$		0.094								3
$f_{4.1 . 3}$		0.094								3
$f_{4.2 . 1}$											13.78
$f_{4.2 . 2}$											13.78

We obtained 100 scenarios through 100 random draws from a uniform distribution

U [0, β_{i j}]

. The optimal demo has six features,

f_{2.1}, f_{2.2}, f_{2.3}, f_{2.4}, f_{4.1 . 2}

, and

f_{4.1 . 3}

. Each of these features cater to the tasks which cannot be done manually (i.e., the

π_{j}

for these tasks are negative). Additionally, task

t_{4.1}

can now be done when the features

f_{4.1 . 2}

, and

f_{4.1 . 3}

are introduced in the demo. This is an example of a re‐engineering effect. The signal, given the ad‐hoc demo, is obtained by fixing the

x_{i}

variables to 1 for the demo features (

f_{1.1}, f_{2.1}, f_{3.1 . 1}, f_{4.1 . 2}

, and

f_{4.2 . 1}

) and 0 for the non‐demo features. Table 4 provides a comparison of the optimal signal and the signal obtained through the ad‐hoc approach. The signal obtained from the optimal demo is 65% higher than that from the ad‐hoc demo.

Table 4

Signal Comparison (in $1000s)

Optimal		Ad‐hoc approach
Signal	Demo	Signal	Demo	Improvement
21.41	$f_{2.1}, f_{2.2}, f_{2.3}, f_{2.4}, f_{4.1 . 2}, f_{4.1 . 3}$	12.98	$f_{1.1}, f_{2.1}, f_{3.1 . 1}, f_{4.1 . 2}, f_{4.2 . 1}$	65%

Performance of Commercial Solvers on Large Problems

The larger version of WiNetPro has over 100 features. In this section, we conduct additional experiments on problems of realistic size to investigate how effective commercial solvers are in solving the vendor's problem. The Branch‐And‐Reduce Optimization Navigator (BARON) (Sahinidis 1996) is a state‐of‐the‐art computational system for solving non‐convex optimization problems, while CPLEX ( 2011) is recognized as the leading software for solving integer programs. CPLEX is run on Intel Core i5 CPU running at 3.20 GHz while the BARON solver is run on NEOS servers. The server used for our experiments had 2 Intel Xeon X5660 CPUs running at 2.8 GHz (12 cores total).

There are various aspects of the problem that could potentially affect the effectiveness and quality of the solutions obtained. Two critical ones are the variability of the parameters and network structure (the density of the network linking features and tasks). The average connections per feature (r) and the average connections per task (q) are set to 10% in the sparse network, 50% in the medium network and 90% in the dense network.

The results presented in this section are for a software product with 75 features that can (profitably) perform 100 tasks for the customer. We recognize that in general, enterprise software programs contain more than 75 features and 100 tasks. For example, Oracle's PeopleTools 8.53 has 425 features (PeopleTools 2013). The results of these experiments make it clear why we chose not to consider more than 75 features and 100 tasks—neither of the commercial solvers were able to provide any result even after 2 days. The parameters

π_{j}

and

β_{i j}

for these experiments are drawn from discrete uniform distributions U(−160, 40) and U(10, 50) respectively. These parameter values are chosen such that about 20% of the tasks would be performed without the software. The means

μ_{π}

and

μ_{β}

are −60 and 30 respectively, while the standard deviations

σ_{π}

and

σ_{β}

are 58 and 11.8 respectively. Four values are considered for the number of scenarios (25, 50, 75 and 100) and the

b_{i j}^{s}

values are drawn from

U (0, β_{i j})

(i.e., the vendor is assuming that the customer is always underestimating, to be consistent with existing literature). The linearized formulation

(V S_{L})

is solved using CPLEX, while the nonlinear formulation (VS) is solved using BARON. Table 5 summarizes the experimental results, including the solution time in seconds.

Table 5

Performance of BARON and CPLEX on Large Problems

Network structure (r%, q%)	Scenarios	BARON			CPLEX
Network structure (r%, q%)	Scenarios	Demo size	Objective value	Time (seconds)	Demo size	Objective value	Time (seconds)
(10, 10)	25	13	7431	98	14	7463	3041
	50	14	7421	421	14	7497.2	78,234
	75	NA	NA	NA	14	7484.7	141,020
	100	NA	NA	NA	NA	NA	NA
(50,50)	25	4	51,810	362	3	51,840	1058
	50	NA	NA	NA	4	51,722	4810
	75	NA	NA	NA	3	51,825	10,194
	100	NA	NA	NA	3	51,852	16,435
(90,90)	25	2	96,767	498	2	96,784	419
	50	NA	NA	NA	2	96,712	2093
	75	NA	NA	NA	2	96,723	5773
	100	NA	NA	NA	2	96,722	8973

While BARON is able to solve the smaller problems relatively quickly, it encounters difficulty as the problem sizes get larger (in terms of network density and the number of scenarios used). Moreover, we find that the solutions found by BARON are often suboptimal, and hence not reliable. CPLEX on the other hand, is able to solve all the problems but one. However, it takes a considerable amount of time to solve them. The largest problem in the sparse network was not solved even after 50 hours. As more scenarios give more precise estimates of the signal, these results make clear that neither solver will be able to solve problems of realistic size, when more features and tasks are involved.

The Scenario Aggregation Approach

As the number of scenarios increases, so does the difficulty of solving formulations (VS) and

(V S_{L})

. As the results in Table 5 show, solving the models directly in a commercial solver is not practical for problems of realistic size. We pointed out when solving the customer's problem that this problem decomposes into easily solved subproblems once the demo is available. As the variables

x_{i}

and

ρ_{j}

link the scenarios together, this is equivalent to saying that (VS) and

(V S_{L})

decompose into

| S |

easy problems (one per scenario), once the

x_{i}

and

ρ_{j}

variables are fixed.

(V S_{L})

falls under the general category of scenario aggregation formulations. It is well‐known that scenario aggregation formulations for real‐world problems can be so large as to make it impossible to solve optimally.

Lagrangian decomposition (Guignard and Kim 1987) based approaches have been successfully used to solve scenario aggregation problems (e.g., Glockner et al. 2001, Jönsson et al. 1993), and the approach proposed by Jönsson et al. ( 1993) can be easily adapted to our context. This involves defining scenario‐specific “clones”

x_{i}^{s}

and

ρ_{j}^{s}

of the

x_{i}

and

ρ_{j}

variables, and adding constraints that force the clones in each scenario to be equal, as follows:

\begin{matrix} x_{i}^{1} = x_{i}^{2}, x_{i}^{2} = x_{i}^{3}, \dots, x_{i}^{k} = x_{i}^{k + 1}, \dots, x_{i}^{S - 1} \\ = x_{i}^{S} \forall i \in F \end{matrix}

and

\begin{matrix} ρ_{j}^{1} = ρ_{j}^{2}, ρ_{j}^{2} = ρ_{j}^{3}, \dots, ρ_{j}^{k} = ρ_{j}^{k + 1}, \dots, ρ_{j}^{S - 1} \\ = ρ_{j}^{S} \forall j \in T \end{matrix}

These constraints are then relaxed, with each violation being penalized. Specifically, Lagrangian multipliers

λ_{i}^{k}

and

μ_{j}^{k}

are associated with the

k^{t h}

equality constraints in 18 and 19 respectively (k = 1, 2, …, S − 1), and the following terms are added to the objective function:

\begin{matrix} \sum_{i \in F} \sum_{k = 1}^{S - 1} λ_{i}^{k} (x_{i}^{k} - x_{i}^{k + 1}) \\ = \sum_{i \in F} (λ_{i}^{1} x_{i}^{1} + (- λ_{i}^{1} + λ_{i}^{2}) x_{i}^{2} + \dots - λ_{i}^{S - 1} x_{i}^{S}) \\ = \sum_{k \in S} \sum_{i \in F} w_{i}^{k} x_{i}^{k} \end{matrix}

\begin{matrix} \sum_{j \in T} \sum_{k = 1}^{S - 1} μ_{j}^{k} (ρ_{j}^{k} - ρ_{j}^{k + 1}) \\ = \sum_{j \in T} (μ_{j}^{1} ρ_{j}^{1} + (- μ_{j}^{1} + μ_{j}^{2}) ρ_{j}^{2} + \dots - μ_{j}^{S - 1} ρ_{j}^{S}) \\ = \sum_{k \in S} \sum_{j \in T} u_{j}^{k} ρ_{j}^{k} \end{matrix}

The multipliers

w_{i}^{s}

and

u_{j}^{s}

in the above equations are obtained by collecting the Lagrangian multipliers for each scenario s as follows

\begin{matrix} w_{i}^{1} = λ_{i}^{1}, w_{i}^{2} = - λ_{i}^{1} + λ_{i}^{2}, \dots, \\ w_{i}^{k} = - λ_{i}^{k - 1} + λ_{i}^{k}, \dots, w_{i}^{S} = - λ_{i}^{S - 1} \end{matrix}

and

\begin{matrix} u_{j}^{1} = μ_{j}^{1}, u_{j}^{2} = - μ_{j}^{1} + μ_{j}^{2}, \dots, \\ u_{j}^{k} = - μ_{j}^{k - 1} + μ_{j}^{k}, \dots, u_{j}^{S} = - μ_{j}^{S - 1} \end{matrix}

The Lagrangian dual problem

(V S_{D})

(V S_{L})

can now be written as

(V S_{D}) Min L D (w, u), where

\begin{matrix} L D (w, u) = Max \sum_{s \in S} p^{s} [\sum_{j \in T} ((π_{j} + \sum_{i \in F} b_{i j}^{s}) y_{j}^{s} + \sum_{i \in F} (β_{i j} - b_{i j}^{s}) z_{i j}^{s}) - \sum_{i \in F} w_{i}^{s} x_{i}^{s} - \sum_{j \in T} u_{j}^{s} ρ_{j}^{s} - \sum_{j \in T} ρ_{j}^{s}] \end{matrix}

s.t. z_{i j}^{s} \leq x_{i}^{s} \forall s \in S; \forall i j \in E

z_{i j}^{s} \leq y_{j}^{s} \forall s \in S; \forall i j \in E

z_{i j}^{s} \geq (x_{i}^{s} + y_{j}^{s} - 1) \forall s \in S; \forall i j \in E

ρ_{j}^{s} \geq (π_{j} + \sum_{i \in F} β_{i j} x_{i}^{s}) \forall s \in S; \forall j \in T

ρ_{j}^{s} \geq 0 \forall s \in S; \forall j \in T

x_{i}^{s}, y_{j}^{s} \in {0, 1} \forall s \in S; \forall i \in F; \forall j \in T

This dual problem not only decomposes into separate smaller problems for each scenario, it also provides an upper bound to the objective function value of

(V S_{L})

. While solutions to each scenario are easy to obtain, feasible solutions necessitate that the

x_{i}^{s}

be set to the same values in each scenario. The scenario aggregation algorithm described in the Appendix B combines the scenario solutions systematically to find feasible solutions.

Performance of Scenario Aggregation

As we observed in our earlier experiments, neither BARON nor CPLEX can solve problems of realistic size efficiently. We apply the scenario aggregation algorithm to the same problems, and the results are provided in Table 6. We also repeat the results presented in Table 5 for easy comparison. The maximum iteration counter is set to 30, and the procedure terminates when the gap between the upper and lower bounds falls below 1%. The upper and lower bounds are obtained through the scenario aggregation procedure described in the Appendix B. Note that the lower bound is always a feasible solution to the original integer program

(V S_{L})

. As we can see, scenario aggregation is able to solve all of these large problems within two hours.

Table 6

Performance of Scenario Aggregation

Network structure (r%, q%)	Scenarios	Scenario aggregation				BARON solver			CPLEX solver
Network structure (r%, q%)	Scenarios	Demo size	Upper bound	Lower bound	Time (seconds)	Demo size	Objective value	Time (seconds)	Demo size	Objective value	Time (seconds)
(10, 10)	25	14	7529.6	7461.1	1197	13	7431	98	14	7463	3041
	50	14	7575.2	7497.2	2726	14	7421	421	14	7497.2	78,234
	75	14	7565.3	7484.7	5171	NA	NA	NA	14	7484.7	141,020
	100	14	7576.7	7498.3	7142	NA	NA	NA	NA	NA	NA
(50, 50)	25	4	52,045	51,826	65	4	51,810	362	3	51,840	1058
	50	4	51,921	51,722	130	NA	NA	NA	4	51,722	4810
	75	3	52,029	51,825	193	NA	NA	NA	3	51,825	10,194
	100	4	52,050	51,852	282	NA	NA	NA	3	51,852	16,435
(90, 90)	25	2	96,944	96,784	64	2	96,767	498	2	96,784	419
	50	2	96,888	96,712	119	NA	NA	NA	2	96,712	2093
	75	2	96,873	96,723	192	NA	NA	NA	2	96,723	5773
	100	2	96,877	96,722	321	NA	NA	NA	2	96,722	8973

Scenario aggregation identifies optimal or near‐optimal solutions extremely quickly, taking <25 minutes on average, across all the 12 problems solved. The sparse network problems took around 5–10 iterations (mostly to reduce the upper bound to reach the tolerance of 1%) while the medium and dense network problems took only a single iteration to find the solution. The best feasible solution identified is the same as the optimal one obtained from CPLEX in 9 out of 11 problems—for the remaining 2 problems, the feasible solution is <0.03% away from the optimum. The relative effectiveness of scenario aggregation gets more pronounced as the number of scenarios approaches 100. In the largest problem involving the sparse network, both BARON and CPLEX failed to provide any solution within a reasonable time while scenario aggregation found a solution in <2 hours. These results show that scenario aggregation can find near‐optimal solutions quickly, with the benefits being more apparent when the number of scenarios is large. A large number of scenarios is preferred, as it gives more precise estimates of the signal. However, that is precisely when both the optimal approaches are likely to fail.

Next, we conduct a similar set of experiments to study the impact on the performance of scenario aggregation as the variability of parameters decreases. In these experiments, we use

σ_{π} = 1

and

σ_{β} = 1

; the corresponding results are presented in Table 7. The

π_{j}

and

β_{i j}

are drawn from U(−61.3, −58.7) and U(28.7, 31.3) respectively, to maintain the same values of

μ_{π} = - 60

and

μ_{β} = 30

as in the higher variability case. CPLEX was not able to solve even the smallest problem after 50 hours of computation. This is expected, as the near‐homogeneous nature of the parameters induces symmetry in the integer program

(V S_{L})

. Integer programs with symmetry are well known to be difficult to solve via traditional branch and bound (Margot 2009). Therefore, results from solving the problems in CPLEX are not presented in Table 7. Baron also performed poorly, solving only 4 out of the 12 problems (providing suboptimal solutions in each case). These experiments confirm our earlier results—neither BARON nor CPLEX will be effective on problems of realistic size.

Table 7

Performance of BARON and Scenario Aggregation (Low Parameter Variability)

Network structure (r%, q%)	Scenarios	Scenario aggregation				BARON solver
Network structure (r%, q%)	Scenarios	Demo size	Upper bound	Lower bound	Time (seconds)	Demo size	Objective value	Time (seconds)
(10, 10)	25	19	7939.2	7724.0¹	43,406	17	7462	107
	50	19	7934.2	7703.2¹	184,250	18	7542	466
	75	19	7924.9	7698.5¹	116,460	NA	NA	NA
	100	19	7941.2	7710.9¹	176,960	NA	NA	NA
(50, 50)	25	4	52,973	52,782	556	0	50,437	367
	50	4	52,812	52,613	943	NA	NA	NA
	75	4	52,838	52,636	1596	NA	NA	NA
	100	4	52,791	52,591	2017	NA	NA	NA
(90, 90)	25	2	98,141	97,849	81	NA	NA	NA
	50	2	98,411	98,092	150	NA	NA	NA
	75	2	98,170	97,837	251	NA	NA	NA
	100	2	98,235	97,887	345	NA	NA	NA

A tolerance of 3% is used.

Scenario aggregation solves all the problems involving medium and dense networks relatively quickly, taking 1278 and 207 seconds respectively on average. BARON had difficulty with these problems and could only solve the smallest problem in the medium network suboptimally. The performance of scenario aggregation deteriorates considerably when the network is sparse; it takes 5–8 iterations and over 36 hours on average for the heuristic to converge within a gap of 3%. While the best solution found was always better than that provided by BARON, the slow convergence is a concern.

A Continuous Approximation and the Augmented Heuristic

We see that BARON, CPLEX, and scenario aggregation are all unable to solve problems efficiently when the variabilities in

π_{j}

and

β_{i j}

are very small. As mentioned earlier, this is likely to be a result of symmetry in the integer program

(V S_{L})

. To overcome this difficulty, we first solve a continuous approximation to estimate the number of features in the demo, and use the result of this analytical model in section to develop an augmented heuristic (AH) to find fast and near‐optimal solutions.

The Continuous Model

We start with a simplified model where the feature‐to‐task mapping is assumed to be homogenous. This implies that we have

N = | F |

homogenous features catering to

T = | T |

homogenous tasks. The vendor needs to decide on the number of features n to include in the demo such that the value of the signal detected by the customer is maximized.

We define q (≥1) to be the average number of features connected to a task and r (≥1) to be the average number of tasks connected to a feature. Therefore, the total number of connections between features and tasks is qT = rN. On average, each task will map to

\frac{n r}{T}

features in the demo and

\frac{(N - n) r}{T}

features not in the demo. The customer will perform all tasks for which the expected net benefit is positive that is,

E_{π, b} [π + \frac{β n r}{T} + \frac{(N - n) b r}{T}] > 0

. Therefore,

{\tilde{Π}}_{F}^{D}

which is the revised estimate of the profit with the complete software given a demo is

E_{π, b} {[T (π + \frac{β n r}{T} + \frac{(N - n) b r}{T})]}^{+}

. Here,

E_{π, b}

is the expectation over the variables π and b while

E_{π, b}^{+}

is the expectation over π and b when the argument is positive. To obtain the signal, the customer needs to subtract the value

Π_{D}

of the demo

D

from

{\tilde{Π}}_{F}^{D}

. The profit

Π_{D}

of using only the features in

D

can be obtained by removing the term

\frac{(N - n) b r}{T}

from the formulation of

{\tilde{Π}}_{F}^{D}

. Consequently, the vendor will formulate problem (VC) to obtain the optimum number of features n in the demo that maximizes the signal

Ψ^{V C}

. We denote the vendor's estimate of the signal as

Ψ^{V C}

, to distinguish it from the more precise estimate of Ψ calculated by the customer.

\begin{matrix} (V C) \underset{0 \leq n \leq N}{Max} Ψ^{V C} = E_{π, b} {[T (π + \frac{β n r}{T} + \frac{(N - n) b r}{T})]}^{+} \\ - E_{π} {[T (π + \frac{β n r}{T})]}^{+} \end{matrix}

(VC) can be solved by treating

\hat{π}

and

\hat{b}

as point estimates. The result is captured in Proposition 2 (proof in Appendix C).

Proposition 2

For a homogenous feature‐to‐task mapping with

\hat{π}

and

\hat{b} \leq β

as point estimates, the optimal number of features

n^{⋆}

to be included in the demo and the corresponding signal

Ψ^{V C} (n^{⋆})

are

\begin{matrix} (n^{⋆}, Ψ^{V C} (n^{⋆})) \\ = \{\begin{matrix} (0, 0), & i f \hat{π} \in (- \infty, - \frac{β r N}{T}) & (2.1) \\ (- \frac{\hat{π} T}{β r}, \hat{b} r (N + \frac{\hat{π} T}{β r})), & i f \hat{π} \in [- \frac{β r N}{T}, 0] & (2.2) \\ (0, \hat{b} r N), & i f \hat{π} \in [0, \infty) & (2.3) \end{matrix} \end{matrix}

Propositions 2.1 and 2.3 identify situations where it would not be in the best economic interest of the vendor to provide a feature‐limited demo. Proposition 2.1 says that the vendor will not provide a demo if the pre‐software profit

\hat{π}

from a task is less than

- \frac{β r N}{T}

, the total profit from a task when the entire software is available. Therefore, the customer will not be able to perform any task even with the entire software, since

(\hat{π} + \frac{β r N}{T}) < 0

. Hence, providing a free demo would not generate productivity or re‐engineering gains. Similarly, the vendor is better off by not providing any demo when

\hat{π}

is non‐negative. In this case, the customer will be able to profitably perform all the tasks without the software and the software provides no re‐engineering benefits. On the other hand, when

\hat{π} \in [- \frac{β r N}{T}, 0]

, there will be both re‐engineering and productivity benefits. In this case a more negative π will lead to a large demo as more features are needed to signal the re‐engineering benefits for a task. The optimal demo size

n^{⋆}

decreases with β—as the value per feature increases, fewer features are needed for the same level of profit. Along the same lines,

n^{⋆}

is smaller while the strength of the signal is higher for denser networks. As r increases, more tasks get connected to a feature. Hence, fewer features in a dense network will have the same effect on profit as more features in a sparse network. It is interesting to note that the optimal number of features

n^{⋆}

is independent of the estimate

\hat{b}

Incorporating Insights from the Continuous Model

We saw earlier that both the optimal and the scenario aggregation approaches have difficulty when the parameter variability is low, and the network is sparse. In this section, we develop an Augmented Heuristic (AH) that explicitly incorporates the results from the continuous model into formulation

(V S_{L})

, to solve it effectively.

First, we obtain an estimate of the optimal demo size

n^{⋆}

by replacing the point estimates

\hat{π}

and

\hat{β}

with the corresponding mean values π and

\bar{β}

, and solving the continuous version using Proposition 2. We then find the smallest number of features required to make the expected benefit of performing a task positive. If q is the average number of features contributing to a task, then on average,

\frac{n^{*} q}{N}

features in the demo and

\frac{(N - n^{*}) q}{N}

features not in the demo will be contributing to a task. Therefore, the total expected benefit of performing a task is

(\bar{π} + \bar{β} \frac{n^{*} q}{N} + \bar{b} \frac{(N - n^{*}) q}{N})

. The smallest value of q that makes this expected benefit positive (say,

q_{l}

) is obtained by finding the smallest value of q that makes

(\bar{π} + \bar{β} \frac{n^{*} q}{N} + \bar{b} \frac{(N - n^{*}) q}{N}) > 0

. Next, we identify all tasks that are connected to at least

q_{l}

features—performing these tasks is expected to result in positive benefits. We fix the variable

y_{j}^{s}

to 1 for all such tasks j in every scenario s, and to 0 for all other tasks in every scenario. Once the

y_{j}^{s}

variables are fixed, formulation

(V S_{L})

is substantially reduced; this reduced version of

(V S_{L})

is solved in CPLEX to obtain the solution to the original problem.

Table 8 compares the results of the Augmented Heuristic and scenario aggregation for problems involving low parameter variability (

σ_{π} = 1

and

σ_{β} = 1

). The mean values of

π_{j}

and

β_{i j}

are set to −60 and 30 respectively. As before, three density levels are considered—sparse, medium and dense. The same datasets in Table 7 are used in these experiments.

Table 8

Performance of Augmented Heuristic (Low Parameter Variability)

Network structure (r%, q%)	Scenarios	Cont. demo size	Augmented heuristic			Scenario aggregation			BARON solver
Network structure (r%, q%)	Scenarios	Cont. demo size	Demo size	Objective value	Time(seconds)	Demo size	Lower bound	Time (seconds)	Demo size	Objective value	Time (seconds)
(10, 10)	25	20	19	7727.6	15	19	7724.0¹	43,406	17	7462	107
	50	20	20	7691.8	32	19	7703.2¹	184,250	18	7542	466
	75	20	20	7661.7	32	19	7698.5¹	116,460	NA	NA	NA
	100	20	19	7676.5	49	19	7710.9¹	176,960	NA	NA	NA
(50, 50)	25	4	4	52,782	14	4	52,782	556	0	50,437	367
	50	4	4	52,613	29	4	52,613	943	NA	NA	NA
	75	4	4	52,636	36	4	52,636	1596	NA	NA	NA
	100	4	4	52,591	37	4	52,591	2017	NA	NA	NA
(90, 90)	25	2	2	97,849	13	2	97,849	81	NA	NA	NA
	50	2	2	98,098	15	2	98,092	150	NA	NA	NA
	75	2	2	97,837	29	2	97,837	251	NA	NA	NA
	100	2	2	97,902	32	2	97,887	345	NA	NA	NA

A tolerance of 3% is used.

The quality of the signal degrades slightly as the network becomes sparser. However, the signal from the Augmented Heuristic is almost the same as the best one obtained from scenario aggregation. In fact, in several cases, the Augmented Heuristic is able to improve upon the signal from scenario aggregation. This is probably because the scenario aggregation algorithm is terminated at the convergence tolerance of 3% for the sparse network and 1% for the medium and dense networks. The fact that these near‐optimal solutions are identified in a matter of seconds—the average solution time for the 12 problems we tried was only 27.8 seconds—makes the Augmented Heuristic particularly appealing for low parameter variability contexts. We see that the optimal demo size decreases as the network density increases, as predicted by the continuous model.

Table 9 provides a quick reference for the best method to adopt for each combination of parameter variability, network structure and number of scenarios. The Augmented Heuristic is preferred for problems with low parameter variability. It is able to find a near‐optimal demo within 28 seconds on average with an accuracy within 3% of the optimal. For problems with high parameter variability, the scenario aggregation approach is able to find the optimal signal in <25 minutes on average. Moreover, scenario aggregation is the only method that is able to solve all 12 trials. In the sparse network with high variability, scenario aggregation occasionally gives suboptimal signals when the number of scenarios is fewer than 25. CPLEX is practical here, and we recommend using it when the number of scenarios is fewer than 25.

Table 9

Performance Comparison

Parameter variability	Network structure	Comparative performance			Best method
Parameter variability	Network structure	Method	Optimality	Average time (seconds)	Best method
Low	Sparse	BARON	Unreliable	—	AH
		SA	Within 3%	36 hours
		AH	Within 3%	32
	Medium	BARON	Unreliable	—	AH
		SA	Within 1%	1278
		AH	Within 1%	29
	Dense	BARON	Unreliable	—	AH
		SA	Within 1%	207
		AH	Within 1%	22
High	Sparse	CPLEX	Optimal	1–50 hours	SA/CPLEX¹
		BARON	Unreliable	—
		SA	Optimal	4059
	Medium	CPLEX	Optimal	8124	SA
		BARON	Unreliable	—
		SA	Optimal	168
	Dense	CPLEX	Optimal	4315	SA
		BARON	Unreliable	—
		SA	Optimal	174

CPLEX is the preferred method for scenarios ≤25.

Extending to a Multi‐Segment Model

So far, we have considered a context where the demo is being constructed either for a single customer, or for a single segment of homogeneous customers. This is because our work is motivated by a problem from the telecommunications industry where, even when the demo is not being built for a single customer, the customer segments were clearly identified. Many software vendors do not have that luxury, and would need to either design a single demo to serve across multiple customer segments, or spend time and effort to identify the customers in each segment (which would enable them to provide customized demos to each segment). All the formulations and solution approaches we have presented so far easily extend to the context of building a single demo in a multi‐segment environment.

Usually, vendors can segment the market according to customer needs. Suppose

K

represents the set of customer segments, and

p_{k}

the proportion of customers in segment k. As before, benefits are a function of how important a task is to the customer, and there will be segment specific values

π_{j}^{k}

and

β_{i j}^{k}

for each segment

k \in K

. If a single demo needs to be assembled to serve all the customer segments, the first change needed is in how the scenarios are generated—we need to generate scenarios in the proportion customers exist in the population. So we generate

S_{k}

scenarios from each segment

k \in K

, such that

\frac{S_{k}}{⋃_{k \in K} S_{k}} = p_{k}

, where

⋃_{k \in K} S_{k}

is the set of all scenarios,

S

. Once the scenarios are drawn appropriately, the objective function and constraints need to be adjusted to reflect the segments. The modified formulation is

(V S_{M})

below. Other than the

x_{i}

variables, all the parameters and variables in

(V S_{M})

have a new index k to identify the customer segment. The

x_{i}

variables are independent of the customer segments as there has to be one demo across all the segments.

\begin{matrix} (V S_{M}) Max & \sum_{k \in K} p_{k} (\sum_{s \in S_{k}} p^{k s} (\sum_{j \in T} (π_{j}^{k} + \sum_{i \in F} β_{i j}^{k} x_{i} + \sum_{i \in F} b_{i j}^{k s} (1 - x_{i})) y_{j}^{k s}) - \sum_{j \in T} ρ_{j}^{k}) \end{matrix}

s.t. ρ_{j}^{k} \geq (π_{j}^{k} + \sum_{i \in F} β_{i j}^{k} x_{i}) \forall j \in T; \forall k \in K

ρ_{j}^{k} \geq 0 \forall j \in T; \forall k \in K

x_{i} \in {0, 1} \forall i \in F

y_{j}^{k s} \in {0, 1} \forall j \in T; \forall s \in S_{k}; \forall k \in K

If the vendor had perfect information on the segments each customer belonged to, they could provide customized demos to each customer segment and do better. The difference between the expected signal from the customized demos and from the signal from the single demo is the expected value of knowing the customer segments perfectly. This expected value of perfect information (EVPI) provides the loss in the signal resulting from the need to build a single demo. Conversely, it provides the vendor an estimate of the amount they should be willing to spend in order to identify the segments their customers belong to.

Table 10 shows results from computational experiments involving three customer segments—a “low” segment comprising customers who generate limited benefits from the software, a “high” segment comprising customers who generate substantial benefits from the software, and a “medium” segment comprising customers who generate benefits that are somewhere in between. The “Low,” “Medium,” and “High” columns in Table 10 present results based on providing a customized demo to each segment. Results for providing a single demo that hedges across all three customer segments is provided under “Combined.” The “EVPI” column provides the expected value of perfect information—this is the expected benefit to be gained by identifying the members of each customer segment perfectly.

Table 10

Multiple Segments and EVPI

Network structure (r%, q%)	Low			Medium			High			Combined
Network structure (r%, q%)	Scenarios	Demo size	Signal	Scenarios	Demo size	Signal	Scenarios	Demo size	Signal	Scenarios	Demo size	Signal	EVPI
(10, 10)	50	4	952	25	17	1512	25	9	3930	100	7	1704	132.5
	25	5	952	50	18	1487	25	9	3930	100	9	1794	170.0
	25	5	952	25	17	1512	50	10	3918	100	10	2473	102.0
(50, 50)	50	8	6235	25	10	17,822	25	4	32,535	100	5	15,345	361.8
	25	9	6204	50	10	17,750	25	4	32,535	100	4	17,985	574.8
	25	9	6204	25	10	17,822	50	4	32,650	100	5	22,005	326.5
(90, 90)	50	8	14,345	25	5	37,346	25	2	62,100	100	3	31,651	383.0
	25	8	14,423	50	5	37,299	25	2	62,100	100	3	37,322	458.3
	25	8	14,423	25	5	37,346	50	2	62,246	100	3	43,736	329.3

For these experiments, the segments are created by keeping the coefficients of variation (CV) for

π_{j}

and

β_{i j}

the same across all the segments. The

π_{j}

values for the low, medium and high types are drawn from uniform distributions with means −100, −80 and −60 respectively. The standard deviations for

π_{j}

are taken as 96.7, 77.3 and 58 for low, medium and high types respectively. Likewise, the

β_{i j}

values are also drawn from uniform distributions with means 10, 20 and 30 for low, medium and high respectively. The standard deviations for

β_{i j}

are 3.9, 7.8 and 11.8 for low, medium and high respectively. This maintains the CV for

π_{j}

and

β_{i j}

at −0.97 and 0.39 respectively across the three segments.

Experiments are conducted on three customer segment type distributions for each network structure. A total number of 100 scenarios are generated in each experiment; the first category has

p_{l o w} = 0.5

p_{m e d i u m} = p_{h i g h} = 0.25

, the second has

p_{m e d i u m} = 0.5

p_{l o w} = p_{h i g h} = 0.25

, and the third has

p_{h i g h} =

0.5 p_{l o w} = p_{m e d i u m} = 0.25

. The scenarios from each segment are drawn from

U [0, β_{i j}]

in the same proportion as

p_{l o w}

p_{m e d i u m}

and

p_{h i g h}

We see that the EVPI is smallest when the probability of a customer belonging to a high type segment is high. This is partly a result of the fact that the high segment drives the combined demo to a great extent, and the loss in signal is primarily a result of some features not being in the demo to help the low and medium types. Overall however, Table 10 suggests that the loss in the signal by combining all the segments is not very high. It is possible however, that the magnitude of the loss will increase as the number of segments increase.

From a business perspective, the decision of whether to provide a single demo or not must be made carefully. As we now provide a single demo that, in a crude sense, averages across different customer segments, the single demo is clearly not optimal for any single segment. Ideally, the best option is to customize a demo for each segment. However, this requires that the firm distinguish between customers in different segments. Table 10 provides the benefits of identifying customer segments perfectly. However, there is benefit to be gained even if the customer segments are not identified perfectly, that is, even if the firm can make noisy observations about the segment to which a customer belongs. A very similar analysis can provide the vendor with the expected value of imperfect information as well. That is, the models presented in this study offer a sound basis for the firm to choose between providing a single demo and providing several customized demos based on a noisy signal about the segment to which a customer belongs.

Conclusions

An important problem for many companies is that of designing a feature limited version of their product targeted to specific customers in order to signal the value of the full product. Such feature‐limited products have been used successfully in various industries. In spite of the popularity and advantages of this model, there has been very little research into the optimal design of feature‐limited demonstration software. This study is the first attempt to develop a theoretical basis for designing feature‐limited demos.

We first develop a scenario‐based approach to model how customers should evaluate software products, given a feature‐limited demo. The customer's problem is shown to be easily solved through the sequential evaluation of the signal under many scenarios. However, this is not the case with the vendor's problem—the vendor needs to incorporate the customer's evaluation process into their decision, and identify the best demo to provide the customer. We formulate the vendor's problem of designing the best feature‐limited demo as a non‐linear integer program that incorporates in it the scenario‐based evaluation approach used by the customer and show that it is NP‐complete. We show how to linearize the non‐linear formulation, and show through a case study from a telecommunications company how optimal design can be beneficial even when the problem is small. The case study highlights how feature‐limited demos can be used by a vendor to “showcase” features of a product and entice customers to try out automation for common tasks. Implemented well, this can help vendors break into new customer segments.

We find that, as the problem size increase and approach realistic dimensions, neither the non‐linear nor the linearized version can be solved directly in state‐of‐the‐art commercial optimizers. This is particularly relevant as a large number of scenarios are required to get a stable solution. To overcome this difficulty, we present a heuristic solution approach that relies on Lagrangian decomposition and scenario aggregation. Computational experiments show that this approach identifies optimal or near‐optimal solutions, and takes substantially less time than the optimal approaches.

However, this heuristic also requires considerable computational time to find good solutions when the network is sparse and the variability in the problem parameters is low. We tackle this by simplifying the problem into a homogeneous one and solving for the number of features to include in the demo analytically. The insights gained from the analytical model are used to identify the tasks that contribute to the signal. Fixing these tasks reduces the size of the integer program, which can then be solved quickly using standard optimizers. We provide a comparative table to guide vendors on the solution approach to take, given their specific context.

The formulations and solution approaches presented in this study can easily be extended into a context where multiple segments of customers exist—the vendor can either create a single demo across all customer segments, or segment‐specific demos for each segment. The vendor can use the ideas presented in this study to estimate the expected value of identifying the segment to which each customer belongs. This provides the vendor with an estimate of how much they should be willing to spend to identify the customers precisely.

Footnotes

Vendor's Problem: Proof of NP‐completeness

The Scenario Aggregation Algorithm

Proof of Proposition 2

1

http://www.salesforce.com/crm/editions-pricing.jsp.

2

http://www.sap.com/pc/tech/cloud/software/productstewardship-network/pricing.html.

3

discuss.joelonsoftware.com/default.asp?biz.5.499021.12.

4

A deterministic equivalent of a stochastic program is a deterministic model that incorporates in it every possible scenario.

References

Bala

Carr

. 2009. Pricing software upgrades: The role of product improvement and user costs. Prod. Oper. Manag. 18(5): 560–580.

Chellappa

Shivendu

. 2005. Managing piracy: Pricing and sampling strategies for digital experience goods in vertically segmented markets. Inf. Syst. Res. 16(4): 400–417.

Cheng

Liu

. 2015. Optimal software free trial strategy: Limited version, time‐locked, or hybrid? Prod. Oper. Manag. 24(3): 504–517.

CPLEX . 2011. IBM ILOG CPLEX VOptimization Studio: CPLEX User's Manual Version 12 Release 4. IBM.

Froberg

2015. Analytical model. Available at http://www.freemium.org/analytical-model/ (accessed date June 26, 2016).

Glockner

Nemhauser

Tovey

. 2001. Dynamic network flow with uncertain arc capacities: Decomposition algorithm and computational results. Comput. Optim. Appl. 18(3): 233–250.

Guignard

Kim

. 1987. Lagrangean decomposition: A model yielding stronger lagrangean bounds. Math. Program. 39(2): 215–228.

Heiman

Muller

. 1996. Using demonstration to increase new product acceptance: Controlling demonstration time. J. Mark. Res. 33(4): 422–430.

Ilan

2001. The economics of software distribution over the internet revisited. Available at http://www.firstmonday.org/ojs/index.php/fm/article/view/905/814 (accessed date June 26, 2016).

10.

Jönsson

Jörnsten

Silver

. 1993. Application of the scenario aggregation approach to a two‐stage, stochastic, common component, inventory problem with a budget constraint. Eur. J. Oper. Res. 68(2): 196–211.

11.

Kreps

1990. A Course in Microeconomic Theory. Princeton University Press, Princeton, NJ.

12.

Lee

Kumar

Gupta

. 2013. Designing freemium: A model of consumer usage, upgrade, and referral dynamics. Diss., Harvard Business School.

13.

Lewis

T. R.

Sappington

D. E. M.

. 1994. Supplying information to facilitate price discrimination. Int. Econ. Rev. 35(2): 309–327.

14.

Gery

. 2000. E‐tailing—For all products? Bus. Horiz. 43(6): 49–54.

15.

Margot

2009. Symmetry in integer linear programming. Jünger

Liebling

Th. M.

Naddef

Nemhauser

G. L.

Pulleyblank

W. R.

Rinaldi

Wolsey

L. A.

, eds. 50 Years of Integer Programming: 1958–2008. Springer, Berlin, Heidelberg, 647–686.

16.

Mehra

Seidmann

Mojumder

. 2014. Product life‐cycle management of packaged software. Prod. Oper. Manag. 23(3): 366–378.

17.

Nelson

1970. Information and consumer behavior. J. Polit. Econ. 78(2): 311–329.

18.

Niculescu

M. F.

D. J.

. 2014. Economics of free under perpetual licensing: Implications for the software industry. Inf. Syst. Res. 25(1): 173–199.

19.

Oracle . 2012. PeopleSoft Interaction Hub: Rebranding And Licensing for PeopleSoft Portal. Available at https://blogs.oracle.com/peopletools/resource/PIH%20data%20sheet-publish_Sept12.pdf (accessed date June 26, 2016).

20.

PeopleTools . 2013. PeopleTools 8.53 Cumulative Features Overview. Available at https://myshare.in.gov/SBA/encompass/Shared%20Documents/Forms/AllItems.aspx?RootFolder=%2FSBA%2Fencompass%2FShared%20Documents%2FPeopleSoft%20Enterprise%20Release%20Notes%2FPeopleTools%208%2E53&FolderCTID=0x012000BCB1AAB4C101E043ACA92C4E2CAF12AC&View={F028AA1A-92F6-481F-AD3C-A6A404494279} (accessed date June 26, 2016).

21.

Puchinger

Raidl

Pferschy

. 2010. The multidimensional knapsack problem: Structure and algorithms. Informs J. Comput. 22(2): 250–265.

22.

Roberts

Urban

. 1988. Modeling multiattribute utility, risk and belief dynamics for new consumer durable brand choice. Management Sci. 34(2): 167–185.

23.

Rockafellar

Wets

. 1991. Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1): 119–147.

24.

Sahinidis

N. V.

1996. Baron: A general purpose global optimization software package. J. Global Optim. 8(2): 201–205.

25.

Semenzin

Meulendijks

Seele

Wagner

Brinkkemper

. 2012. Differentiation in Freemium: Where Does the Line Lie? M. A. Cusumano, B. Iyer, N. Venkatraman, eds. Software Business. Springer‐Verlag, Berlin, Heidelberg, 291–296.

26.

Seufert

E. B.

2013. Freemium Economics: Leveraging Analytics and User Segmentation to Drive Revenue. Elsevier, Boston, MA.

27.

Shapiro

1983. Optimal pricing of experience goods. Bell J. Econ. 14(2): 497–507.

28.

Wang

C. A.

Zhang

X. M.

. 2009. Sampling of information goods. Decis. Support Syst. 48(1): 14–22.

29.

Wei

X. D.

Nault

B. R.

. 2014. Monopoly versioning of information goods when consumers have group tastes. Prod. Oper. Manag. 23(6): 1067–1081.