Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context.

Advertizing Budget Allocation Instances

We consider an advertising budget allocation problem introduced by Zoltners and Sinha. In this problem, a company is required to allocate an advertising budget $D$ among a set $mathcal{K}$ of advertising strategies for a set of $mathcal{J}$ products. The return on investment functions are approximated using a piecewise linear function with n breakpoints (n-1 pieces). We created 20 random instances for each of the six problem sizes ($mathcal{J}$, $mathcal{K}$, n) ∈ {(50, 50, 10), (50, 100, 10), (100,100,10), (50,50,20), (50,100,20), (100,100,20)}.

model_J_K_t_n_rep

where

model refers to the piecewise linear formulation use. sos and nt_sos are two variants of a specially ordered set based formulation (see paper for details). Instances with the tag sos refer to formulation S1 in the paper while nt_sos refers to formulation S2 in the paper.
J is the number of customers.
K is the number of marketing strategies.
t is the roi function type. All instances are of s-shaped roi curves and are denoted by type 1.
n is the number of pieces used in the approximation of the nonlinear roi function.
rep is the id of the random instance of that category (there are 20 per category).

Individual Instances

Formulations with a tag S2 are locally ideal while S1 are not. Both S1 and S2 refer to the same underlying model and should hence produce the same MIP solution.