7 Introduction to Optimisation
259
the simplest way of solving a problem using all possible solutions (an extensive
search), but due to the ‘curse of dimensionality’, the complexity of the problem rises
exponentially with the increasing number of dimensions within the design vector.
As such, explicit enumeration is a valuable tool for small integer problems where
dimensionality is limited. For larger problems, implicit enumeration is used.
Within explicit enumeration, the optimisation algorithm builds all the possible
solutions to find the optimal solution. This is typically more costly than implicit
enumeration, where all possible solutions are considered in some manner without
explicit evaluation. Implicit enumeration methods consist of a wide variety of
possible optimisation algorithms, where the most common are ‘divide-and-conquer’
methods, where a problem is divided into sets of m groups of problems iteratively
until a subproblem is simple enough to be solved, and the branch-and-bound
method, as discussed below.
Branch and Bound
In 1960, Alison Doig and Ailsa Land published a paper entitled ‘An Automatic
Method for Solving Discrete Programming Problems’, introducing the concept
of branch-and-bound algorithms. Although first intended to solve combinatorial
optimisation problems, many improvements have been made to generalise the
algorithm to solve continuous problems and improve the efficiency.
When solving MIP problems, the branch-and-bound method does not consider
integer design variables as discrete values but rather converts these discrete values
to continuous values by relaxation of the integer restrictions. This simplifies
manipulation of the problem and thus, decreases the difficulty to solve.
The ‘branch-and-bound’ method consists generally of three main techniques:
branching, bounding and searching.
• Branching
– This step splits the continuous search space into several smaller subspaces,
eliminating infeasible parts of the continuous space through application of
necessary conditions for integer solutions.
• Bounding
– The method of bounding depends on whether the objective function is to
be maximised or minimised. If this function is to be maximised, an upper
bounding strategy is used, and if minimised, a lower bounding strategy is
applied.
• Searching
– The process of searching each subspace for an optimal solution, preferably the
most promising region first.
To begin the branching process, the search space S is split into a number of
smaller and mutually disjoint subsets S 1 , S 2 , . . . S r . Following this partition, each
subspace is analysed to find a local, feasible minimum, where each subset is also
a set of feasible solutions of a ‘candidate problem’, which is found by imposing
259
the simplest way of solving a problem using all possible solutions (an extensive
search), but due to the ‘curse of dimensionality’, the complexity of the problem rises
exponentially with the increasing number of dimensions within the design vector.
As such, explicit enumeration is a valuable tool for small integer problems where
dimensionality is limited. For larger problems, implicit enumeration is used.
Within explicit enumeration, the optimisation algorithm builds all the possible
solutions to find the optimal solution. This is typically more costly than implicit
enumeration, where all possible solutions are considered in some manner without
explicit evaluation. Implicit enumeration methods consist of a wide variety of
possible optimisation algorithms, where the most common are ‘divide-and-conquer’
methods, where a problem is divided into sets of m groups of problems iteratively
until a subproblem is simple enough to be solved, and the branch-and-bound
method, as discussed below.
Branch and Bound
In 1960, Alison Doig and Ailsa Land published a paper entitled ‘An Automatic
Method for Solving Discrete Programming Problems’, introducing the concept
of branch-and-bound algorithms. Although first intended to solve combinatorial
optimisation problems, many improvements have been made to generalise the
algorithm to solve continuous problems and improve the efficiency.
When solving MIP problems, the branch-and-bound method does not consider
integer design variables as discrete values but rather converts these discrete values
to continuous values by relaxation of the integer restrictions. This simplifies
manipulation of the problem and thus, decreases the difficulty to solve.
The ‘branch-and-bound’ method consists generally of three main techniques:
branching, bounding and searching.
• Branching
– This step splits the continuous search space into several smaller subspaces,
eliminating infeasible parts of the continuous space through application of
necessary conditions for integer solutions.
• Bounding
– The method of bounding depends on whether the objective function is to
be maximised or minimised. If this function is to be maximised, an upper
bounding strategy is used, and if minimised, a lower bounding strategy is
applied.
• Searching
– The process of searching each subspace for an optimal solution, preferably the
most promising region first.
To begin the branching process, the search space S is split into a number of
smaller and mutually disjoint subsets S 1 , S 2 , . . . S r . Following this partition, each
subspace is analysed to find a local, feasible minimum, where each subset is also
a set of feasible solutions of a ‘candidate problem’, which is found by imposing