Alternate formulation for modeling inventory constraints

Question

I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-20 time-periods and 10-15 price buckets. Inventory consumed at a time-period (t) is minimum of available inventory and demand (which is dependent on price bucket selected). This particular constraint is making problem harder (not able to obtain optimal solution even in 30 mins for above scale using commercial solver) and my current modeling is shown below:

$$ \begin{align*} &\mathcal{I} \quad \text{set of items (indexed by $i$)}\\ &\mathcal{T} \quad \text{set of time-periods (indexed by $t$)}\\ &\mathcal{K} \quad \text{set of price-buckets (indexed by $k$)}\\ &D_{i,t,k} \quad \text{demand of item $i$ for time-period $t$ at price-bucket $k$} \\ &z_{i,t,k} \quad \text{binary variable takes value 1 if $k^{th}$ price-bucket is selected for item-i for time-period $t$} \end{align*} $$ As mentioned above, Inventory catered ($q_{i,t}^{supplied}$) at time-period $t$ is computed as minimum of available inventory ($q_{i,t}$) and posed demand ($\sum_{k}D_{i,t,k} \cdot z_{i,t,k}$). Linearization of this is achieved by following constraints. $$ \begin{align} q_{i,t}^{supplied} &\le q_{i,t} \\ q_{i,t}^{supplied} &\le \sum_{k}D_{i,t,k} \cdot z_{i,t,k} \\ q_{i,t}^{supplied} &\ge q_{i,t} - M^{big} \cdot \delta_{i,t} \\ q_{i,t}^{supplied} &\ge \sum_{k}D_{i,t,k} \cdot z_{i,t,k} - M^{big} \cdot (1-\delta_{i,t}) \end{align} $$ where $\delta_{i,t}$ is a binary variable. Big-M's are chosen as tight as possible. These set of constraints are taking time while solving. Please suggest for any possible alternate formulation to achieve this or any references would be helpful.

Answer 1

If, given inventory level ($q_{i,t}$) and bucket decisions ($z_{i,t,k}$), profit is maximized by maximizing the supplied quantities, you probably can drop the big M constraints and trust the objective to prevent selection of a supplied quantity less than the min of the two upper limits. As an experiment, you could try running without those constraints and see if in fact the solution satisfied the min constraints.

Otherwise, I'm not sure there is a better formulation. You could try combinatorial Benders cuts [1] in lieu of the big M constraints, but I'm not sure that would be faster (particularly if your values of M are fairly tight), and you likely would want a solver that supported user callbacks. Another possible reformulation would be to introduce new continuous variables $w_{i,t,k}\in [0,1]$ along with the constraints \begin{align*} w_{i,t,k} & \le z_{i,t,k}\\ w_{i,t,k} & \le \delta_{i,t}\\ w_{i,t,k} & \ge z_{i,t,k}+\delta_{i,t}-1. \end{align*} Collectively, those constraints force $w_{i,t,k}=z_{i,t,k}\delta_{i,t}$. You can now replace your fourth constraints with $$q_{i,t}^{supplied} \ge \sum_{k}D_{i,t,k} w_{i,t,k}.$$ That eliminates half the big M constraints, but still leaves the other half. (I'm assuming that available inventory $q_{i,t}$ is a variable and not a parameter.)

[1] Codato, G. and Fischetti, M. (2006) Combinatorial Benders' Cuts for Mixed-Integer Linear Programming. Operations Research, Vol. 54(4), pp. 756-766.