2.2 Optimization Methods
27
no uniform classification can be found in literature. More than 1000 optimization programs can be found worldwide. “In mathematics we distinguish between
exact methods that deliver a totally definite answer without uncertainty and heuristic methods that deliver an approximate answer” [Ba2012b, p. 5]. Exact methods
determine the optimal solution of an optimization problem for a given period of
time with exponentially increasing computational efforts with increasing numbers of variables or boundary conditions [PH2010, p. 401]. Exact optimization
methods are very computationally intensive and therefore only suitable for a limited system complexity. Additionally, exact methods are not very robust, which
means that every time the problem changes, the algorithm needs to be adjusted [MF2004, p. 55]. The most basic exact method is the complete enumeration,
which lists all possibilities and selects the best one [Ba2012b, p. 5]. By breaking
up the solution space into sections and furthermore creating hierarchical structures (branches) for these sections, a search tree for the branch-and-bound algorithm
is generated. “The bound part of the method uses a problem-specific method to
compute an upper and lower bound upon the goal function value” [Ba2012b,
p. 6]. Thus, large parts of the solution space can be easily identified as unsuitable
for the optimum solution of the optimization task. Exact methods are also called
mathematical programming and make up the only kind of optimization accepted
by the mathematical optimization science [Ca2013, p. 7].
Besides exact methods, heuristic optimization methods exist. They “describes
a class of procedures for finding acceptable solutions to a variety of difficult
decision problems, that is, procedures for searching for the best solutions to
optimization problems” [LM2013, p. 695]. Through a limitation of the size of
the solution space, heuristic methods use a defined search-strategy to allow the
search for a relatively good solution depending on the available computing time
[PH2010, p. 401]. Heuristic methods are usually problem-oriented and do not
guarantee to find the mathematical optimum. Additionally, they do not give an
estimate of how far the solution found is from the actual optimum, but they use
the known properties to quickly generate good solutions [SM2009, p. 13]. Heuristic optimization methods can be split up in optimization procedures specifically
tailored to OR problems and metaheuristics which can be used universally to solve
multiple optimization problems [So2018, p. 58]. While heuristics exploit a specific aspect of a problem and only apply to this aspect 14 , metaheuristics are general
exist, which will not be further discussed here for reasons of space. For this work, the differentiation of exact and heuristic methods will be made and within the heuristic methods, the
classification of trajectory-based and population-based algorithms will be discussed shortly.
14 „For example, when solving a linear programming problem by the simplex algorithm, a
heuristic is often used for choosing so-called entering and leaving variables“ [CT2018, p. 22].
27
no uniform classification can be found in literature. More than 1000 optimization programs can be found worldwide. “In mathematics we distinguish between
exact methods that deliver a totally definite answer without uncertainty and heuristic methods that deliver an approximate answer” [Ba2012b, p. 5]. Exact methods
determine the optimal solution of an optimization problem for a given period of
time with exponentially increasing computational efforts with increasing numbers of variables or boundary conditions [PH2010, p. 401]. Exact optimization
methods are very computationally intensive and therefore only suitable for a limited system complexity. Additionally, exact methods are not very robust, which
means that every time the problem changes, the algorithm needs to be adjusted [MF2004, p. 55]. The most basic exact method is the complete enumeration,
which lists all possibilities and selects the best one [Ba2012b, p. 5]. By breaking
up the solution space into sections and furthermore creating hierarchical structures (branches) for these sections, a search tree for the branch-and-bound algorithm
is generated. “The bound part of the method uses a problem-specific method to
compute an upper and lower bound upon the goal function value” [Ba2012b,
p. 6]. Thus, large parts of the solution space can be easily identified as unsuitable
for the optimum solution of the optimization task. Exact methods are also called
mathematical programming and make up the only kind of optimization accepted
by the mathematical optimization science [Ca2013, p. 7].
Besides exact methods, heuristic optimization methods exist. They “describes
a class of procedures for finding acceptable solutions to a variety of difficult
decision problems, that is, procedures for searching for the best solutions to
optimization problems” [LM2013, p. 695]. Through a limitation of the size of
the solution space, heuristic methods use a defined search-strategy to allow the
search for a relatively good solution depending on the available computing time
[PH2010, p. 401]. Heuristic methods are usually problem-oriented and do not
guarantee to find the mathematical optimum. Additionally, they do not give an
estimate of how far the solution found is from the actual optimum, but they use
the known properties to quickly generate good solutions [SM2009, p. 13]. Heuristic optimization methods can be split up in optimization procedures specifically
tailored to OR problems and metaheuristics which can be used universally to solve
multiple optimization problems [So2018, p. 58]. While heuristics exploit a specific aspect of a problem and only apply to this aspect 14 , metaheuristics are general
exist, which will not be further discussed here for reasons of space. For this work, the differentiation of exact and heuristic methods will be made and within the heuristic methods, the
classification of trajectory-based and population-based algorithms will be discussed shortly.
14 „For example, when solving a linear programming problem by the simplex algorithm, a
heuristic is often used for choosing so-called entering and leaving variables“ [CT2018, p. 22].