Large Scale Optimization Models
Large Scale Optimization Models
‘In real applications optimization models quickly grow to thousands, even millions, of variables and constraints.’ [Reference 1] It is not practical to solve these models by hand. Therefore, we need to use computers to solve these models. We need to represent parameters, variables, and constraints using relevant sets. Let’s define a set of variables:
\[ z_{i} \quad \forall i \in I\]
where \(I\) is the set of all values that the index \(i\) can take. The index \(i\) is used to identify each variable. For example, \(z_{1}\) is the first variable, \(z_{2}\) is the second variable, and so on. Appropriate indices should be defined for each distinct dimenstion of a problem. In 2 Crude example, we had two variables \(x_{1}\) and \(x_{2}\). We could define a set of variables to represent many resources instead of just two:
\[ x_{i} \quad \forall i \in I\]
Similarly, we could define a set of cost coefficients to represent costs of many resources instead of just two:
\[ c_{i} \quad \forall i \in I\]
Referring to example 2.8, we can define a set of variables using 4 indices as follows:
\[ w_{i,j,k,l} \quad \forall i \in I, j \in J, k \in K, l \in L\]
Assuming that \(I = \{1,...,100\}\), \(J = \{1,...,100\}\), \(K = \{1,...,50\}\), and \(L = \{1,...,50\}\), there would be 25,000,000 variables in this model.
In linear programming (LP), objective function and constraints are linear. There are expressed as linear combinations of variables. Therefore summation notation is prevelant in LP models. See Example 2.9.
Constraints are also expressed using index notation. See Example 2.10 and 2.11.
‘Pi Hybrids is an example for large scale modeling. A large manufacturer of corn seed, which we will call Pi Hybrids, operates \(l\) facilities producing seeds of \(m\) hybrid corn varieties and distributes them to customers in \(n\) sales regions. They want to know how to carry out these production and distribution operations at minimum cost.’ [Reference 1]. We can define parameters and sets as follows:
We should define sets for facilities, hybrids, and sales regions. It is conventional to represent sets with capital letters. For example, \(F\) is the set of all facilities, \(H\) is the set of all hybrids, and \(R\) is the set of all sales regions. We can define parameters as follows:
\(p_{fh}\): cost per bag of producing hybrid h at facility f where \(f \in F\) and \(h \in H\)
\(s_{fhr}\): cost per bag of shipping hybrid h from facility f to sales region r where \(f \in F\), \(h \in H\), and \(r \in R\)
\(d_{hr}\): demand for hybrid h in sales region r where \(h \in H\) and \(r \in R\)
\(u_f\): capacity of facility f where \(f \in F\)
\(a_h\): number of bushels of corn that must be processed to obtain a bag of hybrid \(h\)
We can define variables as follows:
\(x_{fh}\): number of bags of hybrid h produced at facility f where \(f \in F\) and \(h \in H\)
\(y_{fhr}\): number of bags of hybrid h shipped from facility f to sales region r where \(f \in F\), \(h \in H\), and \(r \in R\)
Objective function and constraints can be expressed using these parameters, sets, and variables.
Objective function is expressed as:
\[ \min \sum_{f \in F} \sum_{h \in H} p_{fh}x_{fh} + \sum_{f \in F} \sum_{h \in H} \sum_{r \in R} s_{fhr}y_{fhr}\]
(capacity constraints)
\[ \sum_{h \in H} a_{h}x_{fh} \leq u_{f} \quad \forall f \in F\]
(demand constraints)
\[ \sum_{f \in F} y_{fhr} = d_{hr} \quad \forall h \in H, r \in R\]
(production balance constraints)
\[ \sum_{f \in F} y_{fhr} = x_{fh} \quad \forall f \in F, h \in H\]
(nonnegativity constraints)
\[ x_{fh} \geq 0 \quad \forall f \in F, h \in H\]
\[ y_{fhr} \geq 0 \quad \forall f \in F, h \in H, r \in R\]
Please refer to the colab notebook below (also included in the Black Board) to practice how to model and solve this model. Production planning notebook is also available in the same folder as this notebook.
References
1: Optimization in OR textbook by R. Rardin