One of the primal heuristics used within Octeract Engine is the Nonlinear Feasibility Pump (NFP). It offers a way of obtaining feasible points for MINLPs. The implementation is based on the ideas introduced in [1].
Let’s consider the problem
\[\begin{equation}
\begin{aligned}
\textrm{(MINLP)}: \quad \min \quad & f(x,y) \\
\textrm{s.t.} \quad & g(x,y) \le b \\
& x \in \mathbb{Z}^{n_1} \\
& y \in \mathbb{R}^{n_2}
\end{aligned}
\end{equation}\]
where \(f: \mathbb{R}^{n_1} \times \mathbb{R}^{n_2} \rightarrow \mathbb{R}\) and \(g: \mathbb{R}^{n_1} \times \mathbb{R}^{n_2} \rightarrow \mathbb{R}^m\) are (nonlinear) smooth functions. Note that we assume variable bounds are included in the constraints \(g(x,y) \le b\).
The NFP iteratively constructs two co-dependent sequences of points that are capable of converging to a feasible solution of (MINLP):
- \(\big\{(\overline{x}^i, \overline{y}^i)\big\}_{i \ge 0}\) – a sequence of points satisfying the constraints \(g(x,y) \le b\) of (MINLP) but not necessarily the integrality constraints \(x \in \mathbb{Z}^{n_1}\).
- \(\big\{(\hat{x}^{i+1}, \hat{y}^{i+1})\big\}_{i \ge 0}\) – a sequence of points satisfying the integrality constraints \(x \in \mathbb{Z}^{n_1}\) of (MINLP) but not necessarily the constraints \(g(x,y) \le b\).
These sequences are constructed in the following way.
- Given a point \((\overline{x}^{i-1}, \overline{y}^{i-1})\), the point \((\hat{x}^i, \hat{y}^i)\) is obtained by solving the MILP \begin{equation} \begin{aligned} \textrm{(MILP(i))}: \quad \min \quad & \sum_{j=1}^{n_1} \big| x_j-\overline{x}_j^{i-1} \big| \\ \textrm{s.t.} \quad & g(\overline{x}^k,\overline{y}^k) + J_g(\overline{x}^k,\overline{y}^k) \bigg( \begin{pmatrix} x \\ y \end{pmatrix} – \begin{pmatrix} \overline{x}^k \\ \overline{y}^k \end{pmatrix} \bigg) \le b \quad \\&\forall k = 0, \dots, i-1 \\ & x \in \mathbb{Z}^{n_1} \\ & y \in \mathbb{R}^{n_2} \end{aligned} \end{equation}
where \(J_g(\overline{x}^k,\overline{y}^k)\) is the Jacobian matrix of \(g\) at the point \((\overline{x}^k,\overline{y}^k)\). Note, (MILP(i)) uses an outer approximation of the region defined by the constraints \(g(x,y) \le b\). - Given a point \((\hat{x}^i, \hat{y}^i)\), the point \((\overline{x}^i, \overline{y}^i)\) is obtained by solving the NLP \begin{equation} \begin{aligned} \textrm{(NLP(i))}: \quad \min \quad & \sum_{j=1}^{n_1} \big( x_j-\hat{x}_j^i \big)^2 \\ \textrm{s.t.} \quad & g(x,y) \le b \\ & x \in \mathbb{R}^{n_1} \\ & y \in \mathbb{R}^{n_2} \end{aligned} \end{equation}
The NFP algorithm can be outlined as follows:
\[\begin{equation*} \begin{aligned} & \text{Compute } (\overline{x}^0,\overline{y}^0) = \text{ a feasible point of the continuous relaxation of (MINLP)} \\ & \textbf{FOR } i = 1 \rightarrow \text{MaxIters}: \\ & \quad\quad \textbf{IF } (\overline{x}^{i-1}, \overline{y}^{i-1}) \text{ is a feasible point of (MINLP) } \textbf{OR} \text{ (MILP(i)) is infeasible} \\ & \quad\quad\quad\quad \textbf{STOP} \\ & \quad\quad \text{Compute } (\hat{x}^i, \hat{y}^i) \text{ from } (\overline{x}^{i-1}, \overline{y}^{i-1}) \text{ by solving (MILP(i))} \\ & \quad\quad \text{Compute } (\overline{x}^i, \overline{y}^i) \text{ from } (\hat{x}^i, \hat{y}^i) \text{ by solving (NLP(i))} \\ \end{aligned} \end{equation*}\]
Associated options
References
[1] P. Bonami, G. Cornu’ejols, A. Lodi, and F. Margot. A feasibility pump for mixed integer nonlinear programs. Mathematical Programming, 2009