\(\newcommand{\R}{{\mathbb{R}}}\) \(\newcommand{\Z}{{\mathbb{Z}}}\) \(\newcommand{\N}{{\mathbb{N}}}\) \(\newcommand{\var}[1]{{\color{red}{\mathbf{#1}}}}\) \(\newcommand{\param}[1]{{\color{blue}{#1}}}\) \(\newcommand{\mathsc}[1]{{\normalfont\textsc{#1}}}\) \(\def\sc#1{\dosc#1\csod}\) \(\def\dosc#1#2\csod{{\rm{#1{\rm\small #2}}}}\) \(\newcommand{\set}[1]{{\sc#1}}\) \(\newcommand{\mathvar}[1]{\var{#1}}\) \(\newcommand{\mathpar}[1]{\param{#1}}\) \(\newcommand{\half}{{\small{\frac{1}{2}}}}\)

# 2. Structured linear optimization models¶

This chapter is devoted to the introduction of some classes of linear optimization problems with a special “structure”. Before starting with quite a large number of special models, let us introduce the basic terminology first. All of the optimization models we will be presenting can be represented as constrained optimization models in \(\R^n\):

Here \(\var{x}\) is the vector of decision variables; the set \(S\) is the feasible set, while \(f: \R^n\rightarrow \R\) is called objective function. In a linear model, the objective function is linear, which, in finite Euclidean spaces, is equivalent to say that

there exist real coefficients \(c \in \R^n\) such that

\begin{align*} f(\var{x}) & = \sum_{j=1}^n c_j \var{x}_j \end{align*}the feasible set is a polyhedron, or, equivalently, that there exist matrices \(A, B\) and vectors \(\alpha, \beta\) such that the set \(S\) is composed by the solutions of the system of liner equations and inequalities

\begin{align*} A \var{x} & = \alpha \\ B \var{x} & \leq \beta \end{align*}

Thus, in a *linear model* both the objective function and the left
hand sides of all equalties and inequalities are linear expressions.

By the therm *structured models* we mean that
these models can be seen as special cases of generic linear optimization ones,
whose structure from one side identifies a class of potentially useful
applications and, on another side, lends itself to further theoretical
analysis; this, in some cases, might lead to improved numerical
performance. By a “structure” we usually mean a set of constraints
with a special form (like, as we will see later, *balance equations*) or
families of constraints with a special meaning in the applied context,
like blending or resource consumption.

An important class of such structured problems is that of Network flow models, which will be the subject of a detailed analysis later on; being able to identify and exploit the fact that a model is indeed a network flow one allows to get significantly greater insight as well as opens the way towards very efficient optimization algorithms.

Before starting a review of some of the main mathematical optimization models and their applications, we introduce here a fairly simple model connected to the production of aluminum from available scrap. This is indeed an instance of a class of models, called Blending Models which will be described in more detail later. It seems useful to start the presentation with this simple case, the description of which is sufficiently elementary to be understood even without deeper knowledge; its formulation contains the main elements of more complex models. Moreover, although elementary, this model is currently in use at several companies.

- application:
Blending aluminum scrap

One of the industrial sectors in which optimization models are widely used is that of mixing different scrap to produce aluminum alloys of a prescribed quality. Consider the situation in which we may buy, in limited amounts, some scrap mostly composed of aluminum, but containing also other chemical elements; we would like to mix some of these scraps in order to obtain, through casting, an alloy with a prescribed percentage of various chemical elements. We can also consider the case in which, in order to improve the quality of the available scrap, it is possible to purchase pure metals, without any limit, although at a significantly higher price. The problem thus becomes that of establishing the quantities to buy for each scrap and pure metal to be used in a blend of minimum total cost which satisfies quality constraints.

The following table shows a data file prepared according to the syntax of AMPL, JuMP and Pyomo for a hypothetical problem of aluminum blending from scrap. The objective is to obtain a blend which satisfies a set of quality specifications, does not use more scrap than available, and produces the required quantity of finished product at minimum total cost.

# optimal blending of Al scrap set MATERIALS := UBC MixedAuto Radiator WireScraps MixedTurnings LithoSheets Si Mg; set ELEMENTS := Si Mg Fe Cu Mn Zn; param required := 1500; # kg param: minReq maxReq := Si 0.4 0.8 Mg 0.8 1.2 Fe 0. 0.7 Cu 0.15 0.4 Mn 0.0 0.15 Zn 0.0 0.25 ; param compos: UBC MixedAuto Radiator WireScraps MixedTurnings LithoSheets Si Mg:= Si 0.225 10.125 0. 0.1875 6.75 0.6 100. 0. Mg 0.975 0.225 0. 0.45 0.225 0. 0. 100. Fe 0.375 0.825 0.525 0.3 0.75 0.6375 0. 0. Cu 0.15 2.625 30.0 0.0375 2.625 0.125 0. 0. Mn 0.825 0.375 0. 0.0375 0.375 0.6375 0. 0. Zn 0.0375 0.9 0. 0.0525 1.125 0.075 0. 0. ; # cost in Euro per kg param: cost avail := UBC 1.25 1000 MixedAuto 1.4 1000 Radiator 1.35 1500 WireScraps 0.8 1200 MixedTurnings 0.6 1000 LithoSheets 1.2 1600 Si 10. 2000 Mg 10. 2000 ;# optimal blending of Al scrap MATERIALS = ["UBC", "MixedAuto", "Radiator", "WireScraps", "MixedTurnings", "LithoSheets", "Si", "Mg"] ELEMENTS = ["Si", "Mg", "Fe", "Cu", "Mn", "Zn"] required = 1500 # kg bounds = JuMP.Containers.DenseAxisArray( [0.4 0.8; 0.8 1.2; 0. 0.8; 0.15 0.4; 0.0 0.15; 0.0 0.25], ELEMENTS, ["minReq", "maxReq"]) compos = JuMP.Containers.DenseAxisArray( # UBC MixedAuto Radiator WireScraps MixedTurnings LithoSheets Si Mg:= [0.225 10.125 0. 0.1875 6.75 0.6 100. 0.; 0.975 0.225 0. 0.45 0.225 0. 0. 100.; 0.375 0.825 0.525 0.3 0.75 0.6375 0. 0.; 0.15 2.625 30. 0.0375 2.625 0.125 0. 0.; 0.825 0.375 0. 0.0375 0.375 0.6375 0. 0.; 0.0375 0.9 0. 0.0525 1.125 0.075 0. 0.], ELEMENTS, MATERIALS) scrapdata = JuMP.Containers.DenseAxisArray( # cost in Euro per kg [ 1.25 1000; 1.4 1000; 1.35 1500; 0.8 1200; 0.6 1000; 1.2 1600; 10. 2000; 10. 2000 ], MATERIALS, ["cost", "avail"])# optimal blending of Al scrap set MATERIALS := UBC MixedAuto Radiator WireScraps MixedTurnings LithoSheets Si Mg; set ELEMENTS := Si Mg Fe Cu Mn Zn; param required := 1500; # kg param: minReq maxReq := Si 0.4 0.8 Mg 0.8 1.2 Fe 0. 0.7 Cu 0.15 0.4 Mn 0.0 0.15 Zn 0.0 0.25 ; param compos: UBC MixedAuto Radiator WireScraps MixedTurnings LithoSheets Si Mg:= Si 0.225 10.125 0. 0.1875 6.75 0.6 100. 0. Mg 0.975 0.225 0. 0.45 0.225 0. 0. 100. Fe 0.375 0.825 0.525 0.3 0.75 0.6375 0. 0. Cu 0.15 2.625 30.0 0.0375 2.625 0.125 0. 0. Mn 0.825 0.375 0. 0.0375 0.375 0.6375 0. 0. Zn 0.0375 0.9 0. 0.0525 1.125 0.075 0. 0. ; # cost in Euro per kg param: cost avail := UBC 1.25 1000 MixedAuto 1.4 1000 Radiator 1.35 1500 WireScraps 0.8 1200 MixedTurnings 0.6 1000 LithoSheets 1.2 1600 Si 10. 2000 Mg 10. 2000 ;The first part of the data file contains the definition of the names of the available materials and the chemical elements of interest. Than we specify the total required quantity to be produced (in kg) and, for each chemical element, the value of the minimum and maximum percentage required, based on the definition of the “6061” blend type specification. The syntax of this part reflects one of the many ways data can be defined – here we are using a multi–dimensional array whose rows have symbolic names (the names of the chemical elements) and the columns represent, for each chemical element, the minimum and maximum allowed contents in the blend. Next, the data file contains the definition of the chemical composition of each scrap type; again, we are using the same syntax (although modeling languages allow for different ways to obtain a similar data specification) and we define a matrix,

`compos`

, whose rows are associated to chemical elements, whose columns correspond to different scrap materials and whose elements are the (average) percentage contents of that chemical in one unit of that material. Finally, for each material, the cost in Euros per kg and the maximum available quantity are reported. Of course, while these data is quite realistic, the reported numbers have no relations with real life situations.It is worth observing that the main chemical component, aluminum, is not included in this dataset: this means that we can consider that the aluminum content in each material is what remains to reach 100%. As an example, for material

`UBC`

summing the first column in the`compos`

matrix we obtain 0.025875 and we can assume that the aluminum contents is 97.4125%.To formalize the problem we need to identify decision variables, constraints, objective function. It is very natural to associate a variable \(\var{x}_{j}\) to each material \(j\) (in the model this variable is called

`Buy`

); although not necessary, it seems useful to introduce another variable, \(\var{y}_i\), for the total chemical contents of the resulting blend (in the model this is called`Chem`

). Notice that while in the text we prefer to use classical mathematical notation and naming conventions, in the implemented models we preferred to use more meaningful variable names.In the declaration of both variables, we include lower and upper bounds. For the main variable, \(\var{x}\), these are zero and the available quantity, respectively. For what concerns chemical contents, they are the minimum and maximum allowed contents for each element.

The constraint on the total quantity to be produced is simply

\begin{align*} \sum_{j \in \set{Materials}} \var{x}_{j} = \param{required} \end{align*}For what concerns the chemical balance, having introduced a specific variable, we just need to “define” this variable through a set of constraints:

\begin{align*} \var{y}_i & = \sum_{j \in \set{Materials}} \param{compos}_{ij} \var{x}_j / \param{required} \end{align*}It is easy to see how we might get rid of the additional variables \(\var{y}\) by simply redefining the lower and upper bound constraints on the quality as

\begin{align*} \param{minReq}_i \leq \sum_{j \in \set{Materials}} \param{compos}_{ij} \var{x}_j / \param{required} \leq \param{maxReq}_i \end{align*}for all \(i \in \set{ELEMENTS}\).

The objective function, given a unit cost \(\param{cost}_{j}\) associated with each material, can be expressed as

\begin{align*} \min \sum_{j \in \set{Materials}} \param{cost}_{j} \var{x}_{j} \end{align*}In summary, the complete blending model has the following form:

\begin{align*} \min_{\var{x},\var{y}} \sum_{j \in \set{Materials}} \param{cost}_{j}\, \var{x}_{j} & \\ \sum_{j \in \set{Materials}} \var{x}_{j} &= \param{required} \\ \var{y}_i & = \sum_{j \in \set{Materials}} \param{compos}_{ij} \var{x}_j / \param{required} & \forall\, i& \in \set{ELEMENTS} \\ 0 \leq \var{x}_j & \leq \param{avail}_j & \forall\, j &\in \set{MATERIALS}\\ \param{minReq}_i \leq \var{y}_i & \leq \param{maxReq}_i &\forall\, i& \in \set{ELEMENTS} \end{align*}The model can be implemented as reported in the following, where the strong similarity between the abstract model above and its implementation can be easily seen.

#------------------------------------------------------# # optimal scrap bleding problem # #------------------------------------------------------# set MATERIALS; set ELEMENTS; param required; # required quantity param minReq{ELEMENTS}; param maxReq{ELEMENTS}; param compos{ELEMENTS,MATERIALS}; param cost{MATERIALS}; param avail{MATERIALS}; # -----------------------------------------------------# # variable declaration and bounding # -----------------------------------------------------# var Buy{m in MATERIALS} >=0, <= avail[m]; var Chem{el in ELEMENTS} >= minReq[el], <= maxReq[el]; # -----------------------------------------------------# # objective function # -----------------------------------------------------# minimize totalcost: sum {m in MATERIALS} cost[m] * Buy[m]; # -----------------------------------------------------# # constraints # -----------------------------------------------------# s.t. chem_def{el in ELEMENTS}: Chem[el] = sum{m in MATERIALS} compos[el,m] * Buy[m] / required; s.t. total: sum{m in MATERIALS} Buy[m] == required;#------------------------------------------------------# # optimal scrap bleding problem # #------------------------------------------------------# function blend_model(model::Model, datafile::String) include(datafile) # -----------------------------------------------------# # variable declaration and bounding # -----------------------------------------------------# @variable(model, 0 <= Buy[m in MATERIALS] <= scrapdata[m,"avail"]) @variable(model,bounds[el,"minReq"] <= Chem[el in ELEMENTS] <= bounds[el,"maxReq"]) # -----------------------------------------------------# # objective function # -----------------------------------------------------# @objective(model,Min,sum(scrapdata[m,"cost"] * Buy[m] for m in MATERIALS)) # -----------------------------------------------------# # constraints # -----------------------------------------------------# @constraint(model, chem_def[el in ELEMENTS], Chem[el] == sum(compos[el,m] * Buy[m] for m in MATERIALS)/required) @constraint(model, total, sum(Buy[m] for m in MATERIALS) == required) endfrom pyomo.environ import * #------------------------------------------------------# # optimal scrap bleding problem # #------------------------------------------------------# Infinity = float('inf') model = AbstractModel() model.MATERIALS = Set() model.ELEMENTS = Set() model.required = Param() # required quantity model.minReq = Param(model.ELEMENTS,default=0.0) model.maxReq = Param(model.ELEMENTS,default=Infinity) model.compos = Param(model.ELEMENTS, model.MATERIALS) model.cost = Param(model.MATERIALS) model.avail = Param(model.MATERIALS) # -----------------------------------------------------# # variable declaration and bounding # -----------------------------------------------------# def chem_bnds(model, i): return (model.minReq[i], model.maxReq[i]) def qty_bnds(model, i): return (0.0, model.avail[i]) model.Buy = Var(model.MATERIALS,bounds=qty_bnds) model.Chem = Var(model.ELEMENTS, bounds=chem_bnds) # -----------------------------------------------------# # objective function # -----------------------------------------------------# def totalcost_rule(model): return sum (model.cost[m] * model.Buy[m] for m in model.MATERIALS) model.totalcost = Objective(rule=totalcost_rule) # -----------------------------------------------------# # constraints # -----------------------------------------------------# def chem_rule(model,el): return model.Chem[el] == sum(model.compos[el,m] * model.Buy[m] for m in model.MATERIALS) / model.required model.chem = Constraint(model.ELEMENTS,rule=chem_rule) def total_rule(model): return sum(model.Buy[m] for m in model.MATERIALS) == model.required model.total = Constraint(rule=total_rule)In order to solve the model, we need to combine the model, a set of data, and pass through a suitable solver. In this example we choose the Cbc [18] open source linear and mixed integer solver. We obtained an optimal solution through a set of language-specific commands, reported below.

model Al_blend.mod; data Al6061.dat; option solver cbc; solve; display Buy; display minReq, Chem, maxReq;using JuMP using Cbc model = Model(Cbc.Optimizer) include("Al_blend_mod.jl") blend_model(model,"Al6061.dat") optimize!(model) println("\n=============== optimal solution =============\n") for m in MATERIALS println("$(m) : $(JuMP.value(model[:Buy][m]))") end println("\n=============== chemical composition =============\n") for el in ELEMENTS println("$(el): $(bounds[el,"minReq"]) <= $(JuMP.value(model[:Chem][el])) <= $(bounds[el,"maxReq"]))") endpyomo solve --solver=cbc Al_blend.py Al6061.datThe solution we obtained by running this solver with the above data was:

\begin{align*} \begin{array}[c]{lr} \hline \mathtt{UBC} & 154.87 \\ \mathtt{Radiator} & 1.07 \\ \mathtt{WireScraps} & 1\,200.00 \\ \mathtt{MixedTurnings} & 139.28 \\ \mathtt{Mg} & 4.78 \\ \hline \end{array} \end{align*}with an overall cost of 1286.37 (an average of 0.857 per unit produced). The chemical composition of the blend is

\begin{align*} \begin{array}[c]{llll} Element & min & actual & max \\ \hline \mathtt{Si} & 0.4 & 0.8 & 0.8\\ \mathtt{Mg} & 0.8 & 0.8 & 1.2\\ \mathtt{Fe} & 0.0 & 0.35 & 0.8\\ \mathtt{Cu} & 0.15 & 0.31 & 0.4\\ \mathtt{Mn} & 0.0 & 0.15 & 0.15\\ \mathtt{Zn} & 0.0 & 0.15 & 0.25\\ \hline \end{array} \end{align*}These data have been obtained by running a solver on the supplied model and data. An example of the output which can be obtained from a solver is given below.

CBC 2.10.3 optimal, objective 1286.369005 5 iterations Buy [*] := LithoSheets 0 Mg 4.77662 MixedAuto 0 MixedTurnings 139.282 Radiator 1.06954 Si 0 UBC 154.872 WireScraps 1200 ; : minReq Chem maxReq := Cu 0.15 0.310622 0.4 Fe 0 0.348733 0.7 Mg 0.8 0.8 1.2 Mn 0 0.15 0.15 Si 0.4 0.8 0.8 Zn 0 0.150333 0.25 ;Welcome to the CBC MILP Solver Version: 2.10.3 Build Date: Jan 1 1970 command line - Cbc_C_Interface -solve -quit (default strategy 1) Presolve 7 (0) rows, 8 (-6) columns and 41 (-6) elements 0 Obj 536.91077 Primal inf 1395.4875 (4) 5 Obj 1286.369 Optimal - objective value 1286.369 After Postsolve, objective 1286.369, infeasibilities - dual 0 (0), primal 0 (0) Optimal objective 1286.369005 - 5 iterations time 0.002, Presolve 0.00 Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00 =============== optimal solution ============= UBC : 154.87179487179483 MixedAuto : 0.0 Radiator : 1.069538461538454 WireScraps : 1200.0 MixedTurnings : 139.28205128205133 LithoSheets : 0.0 Si : 0.0 Mg : 4.776615384615386 =============== chemical composition ============= Si: 0.4 <= 0.8000000000000002 <= 0.8) Mg: 0.8 <= 0.8 <= 1.2) Fe: 0.0 <= 0.3487333128205128 <= 0.8) Cu: 0.15 <= 0.3106215384615384 <= 0.4) Mn: 0.0 <= 0.14999999999999997 <= 0.15) Zn: 0.0 <= 0.15033333333333337 <= 0.25)# ========================================================== # = Solver Results = # ========================================================== # ---------------------------------------------------------- # Problem Information # ---------------------------------------------------------- Problem: - Lower bound: -inf Upper bound: inf Number of objectives: 1 Number of constraints: 7 Number of variables: 14 Sense: unknown # ---------------------------------------------------------- # Solver Information # ---------------------------------------------------------- Solver: - Status: ok Message: CBC 2.10.3 optimal, objective 1286.36900512821; 5 iterations Termination condition: optimal Id: 0 Error rc: 0 Time: 0.02892017364501953 # ---------------------------------------------------------- # Solution Information # ---------------------------------------------------------- Solution: - number of solutions: 1 number of solutions displayed: 1 - Gap: None Status: optimal Message: CBC 2.10.3 optimal, objective 1286.36900512821; 5 iterations Objective: totalcost: Value: 1286.3690051282053 Variable: Buy[Mg]: Value: 4.776615384615386 Buy[MixedTurnings]: Value: 139.28205128205136 Buy[Radiator]: Value: 1.069538461538454 Buy[UBC]: Value: 154.87179487179483 Buy[WireScraps]: Value: 1200 Chem[Cu]: Value: 0.3106215384615384 Chem[Fe]: Value: 0.34873331282051284 Chem[Mg]: Value: 0.8 Chem[Mn]: Value: 0.15 Chem[Si]: Value: 0.8000000000000004 Chem[Zn]: Value: 0.15033333333333337 Constraint: No valuesWe can observe, from the above results, that some elements, like

`Mg`

, are expensive and, thus kept at their minimum value in the optimal solution; on the contrary, others, like`Mn`

, are cheap. We also can observe that in the final optimal blend some materials,`Radiator`

in particular, are present in a tiny fraction of the overall blend. We might easily modify the data to exclude this from the blend. However, it might be preferable to insert a`logical`

constraint stating that for every material, either it is not included in the optimal solution or its level should be greater than a threshold. As an example we might add a constraint saying that either`Radiator`

is zero or it needs to be more than, say, 50kg. This kind of constraint will be presented later in this volume (see section Using binary variables in logical constraints).

In this first introductory model we have seen the main components of mathematical optimization models:

index sets (the names of the scrap, the names of the chemical elements);

numerical parameters (scalars, vectors, matrices) such as the quantity to be produced, the required quality, the unit cost, the chemical composition of each material;

the variables, in this case associated with the quantities to be used in the preparation of the blend;

the constraints, equations or inequalities (in this case they are all linear);

the objective to be optimized, in this case the total cost of the blend, to be minimized.

Since the variables appear linearly in all the constraints and in the objective function, the model just described is called a linear optimization model .

The above ingredients will appear in most of the models analyzed in this volume. From the next paragraph we will begin to examine some important specific classes of optimization models.

© Fabio Schoen 2023