user13724464
Reputation:
Minimal subset of vectors such that each component of their sum is greater than some threshold
Suppose we have a finite set S of vectors of length n with positive real values and a positive real number t. I want to find a minimal subset M of S such that each component of the sum of the vectors is greater than t.
For example, if I the following problem,
t = 10
S = [[8, 2], [5, 5], [4, 3], [3, 9]]
an optimal solution would consist of the 2 vectors
M = [[8, 2], [3, 9]]
since
[8, 2] + [3, 9] = [11, 11] > [10, 10]
and no single vector has each component greater than 10. There is not necessarily a unique optimal subset, or a subset which satisfies the criterion at all.
It seems to me that this problem may be related to integer linear programming, but does not seem to fit within its standard form. It may be the case that the problem is NP Hard, so I would also appreciate algorithms which try to approximate the solution.
Upvotes: 0
Views: 122
Answers (1)
Erwin Kalvelagen
Reputation: 16724
It seems to me that this problem may be related to integer linear programming, but does not seem to fit within its standard form
I think it can be trivially implemented as a MIP model:
Here x(i) indicates if vector i is selected.
The data and results can look like:
---- 33 PARAMETER t = 10
---- 33 PARAMETER S
j1 j2
i1 8 2
i2 5 5
i3 4 3
i4 3 9
---- 33 VARIABLE x.L select vectors
i1 1, i4 1
---- 33 VARIABLE numSelected.L = 2
Just for testing, I also generated a larger problem:
---- 29 PARAMETER t = 100.000
---- 29 PARAMETER S
j1 j2 j3 j4 j5 j6 j7 j8 j9 j10
i1 1.717 8.433 5.504 3.011 2.922 2.241 3.498 8.563 0.671 5.002
i2 9.981 5.787 9.911 7.623 1.307 6.397 1.595 2.501 6.689 4.354
i3 3.597 3.514 1.315 1.501 5.891 8.309 2.308 6.657 7.759 3.037
i4 1.105 5.024 1.602 8.725 2.651 2.858 5.940 7.227 6.282 4.638
i5 4.133 1.177 3.142 0.466 3.386 1.821 6.457 5.607 7.700 2.978
i6 6.611 7.558 6.274 2.839 0.864 1.025 6.413 5.453 0.315 7.924
i7 0.728 1.757 5.256 7.502 1.781 0.341 5.851 6.212 3.894 3.587
i8 2.430 2.464 1.305 9.334 3.799 7.834 3.000 1.255 7.489 0.692
i9 2.020 0.051 2.696 4.999 1.513 1.742 3.306 3.169 3.221 9.640
i10 9.936 3.699 3.729 7.720 3.967 9.131 1.196 7.355 0.554 5.763
i11 0.514 0.060 4.012 5.199 6.289 2.257 3.961 2.760 1.524 9.363
i12 4.227 1.347 3.861 3.746 2.685 9.484 1.889 2.975 0.746 4.013
i13 1.017 3.839 3.241 1.921 1.124 5.966 5.114 0.451 7.831 9.457
i14 5.965 6.073 3.625 5.941 6.799 5.066 1.593 6.569 5.239 1.244
i15 9.867 2.281 6.757 7.768 9.325 2.012 2.971 1.972 2.463 6.465
i16 7.350 0.854 1.503 4.342 1.869 6.927 7.630 1.548 3.894 6.954
i17 8.458 6.127 9.760 0.269 1.874 0.871 5.404 1.269 7.340 1.132
i18 4.884 7.956 4.920 5.336 0.106 5.439 4.511 9.753 1.838 1.635
i19 0.246 1.778 0.613 0.166 8.357 6.017 0.270 1.961 9.507 3.355
i20 5.943 2.592 6.406 1.552 4.600 3.933 8.055 5.410 3.907 5.578
i21 9.328 3.488 0.083 9.488 5.719 3.336 9.837 7.665 1.101 9.948
i22 5.803 1.664 6.434 3.443 9.123 9.001 0.163 3.686 6.644 5.934
i23 0.346 8.418 9.321 5.080 2.996 4.966 0.449 7.737 5.330 7.468
i24 7.201 6.316 1.149 9.712 7.067 9.863 8.548 6.214 7.013 7.009
i25 7.907 6.102 0.543 4.852 0.525 6.986 1.948 2.260 8.136 9.917
i26 7.507 7.183 0.006 2.639 8.238 8.195 8.604 2.127 4.568 0.384
i27 3.230 4.399 3.153 1.348 8.110 4.168 1.418 4.655 2.830 8.957
i28 0.644 4.146 3.416 4.683 6.427 6.436 3.376 1.008 9.058 2.174
i29 9.189 4.518 0.899 3.742 4.150 4.042 1.117 7.511 8.034 0.237
i30 4.809 2.786 9.016 0.176 6.810 9.509 9.002 8.988 8.745 3.910
i31 5.042 8.313 6.021 0.822 5.778 5.932 6.838 1.588 3.318 3.159
i32 5.199 3.638 1.678 6.831 5.054 5.762 7.198 6.837 0.198 8.398
i33 7.100 1.555 6.107 6.616 1.944 3.635 6.239 7.314 4.140 1.575
i34 0.125 0.102 9.520 9.767 9.663 8.563 1.416 0.497 5.530 1.840
i35 9.942 8.091 3.062 0.874 4.305 3.497 1.173 5.860 4.455 4.123
i36 9.145 2.138 2.242 5.423 6.311 3.274 1.488 9.291 2.510 0.626
i37 3.101 0.402 8.212 2.310 4.100 3.026 4.449 7.160 5.932 1.312
i38 1.612 3.156 5.721 2.687 0.364 6.864 6.746 3.321 7.599 1.768
i39 6.825 6.730 8.312 5.152 2.830 5.554 4.140 0.734 8.060 3.327
i40 0.847 5.722 0.221 7.420 9.051 5.608 4.728 7.176 5.130 8.871
i41 7.715 1.401 2.645 6.826 4.498 9.655 9.579 8.992 3.275 4.571
i42 5.962 8.786 1.707 6.336 7.716 5.694 0.277 8.110 2.789 4.333
i43 3.363 5.886 5.744 5.434 5.782 9.772 3.215 7.630 9.625 9.490
i44 2.559 3.249 2.148 1.740 7.313 2.702 7.585 6.174 2.910 7.407
i45 0.078 8.665 0.151 4.283 3.586 7.049 4.159 5.498 3.450 6.996
i46 9.335 4.693 2.136 5.108 3.657 9.354 0.680 5.039 3.924 2.049
i47 5.295 5.891 3.458 2.529 5.477 5.475 0.583 3.777 9.741 3.798
i48 1.563 4.723 3.970 2.055 6.273 0.035 5.040 0.022 5.214 8.361
i49 0.721 7.606 2.901 2.449 4.360 3.688 5.534 0.747 9.094 0.487
i50 8.204 7.930 6.595 3.918 4.132 8.657 9.753 5.724 3.140 4.550
i51 3.710 4.198 0.853 8.145 5.092 7.344 8.244 4.145 9.244 3.941
i52 4.443 6.955 6.767 5.715 1.735 6.043 5.860 7.278 2.462 1.421
i53 8.912 4.428 1.143 9.036 3.339 9.960 4.645 5.305 1.904 1.991
i54 6.449 7.991 5.864 9.716 4.911 3.725 8.272 8.209 0.313 9.252
i55 0.031 6.180 0.067 4.056 6.563 6.155 2.634 0.704 0.460 1.603
i56 4.525 1.689 5.716 8.587 0.359 3.554 3.379 4.865 2.594 8.912
i57 8.493 6.345 9.865 7.579 5.079 7.678 8.321 5.839 5.751 5.567
i58 6.036 9.771 5.541 9.350 4.132 8.064 0.008 4.553 4.192 0.157
i59 0.820 5.988 5.552 6.180 8.851 1.899 4.281 1.665 8.863 6.765
i60 8.633 0.928 9.965 6.168 0.008 6.089 1.737 3.112 7.289 0.847
i61 4.420 6.591 4.845 3.182 9.140 1.842 8.721 4.561 4.589 1.241
i62 1.038 2.349 3.402 8.731 8.448 8.229 4.805 9.138 9.293 1.081
i63 3.506 8.600 3.405 2.131 9.264 3.607 8.760 1.481 4.560 2.683
i64 2.968 1.155 3.998 9.118 2.516 1.030 1.463 3.863 0.464 0.264
i65 1.540 0.727 8.286 3.998 4.172 9.721 2.434 3.620 6.303 2.429
i66 1.011 4.059 4.791 1.449 5.097 8.853 0.555 5.074 7.641 9.790
i67 7.204 8.719 2.995 7.539 8.438 4.682 6.549 3.781 3.589 2.545
i68 2.555 4.506 9.449 3.355 0.485 8.065 7.326 9.200 3.316 2.098
i69 0.471 8.830 0.928 8.369 4.638 0.002 1.566 7.050 2.803 6.356
i70 5.800 9.621 5.142 5.903 5.675 0.299 9.689 5.938 0.596 5.441
i71 1.274 4.205 8.814 7.166 3.136 9.930 0.553 6.191 8.044 2.966
i72 9.589 6.948 6.314 6.160 5.230 1.410 8.367 8.921 6.965 3.118
i73 3.558 7.611 1.364 7.166 9.637 4.419 2.645 4.442 3.967 3.669
i74 6.213 8.597 7.550 9.008 4.380 0.691 9.386 8.440 9.504 5.794
i75 0.352 4.074 0.574 5.320 1.124 8.938 2.417 6.422 2.908 8.136
i76 1.861 5.007 9.388 6.816 1.852 8.729 1.650 4.308 7.717 9.781
i77 9.445 2.488 8.865 8.844 9.649 7.491 6.476 7.484 5.232 6.861
i78 6.911 8.656 7.958 2.176 5.896 9.226 6.029 0.357 9.111 5.650
i79 3.248 3.901 2.993 2.190 8.217 1.527 9.505 0.319 7.345 1.105
i80 4.878 3.610 2.164 9.237 4.500 9.711 0.963 4.789 7.222 4.332
i81 1.582 1.007 8.055 3.987 1.171 8.744 1.449 1.777 5.452 4.686
i82 9.092 7.231 1.664 3.276 5.813 5.775 6.276 0.267 1.294 0.641
i83 3.111 5.785 8.098 6.792 7.357 3.386 2.242 9.000 8.294 3.162
i84 9.522 2.567 6.261 9.713 9.621 4.253 1.054 0.771 6.441 3.122
i85 5.952 6.064 6.337 9.582 0.823 1.254 6.052 7.415 8.475 3.525
i86 6.414 8.957 3.882 2.734 9.704 3.462 4.096 9.399 6.029 8.995
i87 2.847 2.222 5.748 5.095 5.575 3.442 3.983 7.762 0.282 3.624
i88 7.558 4.749 0.762 0.975 3.297 2.006 0.908 4.488 4.628 8.120
i89 4.500 9.543 1.226 4.066 8.864 7.032 8.749 5.551 2.556 2.592
i90 3.551 1.369 8.071 3.260 4.288 0.090 2.243 6.607 2.874 1.311
i91 4.071 1.616 8.618 3.777 8.886 2.700 7.774 4.228 4.299 2.491
i92 3.818 0.710 7.156 7.029 0.702 9.685 2.700 3.181 8.834 5.862
i93 3.821 9.730 6.708 9.511 7.183 4.436 8.797 4.698 4.639 3.714
i94 1.183 9.654 8.435 7.213 9.644 3.646 7.683 3.325 5.421 1.384
i95 3.137 0.799 9.342 4.943 6.789 6.916 0.547 2.402 8.827 1.006
i96 6.784 1.014 0.428 7.535 9.870 0.148 1.469 9.910 1.322 0.854
i97 1.859 7.902 8.645 7.479 3.895 7.950 6.210 7.614 5.803 6.636
i98 0.821 5.669 4.432 3.283 3.306 1.229 6.179 5.339 1.441 3.923
i99 0.148 8.708 2.455 8.032 0.840 9.872 5.583 6.819 8.596 5.867
i100 0.395 9.129 5.425 2.210 9.256 7.928 7.394 6.777 5.012 4.311
---- 29 VARIABLE x.L select vectors
i24 1, i30 1, i42 1, i43 1, i50 1, i54 1, i57 1, i72 1, i74 1, i76 1, i77 1, i78 1, i83 1
i84 1, i86 1, i93 1, i97 1
---- 29 VARIABLE numSelected.L = 17
This model still solved in 1 second. I am sure there are larger instances that become more difficult to solve to optimality. But MIP solvers typically find good solutions very quickly, so in a sense, a MIP model can also be used as a heuristic: just stop earlier (before proving optimality).
Upvotes: 1
Related Questions
- Selecting such vector elements so that the sum of elements is exactly equal to the specified value
- subset which gives the least sum greater than or equal to a given number
- Formulating a constraint on the SUM of the magnitudes of a set of vectors in a constrained optimization
- Fewest subsets with sum less than N
- R: from a vector, list all subsets of elements so their sum just passes a value
- How to find a combination of elements that sum up just above threshold value
- Minimum of subset of vector (c++)
- Sum of Multiples of Numbers Greater Or Equal to Target, Optimization
- Subset whose sum is the smallest sum over a specific threshold
- Linear algorithm to find minimum subset sum over a threshold