Here is a very small geometric problem:
Given \(n\) points in 2d space, find the smallest triangle that contains all these points.
 |
| Find the smallest triangle containing all points. |
This looks like a simple problem. Somewhat to my surprise, my attempt here does not bear that out.
 |
| Typical shape |
Often I see people who have read or heard about NP-completeness dismissing a MIP formulation even before trying. This is certainly a misunderstanding of complexity theory. To be clear:
Complexity theory says (almost) nothing about how fast a particular MIP solver can solve your particular problem on your particular dataset.
I think we can even drop the "almost." So, let's not fall into this trap, and just try things out!
In [1] a simple problem is stated:
Given \(n=40,000\) numbers, select a subset that sums up to 100,000 or as closely as possible.
A small MIP model can do the job:
| MIP model |
|---|
| \[\begin{align}\min\>&\left|\mathit{\color{darkred}{Deviation}}\right| \\ & \sum_i \color{darkblue}v_i \cdot \color{darkred}x_i = \mathit{\color{darkblue}{Target}} + \mathit{\color{darkred}{Deviation}}\\ & \color{darkred}x_i \in \{0,1\}\end{align} \] |
In [1] the following problem is posted:
Consider \(N\) points and a minimum distance \(\mathit{\color{darkblue}{MinDist}}\). Pick as many points as possible from this collection, such that the distances between the selected points is at least \(\mathit{\color{darkblue}{MinDist}}\).
A small data set can look like:---- 9 PARAMETER p coordinates of points x y i1 17.175 84.327 i2 55.038 30.114 i3 29.221 22.405 i4 34.983 85.627 i5 6.711 50.021 i6 99.812 57.873 i7 99.113 76.225 i8 13.069 63.972 i9 15.952 25.008 i10 66.893 43.536 i11 35.970 35.144 i12 13.149 15.010 i13 58.911 83.089 i14 23.082 66.573 i15 77.586 30.366 i16 11.049 50.238 i17 16.017 87.246 i18 26.511 28.581 i19 59.396 72.272 i20 62.825 46.380 i21 41.331 11.770 i22 31.421 4.655 i23 33.855 18.210 i24 64.573 56.075 i25 76.996 29.781 i26 66.111 75.582 i27 62.745 28.386 i28 8.642 10.251 i29 64.125 54.531 i30 3.152 79.236 i31 7.277 17.566 i32 52.563 75.021 i33 17.812 3.414 i34 58.513 62.123 i35 38.936 35.871 i36 24.303 24.642 i37 13.050 93.345 i38 37.994 78.340 i39 30.003 12.548 i40 74.887 6.923 i41 20.202 0.507 i42 26.961 49.985 i43 15.129 17.417 i44 33.064 31.691 i45 32.209 96.398 i46 99.360 36.990 i47 37.289 77.198 i48 39.668 91.310 i49 11.958 73.548 i50 5.542 57.630
The matrix balancing problem can be described as [1]: find a non-negative matrix \(\color{darkred}A_{i,j}\), that is as close as possible to \(\color{darkblue}A^0_{i,j}\), while observing given row and column totals and a given sparsity pattern. Or, mathematically,
| Matrix Balancing Problem |
|---|
| \[\begin{align}\min_{\color{darkred}A}\>&{\bf{dist}}(\color{darkred}A,\color{darkblue}A^0)\\ & \sum_i \color{darkred}A_{i,j} = \color{darkblue}c_j && \forall j\\ & \sum_j \color{darkred}A_{i,j} = \color{darkblue}r_i && \forall i \\&\color{darkred}A_{i,j}=0 &&\forall i,j|\color{darkblue}A^0_{i,j}=0\\ &\color{darkred}A_{i,j}\ge 0 \end{align} \] |
| Assignment problem |
|---|
| \[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\cdot\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j}=1 && \forall i \\ & \sum_i \color{darkred}x_{i,j}=1 && \forall j \\ & \color{darkred}x_{i,j} \in \{0,1\} \end{align}\] |
Excuses for the lame title.
index 0 1 2 3 4value 2 1 2 0 0
