I'm working on a price-selection model where we need to identify price point for each time-period (could be day/week). Objective of the model is to figure out optimal price-point for each time-point to optimize revenue from all products. One price-point selected applies to all products $$ \begin{align*} &\mathcal{P} \quad \text{set of products (indexed by $p$)}\\ &\mathcal{T} \quad \text{set of time-periods (indexed by $t$)}\\ &\mathcal{K} \quad \text{set of price-points (indexed by $k$)}\\ &D_{p,t,k} \quad \text{demand of product $p$ in time-period $t$ at price-point $k$} \\ &R_{p,t,k} \quad \text{Revenue associated with product $p$ for time-period $t$ at price-point $k$} \\ & \end{align*} $$ Binary variable $z_{t,k}$ equals 1 if price-point $k$ is selected for time-period $t$. As same price applies for all products, objective is to maximize revenue i.e. $$ Maximize \quad \sum_{p,t,k} R_{p,t,k} \cdot q_{p,t,k} $$ Also, main constraint is to identify quantity sold $q_{p,t,k}$ for each product $p$ at time-period $t$ if $k$ price-point is selected and is given by $$ q_{p,t,k} \le D_{p,t,k} \cdot z_{t,k} $$ Only one price point to be selected per time-period $$ \sum_{k} z_{t,k}=1 $$ Total inventory sold is less than initial inventory $I_{p}$ $$ \sum_{t,k} q_{p,t,k} \le I_{p} $$ Also, there are some side constraints on price changes from one time-period to another. With this formulation, while solving as MIP (root-relaxation solve), it shows dense columns in the logs which is leading to high computational time for a larger product case. Snippet of log is provided below:

Barrier statistics:
 Dense cols : 74
 AA' NZ     : 1.509e+06
 Factor NZ  : 8.201e+06 (roughly 400 MBytes of memory)
 Factor Ops : 2.808e+08 (less than 1 second per iteration)
 Threads    : 4

I'm looking for alternate formulation to avoid these dense columns which is primarily caused by inventory constraints.

  • 1
    $\begingroup$ Looks like a good candidate for Benders decomposition with $z$ as the master variables. $\endgroup$
    – RobPratt
    Feb 21, 2022 at 18:36
  • 1
    $\begingroup$ Have you tried not including subscript $k$ on variable $q$? In other words, let $q_{p,t}$ be the amount of $p$ sold at time $t$. The inventory constraint will be sparser, though the demand constraint will be denser (RHS will be a sum). It will reduce your variable count. Whether that's an overall improvement is an empirical question. $\endgroup$
    – prubin
    Feb 21, 2022 at 19:21
  • 1
    $\begingroup$ @prubin How do you avoid the fact that $R$ and $D$ both depend on $p,t,k$? $\endgroup$
    – RobPratt
    Feb 21, 2022 at 20:20
  • 1
    $\begingroup$ @RobPratt Demand is easy: $q_{p,t} \le \sum_k D_{p,t,k} z_{t,k}.$ (This is what I meant by "RHS will be a sum".) Revenue will require a new continuous variable ($w_{p,t,k}$) and constraints $w_{p,t,k} \le R_{p,t,k} q_{p,t}$ and $w_{p,t,k} \le R_{p,t,k}Q z_{t,k}$ (where $Q$ is an upper bound on $q_{p,t}$). The objective is $\sum_{p,t,k} w_{p,t,k}.$ Bad news: more (continuous) variables and constraints. Good news: the extra constraints are sparse. $\endgroup$
    – prubin
    Feb 21, 2022 at 22:35
  • 1
    $\begingroup$ @prubin OK, I thought you were proposing to somehow reduce the variable count. $\endgroup$
    – RobPratt
    Feb 21, 2022 at 23:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.