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} \tag{MINLP} \begin{aligned} \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} \tag{MILP(i)} \begin{aligned} \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} \tag{NLP(i)} \begin{aligned} \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





References

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

ph/ph1001