7 Introduction to Optimisation
257
7.3.2.1 MIP vs MINLP
Mixed-integer programming can be further categorised into mixed-integer programming (MIP) and mixed-integer non-linear programming (MINLP). Problems can
be categorised by the nature of the objectives and constraints with respect to the
design vector. Mixed-integer programming follows the standard linear programming
formulation, where the objectives and constraints are linear with respect to the
design variables which, in this case, consist of at least one design parameter
composed of integers (0, 1, 2 . . . n) and at least one design parameter composed
of continuous values, described in Eq. (7.23).
Minimise c
T (x)
(7.23)
where
Ax ≥ b
x ≥ 0
x j ∈ Z ∀j ∈ I
Commercial solvers such as IBM Ilog Cplex, FICO Xpress and Gurobi as well as
open-source solvers such as COIN-OR all employ the branch-and-bound algorithm
at their core, where the solution is iteratively parted into smaller subproblems,
most commonly referred to as the left and right child problems (with respect to
the original problem), discussed further in Sect. 7.3.2.2. Mixed-integer problems
can also be solved by iteratively solving the so-called separation problem, where
the feasible region of the problem is cut off by adding valid ‘cuts’ (i.e. additional
constraints) and hence by elimination of sections of the design space. This is
commonly known as the ‘cutting plane algorithm’. Where the branch-and-bound
algorithm employs LP relaxation to simplify the subproblems, the cutting plane
algorithm tightens the LP relaxation to find a better approximation of the convex
hull. All MIP solvers employ the so-called branch-and-cut method, which combines
these two major solution methods for a more effective solution process.
A mixed-integer non-linear programming problem consists of at least one design
parameter composed of discrete integers (0, 1, 2 . . . n) and at least one design
parameter composed of continuous values, similar to MIP. However, in this case,
either the objective or at least one of the constraints is non-linear with respect to
design vectors. These problems follow the form:
Minimise f (x)
(7.24)
where
A i (x) = 0 ∀i ∈ E
(7.25)
257
7.3.2.1 MIP vs MINLP
Mixed-integer programming can be further categorised into mixed-integer programming (MIP) and mixed-integer non-linear programming (MINLP). Problems can
be categorised by the nature of the objectives and constraints with respect to the
design vector. Mixed-integer programming follows the standard linear programming
formulation, where the objectives and constraints are linear with respect to the
design variables which, in this case, consist of at least one design parameter
composed of integers (0, 1, 2 . . . n) and at least one design parameter composed
of continuous values, described in Eq. (7.23).
Minimise c
T (x)
(7.23)
where
Ax ≥ b
x ≥ 0
x j ∈ Z ∀j ∈ I
Commercial solvers such as IBM Ilog Cplex, FICO Xpress and Gurobi as well as
open-source solvers such as COIN-OR all employ the branch-and-bound algorithm
at their core, where the solution is iteratively parted into smaller subproblems,
most commonly referred to as the left and right child problems (with respect to
the original problem), discussed further in Sect. 7.3.2.2. Mixed-integer problems
can also be solved by iteratively solving the so-called separation problem, where
the feasible region of the problem is cut off by adding valid ‘cuts’ (i.e. additional
constraints) and hence by elimination of sections of the design space. This is
commonly known as the ‘cutting plane algorithm’. Where the branch-and-bound
algorithm employs LP relaxation to simplify the subproblems, the cutting plane
algorithm tightens the LP relaxation to find a better approximation of the convex
hull. All MIP solvers employ the so-called branch-and-cut method, which combines
these two major solution methods for a more effective solution process.
A mixed-integer non-linear programming problem consists of at least one design
parameter composed of discrete integers (0, 1, 2 . . . n) and at least one design
parameter composed of continuous values, similar to MIP. However, in this case,
either the objective or at least one of the constraints is non-linear with respect to
design vectors. These problems follow the form:
Minimise f (x)
(7.24)
where
A i (x) = 0 ∀i ∈ E
(7.25)