258
A. Riccardi et al.
b i (x) ≤ 0 ∀i ∈ I
(7.26)
x ∈ {x 1 , x 2 . . . x n+m }
(7.27)
where x 1 , x 2 . . . x n are integer variables and x n+1 , x n+2 . . . x n+m are continuous
variables. These problems are particularly complex, combining the combinatorial
difficulty of integer optimisation with non-linear functions, and so few algorithms
have been designed specifically for use with these problems. Most solution algorithms for MINLPs fall into one of the two categories: single-tree and multi-tree
methods [84]. MINLPs can be solved using a generalised Benders’ decomposition
(multi-tree), where a general MIP problem is employed with non-linear programming subproblems, and a modified branch-and-bound method (multi-tree), where
modifications are made to improve the performance of the algorithm. Complications
arise during the optimisation of a non-convex MINLP since even after relaxation of
the integer design variables to continuous design variables, the function can remain
non-convex, resulting in many local minima.
Many MINLP methods break the problem into their MIP and NLP components
and solve the overall problem iteratively.
7.3.2.2 Methods
The algorithm applied to solve a combinatorial problem is dependent largely on the
possible formulation of the problem and the requirements of the user. As per the
‘no free lunch’ theorem, a single algorithm cannot find the best possible solution
to all possible problems. To find the most suitable solution method, the basic
problem formulation must be considered: linear/non-linear, small/large, singleobjective/multi-objective and binary/integer/mixed-integer.
Similarly to integer-only and continuous-only programming, combinatorial problems can be categorised as linear and non-linear. Also similarly to integer-only and
continuous-only problems, linear problems are typically less complex than nonlinear problems. As a result, fairly large, moderately complex problems can be
solved using ‘exact’ methods, where every part of the problem and its subproblems
are solved either explicitly or implicitly. For larger, more complex problems,
‘heuristic’ methods may be used. Heuristics use intuitive techniques to find a ‘rough’
solution to any given problem to a certain degree of accuracy.
Exact Methods
With relatively simple problems with low computational costs, exact methods can
be used to solve combinatorial problems. These methods, unlike heuristic methods
described in Sect. 7.3.2.2, guarantee an optimal solution and thus are the ideal
choice. These solution methods can be placed into one of the two categories:
implicit enumeration or explicit enumeration. Explicit solution methods are often
A. Riccardi et al.
b i (x) ≤ 0 ∀i ∈ I
(7.26)
x ∈ {x 1 , x 2 . . . x n+m }
(7.27)
where x 1 , x 2 . . . x n are integer variables and x n+1 , x n+2 . . . x n+m are continuous
variables. These problems are particularly complex, combining the combinatorial
difficulty of integer optimisation with non-linear functions, and so few algorithms
have been designed specifically for use with these problems. Most solution algorithms for MINLPs fall into one of the two categories: single-tree and multi-tree
methods [84]. MINLPs can be solved using a generalised Benders’ decomposition
(multi-tree), where a general MIP problem is employed with non-linear programming subproblems, and a modified branch-and-bound method (multi-tree), where
modifications are made to improve the performance of the algorithm. Complications
arise during the optimisation of a non-convex MINLP since even after relaxation of
the integer design variables to continuous design variables, the function can remain
non-convex, resulting in many local minima.
Many MINLP methods break the problem into their MIP and NLP components
and solve the overall problem iteratively.
7.3.2.2 Methods
The algorithm applied to solve a combinatorial problem is dependent largely on the
possible formulation of the problem and the requirements of the user. As per the
‘no free lunch’ theorem, a single algorithm cannot find the best possible solution
to all possible problems. To find the most suitable solution method, the basic
problem formulation must be considered: linear/non-linear, small/large, singleobjective/multi-objective and binary/integer/mixed-integer.
Similarly to integer-only and continuous-only programming, combinatorial problems can be categorised as linear and non-linear. Also similarly to integer-only and
continuous-only problems, linear problems are typically less complex than nonlinear problems. As a result, fairly large, moderately complex problems can be
solved using ‘exact’ methods, where every part of the problem and its subproblems
are solved either explicitly or implicitly. For larger, more complex problems,
‘heuristic’ methods may be used. Heuristics use intuitive techniques to find a ‘rough’
solution to any given problem to a certain degree of accuracy.
Exact Methods
With relatively simple problems with low computational costs, exact methods can
be used to solve combinatorial problems. These methods, unlike heuristic methods
described in Sect. 7.3.2.2, guarantee an optimal solution and thus are the ideal
choice. These solution methods can be placed into one of the two categories:
implicit enumeration or explicit enumeration. Explicit solution methods are often