7 Introduction to Optimisation
255
Fig. 7.1 Integer problem
with linear constraints
This can be seen graphically in Fig. 7.1. We note that the number of points
available for evaluation by the function are extremely limited and clearly seen as
finite and by extension, the number of different values provided by the function
is finite. This is due to the small number of dimensions. As the number of
dimensions increases, the number of possible points increases exponentially. For
simple problems such as this, an exhaustive search can be used. Complications arise
upon the introduction of additional dimensions of the design vector where the size
of the search space increases drastically depending upon the bounds, as described
by the ‘curse of dimensionality’.
7.3.1.1 Special Case: 0-1 Integer Programming
As introduced earlier, 0-1 integer programming or ‘binary programming’, is a
special category of integer-only problem where the design variables are either one
or zero (binary). This problem formulation is most commonly used for decisionmaking, when the inputs to a function is one of only two possible values: yes/no,
open/closed, true/false, etc. [82].
Its mathematical formulation is
n
j =1
c
T
j x j
(7.20)
subject to: A i,j x j ≤ b i
(7.21)
x i = {0, 1}
(7.22)