# Issue of Dense columns in the formulation

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)

• Looks like a good candidate for Benders decomposition with $z$ as the master variables. Feb 21, 2022 at 18:36
• 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.
• @prubin How do you avoid the fact that $R$ and $D$ both depend on $p,t,k$? Feb 21, 2022 at 20:20
• @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.