# Raw Material Purchasing Optimization Using Column Generation
## 3 Method  
### Model  
The real-world RMP problem is from a certain large-scale iron and steel enterprise (below called M-Steel) in China. M-Steel purchases about 15 million tons of raw materials per year with about 4.5 billion of CNY of purchase expenditure and the purchased number of raw material items is over 3000. The total raw materials purchasing cost accounts for more than 70% of the total operating cost of M-Steel. The purchasing cost is composed of the raw materials price, purchasing set-up cost, and inventory cost. The optimization problem is to minimize the sum of the above three costs.  
Assumptions:  
A1: a single period is set as a month; therefore, a one-year length includes 12 periods.  
A2: the inventory of each item of raw materials in each period is known.  
A3: the demand quantity of each item in each period is known.  
The RMP model is as follows:  
\[\min\sum_{i=1}^{N}\sum_{t=1}^{T}\left(p_{it}x_{it}+s_{it}Y_{it}+h_{it}I_{it}\right) \tag{1}\]  
subject to  
\[I_{i,t-1}+x_{it}+I_{it}=d_{it},\;\;i=1,\ldots,N,\;t=1,\ldots,T, \tag{2}\]  
\[x_{it}\leq\;M\Upsilon_{it},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \forall\;i,t, \tag{3}\]  
\[\sum_{i=1}^{N}r_{ki}x_{it}\leq C_{it},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;t=1, \ldots,T;\;k=1,\ldots,K, \tag{4}\]  
\[I_{i0}=0,I_{iT}=0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;i=1, \ldots,N, \tag{5}\]  
satisfies the demands of an integral number of periods for any item. Based on the idea, the RMP model can be reformulated as a set partitioning problem:  
\[\min\sum_{i\in\Gamma}\sum_{j\in\Omega_{i}}b_{ij}\theta_{ij} \tag{7}\]  
subject to  
\[\sum_{j\in\Omega_{i}}\theta_{ij}=\ 1\,\forall\ i\in\Omega \tag{8}\]  
\[\sum_{i\in\Omega}\sum_{j\in\Omega_{i}}R^{k}_{ijt}\ \theta_{ij}\leq C_{kt},\forall\ t,k=1,\ldots,K \tag{9}\]  
\[\theta_{ij}\in\ \{0,\ 1\},\ \forall\ i\in\Omega,j\in\Omega_{i} \tag{10}\]  
where, decision variable \(\theta_{ij}\) is equal to 1 when schedule \(j\) is selected, and 0 otherwise. \(K\) is the number of resources, parameter \(b_{ij}\) is the cost associated with the \(j\)th schedule for item \(i\) and parameter \(R^{k}_{ijt}\) is the \(k\)th resource requirement in period \(t\) for schedule \(j\), and parameter \(C^{k}_{t}\) is the \(k\)th resource capacity available in period \(t\). Let \(x_{ijt}\), \(Y_{jt}\), and \(I_{jt}\) denote the purchasing quantity, purchasing set-up, and inventory variables associated with the schedule \(j\) for item \(i\) in period \(t\), respectively. Consequently, hold  
\[b_{ij}=\sum_{t=1}^{\mathrm{T}}\left(p_{ii}x_{ijt}+s_{ii}Y_{ijt}+t_{ii}I_{ijt}\right) \tag{11}\]  
\[R^{k}_{ijt}=r_{ki}x_{ijt},\ t=1,\ldots,T,\ k=1,2 \tag{12}\]  
In the SP model, the objective function (7) minimizes the total sum of purchasing costs, set-up costs, and inventory holding costs. The partitioning constraint (8) requires that for each item \(i\), only a schedule can be selected. Constraint (9) requires the resource absorption of all schedules not to exceed the capacity of each resource in the period \(t\) available. Constraint (10) indicates the decision variable \(\theta_{ij}\) is a 0-1 variable.  
For the W-W schedules [PERSON] [30] called dominant schedules because there are \(2^{T-1}\) dominant schedules per item \(i\), generating them may be rather time-consuming or impractical and the resulting SP problem is far too large to solve. Therefore, a column generation algorithm is introduced to solve the SP problem, in which not all \(N\):\(2^{T-1}\) of schedules are generated explicitly. Alternatively, many schedules are handled implicitly by column generation techniques [34], and, thus, the large-sized SP problem is effectively resolved.