![\"Open](\"https://colab.research.google.com/assets/colab-badge.svg\" "\\"Open"){kind=icon}
![\"Download\"](\"https://img.shields.io/badge/Github-Download-blue.svg\" "\\"Download"){kind=icon}
"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 1,
"link": "[5.2 Linear Blending Problems](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2-Linear-Blending-Problems)",
"section": "5.2 Linear Blending Problems"
}
},
"source": [
"# 5.2 Linear Blending Problems\n",
"\n",
"This notebook introduces simple material blending problems, and outlines a multi-step procedure for creating and solving models for these problems using CVXPY."
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.1 Learning Goals](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.1-Learning-Goals)",
"section": "5.2.1 Learning Goals"
}
},
"source": [
"### 5.2.1 Learning Goals\n",
"\n",
"* Linear Blending problems\n",
" * Frequently encountered in material blending \n",
" * Models generally consist of linear mixing rules and mass/material balances\n",
" * Decision variables are indexed by a set of raw materials\n",
"\n",
"\n",
"* Further practice with key elements of modeling for optimization\n",
" * cvxpy.Variable(): Create instance of an optimization **decision variable**\n",
" * cvxpy.Minimize()/cvxpy.Maximize(): Create instance of an **optimization objective**\n",
" * cvxpy.Problem(): Create instance of an optimization problem with objective and **constraints**.\n",
" \n",
" \n",
"* Modeling and solving linear blending problems in CVXPY\n",
" * Step 1. Coding problem data. Nested dictionaries or Pandas dataframes.\n",
" * Step 2. Create index set. Use .keys() with nested dictionaries, or .index with Pandas dataframes.\n",
" * Step 3. Create a dictionary of decision variables. Add any pertinent qualifiers or constraints for individual variables such as lower and upper bounds, non-negativity, variable names.\n",
" * Step 4. Create an expression defining the problem objective.\n",
" * Step 5. Create a one or more lists of problem constraints.\n",
" * Step 6. Create the problem object from the objectives and constraints.\n",
" * Step 7. Solve and display the solution."
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 2,
"link": "[5.2.1 Problem Statement (Jenchura, 2017)](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.1-Problem-Statement-(Jenchura,-2017))",
"section": "5.2.1 Problem Statement (Jenchura, 2017)"
}
},
"source": [
"## 5.2.1 Problem Statement (Jenchura, 2017)\n",
"\n",
"A brewery receives an order for 100 gallons that is at least 4% ABV (alchohol by volume) beer. The brewery has on hand beer A that is 4.5% ABV and costs \\\\$0.32 per gallon to make, and beer B that is 3.7% ABV and costs \\\\$0.25 per gallon. Water (W) can also be used as a blending agent at a cost of \\\\$0.05 per gallon. Find the minimum cost blend of A, B, and W that meets the customer requirements."
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 2,
"link": "[5.2.2 Solving optimization problems with CVXPY](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2-Solving-optimization-problems-with-CVXPY)",
"section": "5.2.2 Solving optimization problems with CVXPY"
}
},
"source": [
"## 5.2.2 Solving optimization problems with CVXPY\n",
"\n",
"The blending problem described above is relatively simple, it can be solved in CVXPY using no more than `cp.Variable()`, `cp.Minimize()`, and `cp.Problem()` as demonstrated below."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"nbpages": {
"level": 2,
"link": "[5.2.2 Solving optimization problems with CVXPY](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2-Solving-optimization-problems-with-CVXPY)",
"section": "5.2.2 Solving optimization problems with CVXPY"
}
},
"outputs": [],
"source": [
"import numpy as np\n",
"import cvxpy as cp"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.1 Step 1. Coding Problem Data as a Python Dictionary](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.1-Step-1.-Coding-Problem-Data-as-a-Python-Dictionary)",
"section": "5.2.2.1 Step 1. Coding Problem Data as a Python Dictionary"
}
},
"source": [
"### 5.2.2.1 Step 1. Coding Problem Data as a Python Dictionary\n",
"\n",
"The first step is to represent the problem data in a generic manner that could be extended to include additional blending components. Here we use a dictionary of raw materials, each key denoting a unique blending agent. For each key there is a second level dictionary containing attributes of the blending component. This nested \"dictionary of dictionaries\" organization is a useful of organizing tabular data for optimization problems."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.1 Step 1. Coding Problem Data as a Python Dictionary](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.1-Step-1.-Coding-Problem-Data-as-a-Python-Dictionary)",
"section": "5.2.2.1 Step 1. Coding Problem Data as a Python Dictionary"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'A': {'abv': 0.045, 'cost': 0.32}, 'B': {'abv': 0.037, 'cost': 0.25}, 'W': {'abv': 0.0, 'cost': 0.05}}\n"
]
}
],
"source": [
"data = {\n",
" 'A': {'abv': 0.045, 'cost': 0.32},\n",
" 'B': {'abv': 0.037, 'cost': 0.25},\n",
" 'W': {'abv': 0.000, 'cost': 0.05},\n",
"}\n",
"print(data)"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.2 Step 2. Identifying index sets](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.2-Step-2.-Identifying-index-sets)",
"section": "5.2.2.2 Step 2. Identifying index sets"
}
},
"source": [
"### 5.2.2.2 Step 2. Identifying index sets\n",
"\n",
"The objectives and constraints encountered in optimization problems often include sums over a set of objects. In the case, we will need to create sums over the set of raw materials in the blending problem."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.2 Step 2. Identifying index sets](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.2-Step-2.-Identifying-index-sets)",
"section": "5.2.2.2 Step 2. Identifying index sets"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'A', 'B', 'W'}\n"
]
}
],
"source": [
"components = set(data.keys())\n",
"print(components)"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.3 Step 3. Create decision variables](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.3-Step-3.-Create-decision-variables)",
"section": "5.2.2.3 Step 3. Create decision variables"
}
},
"source": [
"### 5.2.2.3 Step 3. Create decision variables"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.3 Step 3. Create decision variables](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.3-Step-3.-Create-decision-variables)",
"section": "5.2.2.3 Step 3. Create decision variables"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'A': Variable((), nonneg=True), 'B': Variable((), nonneg=True), 'W': Variable((), nonneg=True)}\n"
]
}
],
"source": [
"x = {c: cp.Variable(nonneg=True) for c in components}\n",
"print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.4 Step 4. Objective Function](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.4-Step-4.-Objective-Function)",
"section": "5.2.2.4 Step 4. Objective Function"
}
},
"source": [
"### 5.2.2.4 Step 4. Objective Function\n",
"\n",
"If we let subscript $c$ denote a blending component from the set of blending components $C$, and denote the volume of $c$ used in the blend as $x_c$, the cost of the blend is\n",
"\n",
"\\begin{align}\n",
"\\mbox{cost} & = \\sum_{c\\in C} x_c P_c\n",
"\\end{align}\n",
"\n",
"where $P_c$ is the price per unit volume of $c$. Using the Python data dictionary defined above, the price $P_c$ is given by `data[c]['cost']`."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.4 Step 4. Objective Function](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.4-Step-4.-Objective-Function)",
"section": "5.2.2.4 Step 4. Objective Function"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"minimize var0 @ 0.32 + var1 @ 0.25 + var2 @ 0.05\n"
]
}
],
"source": [
"total_cost = sum(x[c]*data[c][\"cost\"] for c in components)\n",
"objective = cp.Minimize(total_cost)\n",
"print(objective)"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.5 Step 5. Constraints](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5-Step-5.-Constraints)",
"section": "5.2.2.5 Step 5. Constraints"
}
},
"source": [
"### 5.2.2.5 Step 5. Constraints"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.2.5 Step 5. Constraints](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5-Step-5.-Constraints)",
"section": "5.2.2.5 Step 5. Constraints"
}
},
"outputs": [],
"source": [
"volume = 100\n",
"abv = 0.040"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.1 Volume Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.1-Volume-Constraint)",
"section": "5.2.2.5.1 Volume Constraint"
}
},
"source": [
"#### 5.2.2.5.1 Volume Constraint\n",
"\n",
"The customer requirement is produce a total volume $V$. Assuming ideal solutions, the constraint is given by\n",
"\n",
"\\begin{align}\n",
"V & = \\sum_{c\\in C} x_c\n",
"\\end{align}\n",
"\n",
"where $x_c$ denotes the volume of component $c$ used in the blend."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.1 Volume Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.1-Volume-Constraint)",
"section": "5.2.2.5.1 Volume Constraint"
}
},
"outputs": [],
"source": [
"constraints = [volume == sum(x[c] for c in components)]"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.2 Product Composition Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.2-Product-Composition-Constraint)",
"section": "5.2.2.5.2 Product Composition Constraint"
}
},
"source": [
"#### 5.2.2.5.2 Product Composition Constraint\n",
"\n",
"The product composition is specified as requiring at least 4% alchohol by volume. Denoting the specification as $\\bar{A}$, the constraint may be written as\n",
"\n",
"\\begin{align}\n",
"\\bar{A} & \\leq \\frac{\\sum_{c\\in C}x_c A_c}{\\sum_{c\\in C} x_c}\n",
"\\end{align}\n",
"\n",
"where $A_c$ is the alcohol by volume for component $c$. As written, this is a nonlinear constraint. Multiplying both sides of the equation by the denominator yields a linear constraint\n",
"\n",
"\\begin{align}\n",
"\\bar{A}\\sum_{c\\in C} x_c & \\leq \\sum_{c\\in C}x_c A_c\n",
"\\end{align}\n",
"\n",
"A final form for this constraint can be given in either of two versions. In the first version we subtract the left-hand side from the right to give\n",
"\n",
"\\begin{align}\n",
"0 & \\leq \\sum_{c\\in C}x_c \\left(A_c - \\bar{A}\\right) & \\mbox{ Version 1 of the linear blending constraint}\n",
"\\end{align}\n",
"\n",
"Alternatively, the summation on the left-hand side corresponds to total volume. Since that is known as part of the problem specification, the blending constraint could also be written as\n",
"\n",
"\\begin{align}\n",
"\\bar{A}V & \\leq \\sum_{c\\in C}x_c A_c & \\mbox{ Version 2 of the linear blending constraint}\n",
"\\end{align}\n",
"\n",
"Which should you use? Normally either will work well. The advantage of version 1 is that it is fully specified by a single product requirement $\\bar{A}$, and doesn't require knowledge of the other product requirement $V$. This may be helpful in writing elegant Python code."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.2 Product Composition Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.2-Product-Composition-Constraint)",
"section": "5.2.2.5.2 Product Composition Constraint"
}
},
"outputs": [],
"source": [
"constraints.append(0 <= sum(x[c]*(data[c]['abv'] - abv) for c in components))"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.2 Product Composition Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.2-Product-Composition-Constraint)",
"section": "5.2.2.5.2 Product Composition Constraint"
}
},
"source": [
"We can review the constraints by printing them out. If no name is specified for a decision variable when it is created, then cvxpy will assign a name beginiing with `var`. "
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.2 Product Composition Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.2-Product-Composition-Constraint)",
"section": "5.2.2.5.2 Product Composition Constraint"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"var0 + var1 + var2 == 100.0\n",
"0.0 <= var0 @ 0.0049999999999999975 + var1 @ -0.0030000000000000027 + var2 @ -0.04\n"
]
}
],
"source": [
"for constraint in constraints:\n",
" print(constraint)"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbpages": {
"level": 4,
"link": "[5.2.2.5.2 Product Composition Constraint](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.2.5.2-Product-Composition-Constraint)",
"section": "5.2.2.5.2 Product Composition Constraint"
}
},
"source": [
"
"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"nbpages": {
"level": 3,
"link": "[5.2.3.2 Optimal blend as a function of product specification](https://jckantor.github.io/cbe30338-2021/05.02-Linear-Blending-Problem.html#5.2.3.2-Optimal-blend-as-a-function-of-product-specification)",
"section": "5.2.3.2 Optimal blend as a function of product specification"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A,Y\n",
"A,X\n",
"W,Y\n",
"W,X\n",
"C,Y\n",
"C,X\n",
"B,Y\n",
"B,X\n",
"A,Y @ 0.32 + A,X @ 0.32 + W,Y @ 0.05 + W,X @ 0.05 + C,Y @ 0.28 + C,X @ 0.28 + B,Y @ 0.25 + B,X @ 0.25\n"
]
},
{
"ename": "KeyError",
"evalue": "'A'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mKeyError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}