I'm sorry if this isn't the right place to ask, but I'm wondering how I can build a model and solve it for the following problem:
http://puzzlor.com/2016-10_ShelterInPlace.html
We seek to find the best location to camp given that we need certain resources and want to minimize the distance travelled. I've considered an integer programming approach, but it would be a strange model, since the objective function would essentially enumerate all of the costs, and we'd have 100 binary decision variables, and our only constraint would be that only one of them is nonzero. Is there a better tool to use for this? For the scale of this problem, it is just as easy to brute force, but if it was larger, the brute force approach wouldn't scale favorably.
Thank you.
Does it have to be integer programming?
Here is my take; I did not test it but I guess it should work. It was kind of hurried, hopefully I did not miss anything.
You want to find a position $\vec{x} = (x, y)$ to build your camp. Say you have some resource at position $\vec{r} = (x_r, y_r)$. Then you will have to travel $2\,(|x_r - x| + |y_r - y|)$ units to go pick that resource and come back.
Notice also that you will want to pick only one spot for food, one for wood and another one for water; there is no much point in picking more than one for each resource. There are then only 9 possible values for your (wood, food, water) tuple.
For some specific (wood, food, water) tuple, you have that wood is at position $(w_x, w_y)$, food at $(f_x, f_y)$, and water at $(t_x, t_y)$. You can find your best spot for that specific combination by minimizing:
$$ d(x,y) = 2(|f_x-x| + |f_y-y|) + 4(|w_x - x| + |w_y-y|) + 6(|t_x-x| + |t_y-y|)$$
You do that for each one of the 9 combinations, and then you take the minimum among all of them. Hopefully it works, haha.
EDIT, Integer Solutions
It is true that you might get non integer solutions from this. Let's see how to fix that.
Let's analyze the one dimensional case first. Imagine there are two resource spots at $x_2=2$ and $x_8=8$. If we camp at $x=2$, we would have to walk $0$ units towards $x_2$ and back, yet $12$ units towards $x_8$ and back. We want to be closer to $x_8$, so we camp at, say, $x=5$. We now need to walk $6$ units towards $x_8$ and back, but now we also need to walk $6$ units towards $x_2$ and back, for a total of $12$ units. Notice that moving between $2$ and $8$ does nothing to minimize our distance metric; if we move one unit towards either of the points, we are moving one unit away from the other point. Therefore, the minimum lies in the segment that joins $x_2$ and $x_8$, including both points.
Now we add an additional resource at, say, $x_{10}=10$. If we were trying to minimize the travel distance between $x_2$ and $x_{10}$, any integer from $2$ to $10$ would do. However, we also have $x_8$. Since any point between $x_2$ and $x_{10}$ will give the same distance traveled between them, we will want to set camp at $x=8$ to minimize travel distance towards $x_8$ (see plot). Therefore, our absolute minimum is the median, as long as all distances are weighted equally. Now I'm thinking how the weights affect the distance metric, but my guess is that you will always have an easily computable integer solution. I'll get back to you once I figure out how to compute it.
In any case, since we can write our total distance as the sum of two independent sum of absolute value functions,
$$ d(x, y) = d_x(x) + d_y(y) $$
the minimum will be the point $(x,y)$ such that $x$ minimizes $d_x$ and $y$ minimizes $d_y$.
I'll get back to you once I figure out the weights problem.
EDIT, Handling Weights I found something here in the site. There is no proof, but I tested it a bit with Wolfram Alpha and it seems to work correctly. It's actually a median as it is defined for probability distributions (Wikipedia); if the weight is the probability of occurrence, then the median is the point that has ~half of the accumulated probability on each side of it. For example, say you want to minimize
$$ d_x = a_w\lvert w_x - x \rvert + a_f\lvert f_x - x \rvert + a_t\lvert t_x - x \rvert, $$
then you proceed as follows: you sort your vector $(w_x, f_x, t_x)$ in increasing order, and then you iterate through that vector summing up the corresponding weights until you hit or go past some value $\alpha$ that is the half of the total sum of weights. The weight that hits or goes past $\alpha$ is associated to the position or one of the positions that minimizes the sum of the absolute values.
For example, say we have $v = (w_x, f_x, t_x) = (10, 2, 8)$, with weights $a = (a_w, a_f, a_t) = (4, 2, 6)$. Then we sort $v$ to get $v' = (f_x, t_x, w_x) = (2, 8, 10)$, with corresponding weights $a' = (2, 6, 4)$. We compute $\alpha = (2 + 6 + 4)/2 = 6$. So we start iterating through $a'$ summing up weights until we reach or go past $6$. First we sum $2$; we are not there yet. Next we sum $6$; we just went past $6$, therefore our ideal $x$ position is the one that corresponds to weight $a_t = 6$, which is $t_x = 8$.
The overall algorithm would be therefore, for each one of the possible combinations, minimize $d_x$ and $d_y$ using the weighted sum procedure. Then take the solution that scores best among all of them and that is your global minimum.
Good luck, have a nice day!