254
A. Riccardi et al.
continuous. Although the true advantage of combinatorial optimisation methods lies
in the ability to process indivisible, discrete, real-life parameters, this optimisation
category can also be utilised to convert continuous inputs to integer-only inputs
with the intention of providing yes-no output values (which can be formulated as
0-1 integer problems), a particularly useful trait in machinery diagnosis.
Network optimisation is a special form of linear programming, where the
structure of the program allows even faster solution approaches such as network
simplex algorithm, and they are highly valued in their ability to optimise some
of the most common, fundamental problems with minimal cost and a free flow
of data to and from each network node. Analytically, network flow problems can
solve some classes of combinatorial optimisation problems, such as shortest path,
assignment and transportation. Network flow problems, although often complex, are
utilised in the design and analysis of large connected problems, proving to be vital
to the operation of many transportation, communication, manufacturing and social
networks. Network optimisation methods make use of powerful techniques such
as data caching, streamlining of data protocols and even data elimination. These
techniques, when correctly applied, can assist in developing faster data transfers,
accurate transport solutions and improved response times for software applications.
7.3.1 Pure Integer Optimisation
As introduced earlier, integer-only programming is a form of combinatorial optimisation developed for cases where all design vectors are integer, i.e. x ∈ {0, 1, 2 . . .}.
Mathematically speaking, the original problem formulation, shown in the Introduction section of this chapter, can be altered to describe the case of an integer-only
problem. Integer-only or ‘pure integer’ optimisation can make use of combinatorial
optimisation algorithms since the search space, and hence the number of potential
solutions is finite. Moreover, in a constrained integer-only problem, the number
of potential solutions is limited by the number of possible combinations of every
integer. For smaller problems, an exhaustive search may be used to evaluate each
point in the design space, but this cannot be extended to larger problems due to the
curse of dimensionality. This can be seen visually by Fig. 7.1, a simple integeronly problem with two integer inputs and three linear inequality constraints, as
formulated in Eqs. (7.16) to (7.19).
x = [x 1 x 2 ] ∈ {0, 1, 2 . . .}
(7.16)
A = [3 − 1]
(7.17)
b = [0 − 10]
(7.18)
lb = [0 0]; ub = [10 10];
(7.19)
A. Riccardi et al.
continuous. Although the true advantage of combinatorial optimisation methods lies
in the ability to process indivisible, discrete, real-life parameters, this optimisation
category can also be utilised to convert continuous inputs to integer-only inputs
with the intention of providing yes-no output values (which can be formulated as
0-1 integer problems), a particularly useful trait in machinery diagnosis.
Network optimisation is a special form of linear programming, where the
structure of the program allows even faster solution approaches such as network
simplex algorithm, and they are highly valued in their ability to optimise some
of the most common, fundamental problems with minimal cost and a free flow
of data to and from each network node. Analytically, network flow problems can
solve some classes of combinatorial optimisation problems, such as shortest path,
assignment and transportation. Network flow problems, although often complex, are
utilised in the design and analysis of large connected problems, proving to be vital
to the operation of many transportation, communication, manufacturing and social
networks. Network optimisation methods make use of powerful techniques such
as data caching, streamlining of data protocols and even data elimination. These
techniques, when correctly applied, can assist in developing faster data transfers,
accurate transport solutions and improved response times for software applications.
7.3.1 Pure Integer Optimisation
As introduced earlier, integer-only programming is a form of combinatorial optimisation developed for cases where all design vectors are integer, i.e. x ∈ {0, 1, 2 . . .}.
Mathematically speaking, the original problem formulation, shown in the Introduction section of this chapter, can be altered to describe the case of an integer-only
problem. Integer-only or ‘pure integer’ optimisation can make use of combinatorial
optimisation algorithms since the search space, and hence the number of potential
solutions is finite. Moreover, in a constrained integer-only problem, the number
of potential solutions is limited by the number of possible combinations of every
integer. For smaller problems, an exhaustive search may be used to evaluate each
point in the design space, but this cannot be extended to larger problems due to the
curse of dimensionality. This can be seen visually by Fig. 7.1, a simple integeronly problem with two integer inputs and three linear inequality constraints, as
formulated in Eqs. (7.16) to (7.19).
x = [x 1 x 2 ] ∈ {0, 1, 2 . . .}
(7.16)
A = [3 − 1]
(7.17)
b = [0 − 10]
(7.18)
lb = [0 0]; ub = [10 10];
(7.19)