7 Introduction to Optimisation
261
For any strategy, the lower bound must be fairly close to the minimum objective
value and generate candidate problems where the lower bounds are as high as
possible. The computational time of the strategy, including calculation of the lower
bounds for every candidate problem, must be low enough that the algorithm can be
iterated many times.
Heuristic Methods
Methods to solve combinatorial optimisation problems discussed so far have been
exact, i.e. finding the global solution is guaranteed (if there is a feasible solution).
When heuristics are involved, this is not the case. Heuristics provide alternative
methods for finding solutions to challenging problems (in particular in real-world
settings) that do not guarantee an optimal solution (some of them only in statistical
way). We note that this is different than approximation algorithms, which provide
a performance guarantee such as maximum deviation from the optimal solution.
Conversely to deterministic sampling, heuristic sampling requires a distribution of
sample points over the search space with a higher density of points in areas of
particular interest. Common heuristics include (a) relaxation-based heuristics and
(b) rounding-based heuristics.
These methods are valid for only convex or small-scale non-convex MINLPs.
There is no method yet that can reliably solve large-scale MINLPs, and, when
compared, the algorithms that exist to solve convex MINLPs do not show a
clear ‘best algorithm’, as can be expected. Where MINLP algorithms lack in
computational speed and other desirable characteristics, a mixed-integer problem
(MIP) is often used as a replacement for large-scale, real-world problems. Even
without non-linear constraints, these problems can still be extremely hard, actual
NP-hard [87].
The nearest neighbour heuristic and the Christofides algorithm [88] are wellknown start heuristics for the TSP. The k-OPT-algorithm is an improvement
heuristic which was originally designed for the TSP, but variants of this are used
for several other combinatorial optimisation problems. It also formed the basis for
the Lin-Kernighan heuristic [89] which is one of the most common algorithms
used to find good solutions for TSPs. Balas and Martin [90] presented the pivotand-complement that was developed for binary programs (BPs) and is based on
the observation that, in the nomenclature of the simplex algorithm, an LP-feasible
solution of which all basic variables are slack variables is also integer feasible. It
performs pivot operations which drive the integer variables out of the basis and the
slacks into the basis. The same authors [91] developed another method called pivotand-shift that can be applied to general MIPs. The method was further improved
with more pivot types and new rules for selecting them, as well as an extension of
the shifting procedure, and a neighbourhood search related to local branching [92].
Another method is the so-called heuristic ceiling point algorithm, which was
restricted to integer problems (IPs) without equality constraints. Scatter search with
star paths is a diversification heuristic [93] that creates a couple of points which are
261
For any strategy, the lower bound must be fairly close to the minimum objective
value and generate candidate problems where the lower bounds are as high as
possible. The computational time of the strategy, including calculation of the lower
bounds for every candidate problem, must be low enough that the algorithm can be
iterated many times.
Heuristic Methods
Methods to solve combinatorial optimisation problems discussed so far have been
exact, i.e. finding the global solution is guaranteed (if there is a feasible solution).
When heuristics are involved, this is not the case. Heuristics provide alternative
methods for finding solutions to challenging problems (in particular in real-world
settings) that do not guarantee an optimal solution (some of them only in statistical
way). We note that this is different than approximation algorithms, which provide
a performance guarantee such as maximum deviation from the optimal solution.
Conversely to deterministic sampling, heuristic sampling requires a distribution of
sample points over the search space with a higher density of points in areas of
particular interest. Common heuristics include (a) relaxation-based heuristics and
(b) rounding-based heuristics.
These methods are valid for only convex or small-scale non-convex MINLPs.
There is no method yet that can reliably solve large-scale MINLPs, and, when
compared, the algorithms that exist to solve convex MINLPs do not show a
clear ‘best algorithm’, as can be expected. Where MINLP algorithms lack in
computational speed and other desirable characteristics, a mixed-integer problem
(MIP) is often used as a replacement for large-scale, real-world problems. Even
without non-linear constraints, these problems can still be extremely hard, actual
NP-hard [87].
The nearest neighbour heuristic and the Christofides algorithm [88] are wellknown start heuristics for the TSP. The k-OPT-algorithm is an improvement
heuristic which was originally designed for the TSP, but variants of this are used
for several other combinatorial optimisation problems. It also formed the basis for
the Lin-Kernighan heuristic [89] which is one of the most common algorithms
used to find good solutions for TSPs. Balas and Martin [90] presented the pivotand-complement that was developed for binary programs (BPs) and is based on
the observation that, in the nomenclature of the simplex algorithm, an LP-feasible
solution of which all basic variables are slack variables is also integer feasible. It
performs pivot operations which drive the integer variables out of the basis and the
slacks into the basis. The same authors [91] developed another method called pivotand-shift that can be applied to general MIPs. The method was further improved
with more pivot types and new rules for selecting them, as well as an extension of
the shifting procedure, and a neighbourhood search related to local branching [92].
Another method is the so-called heuristic ceiling point algorithm, which was
restricted to integer problems (IPs) without equality constraints. Scatter search with
star paths is a diversification heuristic [93] that creates a couple of points which are