7 Introduction to Optimisation
253
design variables to ensure that only discrete values can be considered, described as
‘linear integer programs’. If the design vectors are pure (or all) integer, the problem
is classed as a ‘pure integer program’, whereas if at least one (but not all) design
vector integer, the problem is classed as a ‘mixed-integer program’, discussed in
Sect. 7.3.2.1. Alternatively, these problems can be categorised into general nonnegative integer problems or ‘binary’, where the discrete, integer design vectors hold
a value of either 0 or 1. Most mixed-integer problems in practice are binary, and the
use of integer variables, although beneficial in certain circumstances, is much less
common.
Often in ‘combinatorial optimisation’, the phrases ‘combinatorial’, ‘discrete’ and
‘integer’ are used interchangeably with little explanation of the differences between
them. Each of the three terms can be used to describe a problem or optimisation
method formulated for use with integers, as opposed to continuous variables, as
inputs and outputs of the problem or as components of the optimisation process.
Often, the term discrete, when used to describe problems and processes, is used
to simply describe the discrete nature of one or more aspects of said process, i.e. a
‘discrete problem’, as opposed to a continuous problem. It is not accurate to say that
a discrete problem is always an integer problem, e.g. if a problem has discrete design
variables x = 0, 0.3, 0.6, 0.9, 1.2, the problem is considered ‘discrete’, but not
integer. Similarly, the term combinatorial describes the problem formulation but
can also be used to describe the origin or solution of a problem, and is categorised
by the exponential explosion of variables or constraints, often modelled by ‘integer
programming’. Finally, the phrase integeri, with respect to optimisation, is usually
intended to describe the use of integer values in formulation or solution and thus
also modelling. The similarities between these terms allows for a certain degree
of interchangeability, though it is important to know where each term should and
should not be used.
Integer programming was first recognised in the 1940s to 1950s, where the
simplex algorithm (derived in 1948 and published in 1951) described a finite
method suitable for application on any linear objective function subject to a finite
set of linear constraints [81]. It was not until 1955 that Harold Kuhn derived a
combinatorial algorithm for a single, specific integer problem using a dual-primal
linear algorithm. Since then, a number of papers have expanded upon the available
techniques and solving algorithms, introducing these tools to a wider and wider
audience, such that many modern-day application rely on integer programming
techniques.
Many real-world problems require the evaluation of integer problems; thus
the interest in and knowledge applicable to optimisation of these problems are
highly valued and ever-increasing. Many industries require the use of integer
programming to solve practical problems. Communications, activity management,
resource management, time scheduling and machine sequencing are vital to the
cost minimising, resource management and time management of large commercial
and industrial firms, whereas other problem applications are less grounded in
real-life scenarios, such as high-energy physics and X-ray crystallography. These
problems are generally more difficult to solve than problems that are linear and/or
253
design variables to ensure that only discrete values can be considered, described as
‘linear integer programs’. If the design vectors are pure (or all) integer, the problem
is classed as a ‘pure integer program’, whereas if at least one (but not all) design
vector integer, the problem is classed as a ‘mixed-integer program’, discussed in
Sect. 7.3.2.1. Alternatively, these problems can be categorised into general nonnegative integer problems or ‘binary’, where the discrete, integer design vectors hold
a value of either 0 or 1. Most mixed-integer problems in practice are binary, and the
use of integer variables, although beneficial in certain circumstances, is much less
common.
Often in ‘combinatorial optimisation’, the phrases ‘combinatorial’, ‘discrete’ and
‘integer’ are used interchangeably with little explanation of the differences between
them. Each of the three terms can be used to describe a problem or optimisation
method formulated for use with integers, as opposed to continuous variables, as
inputs and outputs of the problem or as components of the optimisation process.
Often, the term discrete, when used to describe problems and processes, is used
to simply describe the discrete nature of one or more aspects of said process, i.e. a
‘discrete problem’, as opposed to a continuous problem. It is not accurate to say that
a discrete problem is always an integer problem, e.g. if a problem has discrete design
variables x = 0, 0.3, 0.6, 0.9, 1.2, the problem is considered ‘discrete’, but not
integer. Similarly, the term combinatorial describes the problem formulation but
can also be used to describe the origin or solution of a problem, and is categorised
by the exponential explosion of variables or constraints, often modelled by ‘integer
programming’. Finally, the phrase integeri, with respect to optimisation, is usually
intended to describe the use of integer values in formulation or solution and thus
also modelling. The similarities between these terms allows for a certain degree
of interchangeability, though it is important to know where each term should and
should not be used.
Integer programming was first recognised in the 1940s to 1950s, where the
simplex algorithm (derived in 1948 and published in 1951) described a finite
method suitable for application on any linear objective function subject to a finite
set of linear constraints [81]. It was not until 1955 that Harold Kuhn derived a
combinatorial algorithm for a single, specific integer problem using a dual-primal
linear algorithm. Since then, a number of papers have expanded upon the available
techniques and solving algorithms, introducing these tools to a wider and wider
audience, such that many modern-day application rely on integer programming
techniques.
Many real-world problems require the evaluation of integer problems; thus
the interest in and knowledge applicable to optimisation of these problems are
highly valued and ever-increasing. Many industries require the use of integer
programming to solve practical problems. Communications, activity management,
resource management, time scheduling and machine sequencing are vital to the
cost minimising, resource management and time management of large commercial
and industrial firms, whereas other problem applications are less grounded in
real-life scenarios, such as high-energy physics and X-ray crystallography. These
problems are generally more difficult to solve than problems that are linear and/or