252
A. Riccardi et al.
˙
x = f(t k , x k , u k ) ≈
x k+1 − x k
h
(7.14)
where h is the interval size t k+1 − t k . This Euler form is then transformed into a set
of NLP constraints to be nullified:
c k (y) = =x k+1 − x k − hf(t k , y k , u k )
(7.15)
These constraints, which ensure the equation of motion to be approximately
satisfied, are then coupled with the fixed-event ones and the path constraints, to
construct a continuous trajectory and to respect the requested bounds at the grid
points.
In collocation methods the choice of the interval size is vital because it influences
the accuracy of the interpolated function in representing the true trajectory. An
efficient procedure could be to compute initial estimates with a sparse grid and then
refine it progressively. This implementation makes this technique very robust to
imprecise initial guesses. Also in this method, the sparsity of the matrix shall be
exploited as much as possible to make the algorithm efficient.
The greater drawback of collocation methods is that for problems dominated by
highly non-linear dynamics, a very dense grid is needed to compute an accurate
solution which, when integrated forward for validation, leads to small errors in
the final state. This problem arises from the finite-difference approximation of the
dynamics, as in Eq. (7.14) for an Euler scheme, and from the parametrisation of the
shape. However, a dense grid translates into an expensive matrix inversion during
the NLP subproblem, leading to the degradation of the computational performance.
Pseudospectral methods are a special class of direct collocation where the
optimal control problem is transcribed by parameterising the state and control using
global polynomials and collocating the differential-algebraic equations using the
nodes obtained from a Gaussian quadrature [79, 80]. The terms pseudospectral and
orthogonal collocation are used interchangeably in the literature.
7.3 Combinatorial and Network Optimisation
Until now, all optimisation problems and variables have been continuous, that is,
each design vector has consisted of a set of variables composed of possible values
within a specified range. In this section ‘combinatorial optimisation’ problems
shall be discussed, where some or all of the design variables are restricted to a
discrete set, most commonly binary integers, but also non-negative integers. This
section will also discuss problems with a finite number of possibilities, namely,
problems formulated to find a maximum or minimum of one or more functions, with
many variables, which can be limited by a series of equality constraints, inequality
constraints and bounds. All of these problems are ‘linear problems’ or can be
reformulated as such with the inclusion of some constriction on one or more of the
A. Riccardi et al.
˙
x = f(t k , x k , u k ) ≈
x k+1 − x k
h
(7.14)
where h is the interval size t k+1 − t k . This Euler form is then transformed into a set
of NLP constraints to be nullified:
c k (y) = =x k+1 − x k − hf(t k , y k , u k )
(7.15)
These constraints, which ensure the equation of motion to be approximately
satisfied, are then coupled with the fixed-event ones and the path constraints, to
construct a continuous trajectory and to respect the requested bounds at the grid
points.
In collocation methods the choice of the interval size is vital because it influences
the accuracy of the interpolated function in representing the true trajectory. An
efficient procedure could be to compute initial estimates with a sparse grid and then
refine it progressively. This implementation makes this technique very robust to
imprecise initial guesses. Also in this method, the sparsity of the matrix shall be
exploited as much as possible to make the algorithm efficient.
The greater drawback of collocation methods is that for problems dominated by
highly non-linear dynamics, a very dense grid is needed to compute an accurate
solution which, when integrated forward for validation, leads to small errors in
the final state. This problem arises from the finite-difference approximation of the
dynamics, as in Eq. (7.14) for an Euler scheme, and from the parametrisation of the
shape. However, a dense grid translates into an expensive matrix inversion during
the NLP subproblem, leading to the degradation of the computational performance.
Pseudospectral methods are a special class of direct collocation where the
optimal control problem is transcribed by parameterising the state and control using
global polynomials and collocating the differential-algebraic equations using the
nodes obtained from a Gaussian quadrature [79, 80]. The terms pseudospectral and
orthogonal collocation are used interchangeably in the literature.
7.3 Combinatorial and Network Optimisation
Until now, all optimisation problems and variables have been continuous, that is,
each design vector has consisted of a set of variables composed of possible values
within a specified range. In this section ‘combinatorial optimisation’ problems
shall be discussed, where some or all of the design variables are restricted to a
discrete set, most commonly binary integers, but also non-negative integers. This
section will also discuss problems with a finite number of possibilities, namely,
problems formulated to find a maximum or minimum of one or more functions, with
many variables, which can be limited by a series of equality constraints, inequality
constraints and bounds. All of these problems are ‘linear problems’ or can be
reformulated as such with the inclusion of some constriction on one or more of the