This problem involves finding two min-max criteria filters to generate the highest score sum in a dataset.
I have a dataset, with 3 columns. x, y, score, with over 1 million of rows.
| x | y | score |
|---|---|---|
| 3.6 | 1.2 | -5 |
| 4.2 | 1.2 | -4 |
| 1.2 | 30.2 | 1 |
| 2.9 | 6.8 | 6 |
| 3.1 | 5.8 | 7 |
| 0.1 | 15.8 | 7 |
The data may or may not have a correlation.
I want to find a criteria filter of min/max on x and y that gives me the highest possible sum of scores.
This is how the query would look like in SQL.
SELECT SUM(score) FROM mytableWHEREx > xmin AND x < xmax ANDy > ymin AND y < ymaxWhat I am looking for is the optimal values for xmin, xmax, ymin och ymax
What kind of optimization method is needed to solve this problem? And exactly how would the implementation look like?
(Preferrably it would be implemented using Java or postgres sql.)
Advertisement
Answer
Not so easy. Here is my MIP model:
minimize sum(i, selected(i)*score(i))x(i) <= xmin + M*(xBetween(i)+xAbove(i))x(i) >= xmax - M*(xBetween(i)+xBelow(i))x(i) >= xmin - M*xBelow(i)x(i) <= xmax + M*xAbove(i)y(i) <= ymin + M*(yBetween(i)+yAbove(i))y(i) >= ymax - M*(yBetween(i)+yBelow(i))y(i) >= ymin - M*yBelow(i)y(i) <= ymax + M*yAbove(i)xBetween(i)+xAbove(i)+xBelow(i)=1yBetween(i)+yAbove(i)+yBelow(i)=1selected(i) <= xBetween(i)selected(i) <= yBetween(i)selected(i) >= xBetween(i)+yBetween(i)-1xmin <= xmaxymin <= ymaxxBetween(i),xAbove(i),xBelow(i) ∈ {0,1}yBetween(i),yAbove(i),yBelow(i) ∈ {0,1}selected(i) ∈ {0,1}The constants M are large enough numbers (I used the range of x or y data).
With some random numbers, I got:
---- 37 VARIABLE z.L = 30.940 objective---- 44 PARAMETER data data + results x y score x.betw y.betw selectedi1 1.717 6.611 -8.972i2 8.433 7.558 -9.880i3 5.504 6.274 -1.975i4 3.011 2.839 0.398 1.000 1.000 1.000i5 2.922 0.864 2.578 1.000 1.000 1.000i6 2.241 1.025 -5.485 1.000i7 3.498 6.413 -2.078 1.000i8 8.563 5.453 -4.480 1.000i9 0.671 0.315 -6.953i10 5.002 7.924 8.726i11 9.981 0.728 -1.547 1.000i12 5.787 1.757 -7.307 1.000i13 9.911 5.256 -2.279 1.000i14 7.623 7.502 -2.507i15 1.307 1.781 -4.630 1.000i16 6.397 0.341 8.967i17 1.595 5.851 -6.221 1.000i18 2.501 6.212 -4.050 1.000i19 6.689 3.894 -8.509 1.000i20 4.354 3.587 -1.973 1.000i21 3.597 2.430 -7.966 1.000i22 3.514 2.464 -2.322 1.000i23 1.315 1.305 -3.518 1.000i24 1.501 9.334 -6.157i25 5.891 3.799 -7.753 1.000i26 8.309 7.834 1.931i27 2.308 3.000 0.229 1.000 1.000 1.000i28 6.657 1.255 -9.099 1.000i29 7.759 7.489 5.662i30 3.037 0.692 8.915 1.000 1.000 1.000i31 1.105 2.020 1.929 1.000i32 5.024 0.051 2.147i33 1.602 2.696 -2.750 1.000i34 8.725 4.999 1.881 1.000i35 2.651 1.513 3.597 1.000 1.000 1.000i36 2.858 1.742 0.132 1.000 1.000 1.000i37 5.940 3.306 -6.815 1.000i38 7.227 3.169 3.138 1.000i39 6.282 3.221 0.478 1.000i40 4.638 9.640 -7.512i41 4.133 9.936 9.734i42 1.177 3.699 -5.438 1.000i43 3.142 3.729 3.513 1.000 1.000 1.000i44 0.466 7.720 5.536i45 3.386 3.967 8.649 1.000 1.000 1.000i46 1.821 9.131 -5.975i47 6.457 1.196 -4.057 1.000i48 5.607 7.355 -6.055i49 7.700 0.554 -5.073i50 2.978 5.763 2.930 1.000 1.000 1.000range(data) 9.516 9.885 19.614min(solution) 2.241 0.554max(solution) 3.498 5.851