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

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

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{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\).
  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{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


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