6
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 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

0

Reset to default

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.