Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems

Abstract

In this paper, we generalize the extended supporting hyperplane algorithm for a convex continuously differentiable mixed-integer nonlinear programming problem to solve a wider class of nonsmooth problems. The generalization is made by using the subgradients of the Clarke subdifferential instead of gradients. Consequently, all the functions in the problems are assumed to be locally Lipschitz continuous. The algorithm is shown to converge to a global minimum of an MINLP problem if the objective function is convex and the constraint functions are $f^{\circ }$-pseudoconvex. With some additional assumptions, the constraint functions may be $f^{\circ }$-quasiconvex.

Appendix: The facility layout problem: P3

In this problem, 7 departments should be placed in a facility. The width and the height of the facility are $w_F=8.54$ and $h_F=13$, respectively. Parameters for the problem are in Table 3. The decision variables and the indices of the problem are:

• $i=\text {indexes of the departments:}\, 1,2,\ldots ,7$.

• $x_i,y_i=$ coordinates of the center of department i.

• $w_i =$ width of the department i.

• $h_i =$ height of the department i.

• $X_{ij},Y_{ij} =$ auxiliary variables.

The problem reads

$$\begin{aligned} \min&\sum _{i=1}^{6} \left| x_i-x_{i+1} \right| +\left| y_i-y_{i+1} \right| \end{aligned}$$

(7)

$$\begin{aligned} \mathrm{s.t.}&h_iw_i \ge a_i, \quad i=1,2,\ldots ,7 \end{aligned}$$

(8)

$$\begin{aligned}&x_i+\frac{1}{2} w_i \le w_F, \quad i=1,2,\ldots ,7 \end{aligned}$$

(9)

$$\begin{aligned}&-x_i+\frac{1}{2}w_i \le 0, \quad i=1,2,\ldots ,7 \end{aligned}$$

(10)

$$\begin{aligned}&y_i+\frac{1}{2} h_i \le h_F, \quad i=1,2,\ldots ,7 \end{aligned}$$

(11)

$$\begin{aligned}&-y_i+\frac{1}{2}h_i \le 0, \quad i=1,2,\ldots ,7 \end{aligned}$$

(12)

$$\begin{aligned}&\frac{1}{2}(w_i+w_j)-(x_i-x_j) \le w_{F}(X_{ij}+Y_{ij}), \quad 1 \le i< j \le 7 \end{aligned}$$

(13)

$$\begin{aligned}&\frac{1}{2}(w_i+w_j)-(x_j-x_i) \le w_{F}(1+X_{ij}-Y_{ij}), \quad 1 \le i< j \le 7 \end{aligned}$$

(14)

$$\begin{aligned}&\frac{1}{2}(h_i+h_j)-(y_i-y_j) \le h_{F}(1-X_{ij}+Y_{ij}), \quad 1 \le i< j \le 7 \end{aligned}$$

(15)

$$\begin{aligned}&\frac{1}{2}(h_i+h_j)-(y_j-y_i) \le h_{F}(2-X_{ij}-Y_{ij}), \quad 1 \le i< j \le 7 \end{aligned}$$

(16)

$$\begin{aligned}&x_1-x_2 \le 0 \end{aligned}$$

(17)

$$\begin{aligned}&y_1-y_2 \le 0 \end{aligned}$$

(18)

$$\begin{aligned}&w_{i}^{low} \le w_{i} \le w_{i}^{up}, \quad i=1,2,\ldots ,7 \end{aligned}$$

(19)

$$\begin{aligned}&h_{i}^{low} \le h_{i} \le h_{i}^{up}, \quad i=1,2,\ldots ,7 \end{aligned}$$

(20)

$$\begin{aligned}&X_{ij} \in \left\{ 0,1 \right\} , \quad 1 \le i< j \le 7 \end{aligned}$$

(21)

$$\begin{aligned}&Y_{ij} \in \left\{ 0,1 \right\} , \quad 1 \le i< j \le 7 \end{aligned}$$

(22)

Table 3 Parameters of the problem (P3)

The objective is to minimize the distance between consecutive departments. Constraints (7) define the minimum areas of the departments. Constraints (8)–(11) make sure the departments are located inside the facility. Constraints (12)–(15) prevent the overlapping of the departments. Constraints (16)–(17) erase symmetric solutions.