1. Home
2. Docs
3. Math blog
4. Primal heuristics
5. Nonlinear Feasibility Pump

# Nonlinear Feasibility Pump

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{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}

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):

1. $$\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}$$.
2. $$\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.

1. 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{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}
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$$.
2. Given a point $$(\hat{x}^i, \hat{y}^i)$$, the point $$(\overline{x}^i, \overline{y}^i)$$ is obtained by solving the NLP \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}

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
• HEUR_NL_FEASIBILITY_PUMP

### References

[1] P. Bonami, G. Cornu’ejols, A. Lodi, and F. Margot. A feasibility pump for mixed integer nonlinear programs. Mathematical Programming, 2009