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].

The Main Idea

In order to illustrate how NFP works, 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\).

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

Outline of the Algorithm

The NFS 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*}

Options Associated with Nonlinear Feasibility Pump


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

Was this helpful?
Please make sure you fill the comments section before sending.

Thank you for your comments.
Please contact us if you need any further support.