## Wednesday, August 26, 2020

### MINLP vs MIQCP

In [1] a small non-convex MINLP is stated. The elements are:
• We have binary variables $$x_i \in \{0,1\}$$ for $$i=1,\dots,52$$
• The data is comprised of three arrays: $$a_i$$, $$b_i$$ and $$c_i$$
• We want to minimize the following objective: \begin{align} - &\left(\frac{1166}{2000} \sum_i a_i \cdot x_i\right) \times \\ & \left(\frac{1}{2100} \sum_i b_i \cdot x_i + 0.05\right) \times \\ & \left(\frac{1}{1500} \sum_i c_i \cdot x_i + 1.5\right)\end{align}
• Of the first four elements $$x_i$$, only one has the value 1, and the other three are 0. Same thing for the second, third, etc. groups of four.

#### Data

----     66 SET i  items

i1 ,    i2 ,    i3 ,    i4 ,    i5 ,    i6 ,    i7 ,    i8 ,    i9 ,    i10,    i11,    i12,    i13,    i14,    i15
i16,    i17,    i18,    i19,    i20,    i21,    i22,    i23,    i24,    i25,    i26,    i27,    i28,    i29,    i30
i31,    i32,    i33,    i34,    i35,    i36,    i37,    i38,    i39,    i40,    i41,    i42,    i43,    i44,    i45
i46,    i47,    i48,    i49,    i50,    i51,    i52

----     66 SET g  groups

group1 ,    group2 ,    group3 ,    group4 ,    group5 ,    group6 ,    group7 ,    group8 ,    group9 ,    group10
group11,    group12,    group13

----     66 SET group  grouping of items

i1          i2          i3          i4          i5          i6          i7          i8          i9

group1          YES         YES         YES         YES
group2                                                          YES         YES         YES         YES
group3                                                                                                          YES

+         i10         i11         i12         i13         i14         i15         i16         i17         i18

group3          YES         YES         YES
group4                                              YES         YES         YES         YES
group5                                                                                              YES         YES

+         i19         i20         i21         i22         i23         i24         i25         i26         i27

group5          YES         YES
group6                                  YES         YES         YES         YES
group7                                                                                  YES         YES         YES

+         i28         i29         i30         i31         i32         i33         i34         i35         i36

group7          YES
group8                      YES         YES         YES         YES
group9                                                                      YES         YES         YES         YES

+         i37         i38         i39         i40         i41         i42         i43         i44         i45

group10         YES         YES         YES         YES
group11                                                         YES         YES         YES         YES
group12                                                                                                         YES

+         i46         i47         i48         i49         i50         i51         i52

group12         YES         YES         YES
group13                                             YES         YES         YES         YES

----     66 PARAMETER data

a           b           c

i1      251.000     179.000     179.000
i2      179.000     251.000     179.000
i3      215.000     215.000     118.000
i4      251.000                 179.000
i5       63.000      45.000      45.000
i6       45.000      63.000      45.000
i7       54.000      54.000      30.000
i8       63.000                  45.000
i9       47.000      34.000      34.000
i10      34.000      47.000      34.000
i11      40.000      40.000      22.000
i12      47.000                  34.000
i13     141.000     101.000     101.000
i14     101.000     141.000     101.000
i15     121.000     121.000      67.000
i16     141.000                 101.000
i17      47.000      34.000      34.000
i18      34.000      47.000      34.000
i19      40.000      40.000      22.000
i20      47.000                  34.000
i21      94.000      67.000      67.000
i22      67.000      94.000      67.000
i23      81.000      81.000      44.000
i24      94.000                  67.000
i25      47.000      34.000      34.000
i26      34.000      47.000      34.000
i27      40.000      40.000      22.000
i28      47.000                  34.000
i29     157.000     108.000     108.000
i30     108.000     157.000     108.000
i31     133.000     133.000      71.000
i32     157.000                 108.000
i33     126.000      85.000      85.000
i34      85.000     126.000      85.000
i35     106.000     106.000      56.000
i36     126.000                  85.000
i37     126.000      85.000      85.000
i38      85.000     126.000      85.000
i39     106.000     106.000      56.000
i40     126.000                  85.000
i41     110.000      74.000      74.000
i42      74.000     110.000      74.000
i43      92.000      92.000      49.000
i44     110.000                  74.000
i45     110.000      74.000      74.000
i46      74.000     110.000      74.000
i47      92.000      92.000      49.000
i48     110.000                  74.000
i49      63.000      40.000      40.000
i50      40.000      63.000      40.000
i51      52.000      52.000      27.000
i52      63.000                  40.000


The set group was populated using the GAMS statement:

 set group(g,i) 'grouping of items'; group(g,i) = 1+floor((ord(i)-0.5)/4)=ord(g);

The term 0.5 is to make sure we don't take the floor of integer values (the floor function can then deliver different results depending on the very last bit - possibly dangerous when we deal with floating-point computations).

#### Direct MINLP formulation

A direct MINLP model formulation can look like:

MINLP model A
\begin{align}\min\> - &\left(\frac{1166}{2000} \sum_i \color{darkblue}a_i \cdot \color{darkred}x_i\right) \times \\ & \left(\frac{1}{2100} \sum_i \color{darkblue}b_i \cdot \color{darkred}x_i + 0.05\right) \times \\ & \left(\frac{1}{1500} \sum_i \color{darkblue}c_i \cdot \color{darkred}x_i + 1.5\right)\\ & \sum_{i|\color{darkblue}{\mathit{group}}(g,i)} \color{darkred}x_i = 1 &&\forall g\\ & \color{darkred}x_i \in \{0,1\}\end{align}

The solution can look like:

----     89 VARIABLE x.L

i1  1.000,    i5  1.000,    i9  1.000,    i14 1.000,    i17 1.000,    i21 1.000,    i25 1.000,    i29 1.000
i34 1.000,    i38 1.000,    i41 1.000,    i46 1.000,    i49 1.000

----     89 VARIABLE z.L                   =     -889.346  obj


Of course, we see 13 items selected (one for each group of 4).

This is a small model, so we can try a few different global and local solvers.

SolverTypeObjTimeNodes
Couenneglobal-889.346318.259972
Baronglobal-889.34637.18389
AntigoneglobalStuck in preprocessing
Bonminlocal-889.3463892280

Interesting:
• Antigone has problems during preprocessing
• The local solver Bonmin finds the global optimum but is somewhat slow

#### Alternative formulation

There is an alternative formulation. We can substitute out the linear parts of the objective function. This will make the model larger (extra variables and equations), but less non-linear (e.g. in terms of non-linear variables).

MINLP model B
\begin{align}\max & \prod_k\color{darkred}v_k \\ & \color{darkred}v_1 = \frac{1166}{2000} \sum_i \color{darkblue}a_i \cdot \color{darkred}x_i \\ & \color{darkred}v_2 = \frac{1}{2100} \sum_i \color{darkblue}b_i \cdot \color{darkred}x_i + 0.05 \\ & \color{darkred}v_3 = \frac{1}{1500} \sum_i \color{darkblue}c_i \cdot \color{darkred}x_i + 1.5\\ & \sum_{i|\color{darkblue}{\mathit{group}}(g,i)} \color{darkred}x_i = 1 &&\forall g\\ & \color{darkred}x_i \in \{0,1\}\end{align}

This formulation has more linear constraints, but in return, we get a much simpler non-linear objective. Note that we also got rid of the minus sign in the objective. This was probably put in there to convert the problem to a minimization problem.

The solution is obviously the same:

----    122 VARIABLE x.L

i1  1.000,    i6  1.000,    i9  1.000,    i13 1.000,    i17 1.000,    i22 1.000,    i25 1.000,    i29 1.000
i33 1.000,    i38 1.000,    i42 1.000,    i46 1.000,    i49 1.000

----    122 VARIABLE v.L  obj factors

obj1 713.592,    obj2   0.582,    obj3   2.140

----    122 VARIABLE z.L                   =      889.346  obj


Some of the solvers perform better on this model:

SolverTypeObjTimeNodes
Couenneglobal889.34635.14398
Baronglobal889.34639.5309
Antigoneglobal889.346325
Bonminlocal889.34631053336

Couenne and especially Antigone do much better on this formulation.

Gurobi can solve non-convex quadratic models, so it is interesting to reformulate the problem into a form that Gurobi can digest.

MIQCP model
\begin{align}\max\> & \color{darkred}v_1 \cdot \color{darkred}v_{23} \\& \color{darkred}v_{23} = \color{darkred}v_{2} \cdot \color{darkred}v_{3}\\ & \color{darkred}v_1 = \frac{1166}{2000} \sum_i \color{darkblue}a_i \cdot \color{darkred}x_i \\ & \color{darkred}v_2 = \frac{1}{2100} \sum_i \color{darkblue}b_i \cdot \color{darkred}x_i + 0.05 \\ & \color{darkred}v_3 = \frac{1}{1500} \sum_i \color{darkblue}c_i \cdot \color{darkred}x_i + 1.5\\ & \sum_{i|\color{darkblue}{\mathit{group}}(g,i)} \color{darkred}x_i = 1 &&\forall g\\ & \color{darkred}x_i \in \{0,1\}\end{align}

Note that this requires the Gurobi option nonConvex=2.

SolverTypeObjTimeNodes
Gurobiglobal889.34630.266985

Gurobi solves this model very quickly, although the node count is not that low.

#### Conclusion

Even this small MINLP model has some interesting wrinkles and reformulations.