- 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'; |
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.
| Solver | Type | Obj | Time | Nodes |
|---|---|---|---|---|
| Couenne | global | -889.3463 | 18.25 | 9972 |
| Baron | global | -889.3463 | 7.18 | 389 |
| Antigone | global | Stuck in preprocessing | ||
| Bonmin | local | -889.3463 | 89 | 2280 |
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:
| Solver | Type | Obj | Time | Nodes |
|---|---|---|---|---|
| Couenne | global | 889.3463 | 5.1 | 4398 |
| Baron | global | 889.3463 | 9.5 | 309 |
| Antigone | global | 889.3463 | 2 | 5 |
| Bonmin | local | 889.3463 | 105 | 3336 |
Non-convex quadratic 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.
| Solver | Type | Obj | Time | Nodes |
|---|---|---|---|---|
| Gurobi | global | 889.3463 | 0.26 | 6985 |
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.
References
- R Binary Integer Optimization with Groups, https://stackoverflow.com/questions/63584707/r-binary-integer-optimization-with-groups
No comments:
Post a Comment