260
A. Riccardi et al.
additional constraints on the original function. The search space thought to contain
the ‘best solution’ is then analysed. If the optimal solution is found, the subspace,
and thus also the candidate problem, is fathomed. If not, the problem only contains
a lower bound for the minimum objective value in it, and this subspace is divided
into yet smaller subspaces (or candidate problems), and the process is repeated. This
process can be adapted for specific problems. Consider problems with 0-1 variables.
To branch these problems, extra constraints can be added to constrict x 1 = 0 or x 1 =
1, creating two candidate subproblems. In this case, x 1 is known as the branching
variable
The ‘bound’ step of the branch-and-bound algorithm is dependent on the
objective of the objective function. Assuming that the objective function z is to
be minimised, lower bounding strategies are required. Any lower bounding strategy
should be simple, efficient and run with a low computational cost. In any case, a
lower bounding method should bound closest to the minimum value of z, which can
be handled using one of the many strategies [85].
• Relaxation of constraints: All difficult or computationally costly constraints
are relaxed, and z is minimised for only the remaining constraints. Using this
method, the minimum value of z is equal to the lower bound for z min in the
original problem.
• Modification of the objective function: In this case, the modified objective
function is created such that f ≤ z for all feasible solutions. Furthermore, f
should be easy to minimise subject to the original constraints. Subject to these
properties, f is a lower bound to z min of the original problem.
• Lagrangian Relaxation: A Lagrangian multiplier is created where u in L(u, x)
is associated with the relaxed constraints. In this case, the optimum z is a lower
bound of z min of the original problem.
• Branch-and-cut: Otherwise known as ‘cutting planes’, this iterative method
solves the LP relaxation at each solution, and depending on if the solution is
optimal or not, it is either accepted (if optimal) or a linear constraint is found that
excludes the LP solution and no others. This constraint is referred to as a ‘cut’.
The branch-and-bound algorithm is searched using a ‘search tree method’. In
this case, the original solution is analysed and branched, splitting the problem into
two candidate problems. These two problems are bound, analysed and branched.
Candidate problems which do not contain an optimal solution are not branched and
become terminal nodes. Candidate problems which contain an optimal solution are
further branched, and the process repeats. Terminal nodes may be required in further
iterations of the algorithm. This search method continues to branch until an optimal
solution is found.
Since its introduction in 1960, the branch-and-bound method has been slightly
altered for improved results on specific problems. One such example of this is the
‘Beale and Small’ method [86]. This method uses a different bounding strategy,
includes the termination of particularly non-optimal subspaces and includes a
heuristic ‘worst alternative’ branching method.
A. Riccardi et al.
additional constraints on the original function. The search space thought to contain
the ‘best solution’ is then analysed. If the optimal solution is found, the subspace,
and thus also the candidate problem, is fathomed. If not, the problem only contains
a lower bound for the minimum objective value in it, and this subspace is divided
into yet smaller subspaces (or candidate problems), and the process is repeated. This
process can be adapted for specific problems. Consider problems with 0-1 variables.
To branch these problems, extra constraints can be added to constrict x 1 = 0 or x 1 =
1, creating two candidate subproblems. In this case, x 1 is known as the branching
variable
The ‘bound’ step of the branch-and-bound algorithm is dependent on the
objective of the objective function. Assuming that the objective function z is to
be minimised, lower bounding strategies are required. Any lower bounding strategy
should be simple, efficient and run with a low computational cost. In any case, a
lower bounding method should bound closest to the minimum value of z, which can
be handled using one of the many strategies [85].
• Relaxation of constraints: All difficult or computationally costly constraints
are relaxed, and z is minimised for only the remaining constraints. Using this
method, the minimum value of z is equal to the lower bound for z min in the
original problem.
• Modification of the objective function: In this case, the modified objective
function is created such that f ≤ z for all feasible solutions. Furthermore, f
should be easy to minimise subject to the original constraints. Subject to these
properties, f is a lower bound to z min of the original problem.
• Lagrangian Relaxation: A Lagrangian multiplier is created where u in L(u, x)
is associated with the relaxed constraints. In this case, the optimum z is a lower
bound of z min of the original problem.
• Branch-and-cut: Otherwise known as ‘cutting planes’, this iterative method
solves the LP relaxation at each solution, and depending on if the solution is
optimal or not, it is either accepted (if optimal) or a linear constraint is found that
excludes the LP solution and no others. This constraint is referred to as a ‘cut’.
The branch-and-bound algorithm is searched using a ‘search tree method’. In
this case, the original solution is analysed and branched, splitting the problem into
two candidate problems. These two problems are bound, analysed and branched.
Candidate problems which do not contain an optimal solution are not branched and
become terminal nodes. Candidate problems which contain an optimal solution are
further branched, and the process repeats. Terminal nodes may be required in further
iterations of the algorithm. This search method continues to branch until an optimal
solution is found.
Since its introduction in 1960, the branch-and-bound method has been slightly
altered for improved results on specific problems. One such example of this is the
‘Beale and Small’ method [86]. This method uses a different bounding strategy,
includes the termination of particularly non-optimal subspaces and includes a
heuristic ‘worst alternative’ branching method.