256
A. Riccardi et al.
Many real-life decision-making problems involve significant yes/no decisions,
most often at strategic and tactical levels. The knapsack problem is a classic example
of this type of problem. Moreover, other non-binary problems can be converted into
this form if beneficial, where values can be split into ones and zeros to represent
high/low temperatures, fast/slow speeds and other extremes. This can be added
in practice by introducing equality constraints such that 0 = x and 1 = x.
Take a condition monitoring system which uses a temperature input to determine
if a particular part has overheated. Binary programming may be applied where
temperatures above a certain value are considered a failure (1) and temperatures
below this are considered acceptable (0).
7.3.2 Mixed-Integer Programming
Mixed-integer programming, although commonly utilised in many modern-day
problems, was developed following the formulation of the simplex method, developed by Dantzig in 1951. This was followed by the work from Ford and Fulkerson,
whose earliest contribution to network flow began with ‘maximal flow through
a network’, which is often credited as the original algorithm designed to solve
maximum flow problems, and thus is considered one of the most influential papers in
the development of further algorithms used for solving and analysing network flow
models [83]. The simplex method also gave way to the first pure integer optimisation
algorithm developed by Gomory in 1958. The increase in complexity resulted in
an increase in computational cost, best modelled by a polynomial-time algorithm.
These models allowed for the categorisation of problems into categories depending
on hardness, where integer programming was considered NP-hard in general.
More complex problems may require the use of mixed-integer variables. That
is to say that one or more variables of function f (x m+n ) are a set of continuous variable(s), x 1 , x 2 , . . . x m , and other variable(s) that are discrete values
x m+1 , x m+2 , . . . x n+m .
Mixed-integer problems cannot be solved by a continuous variable-based solver,
as the step size, Δx, may be unsuitable for discrete variables. Take the steepest
descent algorithm as an example: if the step size, λ, is not compatible with the design
variables (in this case, not an integer), this will result in the failure of the algorithm
and thus, no solution. Conversely, discrete solvers may disregard step sizes for
continuous variables that are smaller than one, thus increasing the inaccuracy in the
solver. This acts as a form of proof of the NFL theorem but also highlights the need
for the development and correct application of more integer programming methods
and categories, such as linear and non-linear.
A. Riccardi et al.
Many real-life decision-making problems involve significant yes/no decisions,
most often at strategic and tactical levels. The knapsack problem is a classic example
of this type of problem. Moreover, other non-binary problems can be converted into
this form if beneficial, where values can be split into ones and zeros to represent
high/low temperatures, fast/slow speeds and other extremes. This can be added
in practice by introducing equality constraints such that 0 = x and 1 = x.
Take a condition monitoring system which uses a temperature input to determine
if a particular part has overheated. Binary programming may be applied where
temperatures above a certain value are considered a failure (1) and temperatures
below this are considered acceptable (0).
7.3.2 Mixed-Integer Programming
Mixed-integer programming, although commonly utilised in many modern-day
problems, was developed following the formulation of the simplex method, developed by Dantzig in 1951. This was followed by the work from Ford and Fulkerson,
whose earliest contribution to network flow began with ‘maximal flow through
a network’, which is often credited as the original algorithm designed to solve
maximum flow problems, and thus is considered one of the most influential papers in
the development of further algorithms used for solving and analysing network flow
models [83]. The simplex method also gave way to the first pure integer optimisation
algorithm developed by Gomory in 1958. The increase in complexity resulted in
an increase in computational cost, best modelled by a polynomial-time algorithm.
These models allowed for the categorisation of problems into categories depending
on hardness, where integer programming was considered NP-hard in general.
More complex problems may require the use of mixed-integer variables. That
is to say that one or more variables of function f (x m+n ) are a set of continuous variable(s), x 1 , x 2 , . . . x m , and other variable(s) that are discrete values
x m+1 , x m+2 , . . . x n+m .
Mixed-integer problems cannot be solved by a continuous variable-based solver,
as the step size, Δx, may be unsuitable for discrete variables. Take the steepest
descent algorithm as an example: if the step size, λ, is not compatible with the design
variables (in this case, not an integer), this will result in the failure of the algorithm
and thus, no solution. Conversely, discrete solvers may disregard step sizes for
continuous variables that are smaller than one, thus increasing the inaccuracy in the
solver. This acts as a form of proof of the NFL theorem but also highlights the need
for the development and correct application of more integer programming methods
and categories, such as linear and non-linear.