2
$\begingroup$

I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com: Lumosity Pet Detective

The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)

Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?

My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.

My best ansatz so far is this:

An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.

Let $x_{i,j,k}$ be the number of times animal $k\in\{1,...,n\}$ is transported from node i to node j. Let $x_{i,j,0}$ be the number of times the car drives from node i to node j. Let $s_k$ be animal k's node, and $t_k$ be animal k's home node. Let $s_0$ the car's node.

From the s-t-flow networks follows:

$\sum_i x_{l,i,k}-x_{i,l,k}=0,\forall l\notin\{s_k,t_k\},\forall k\in\{1,...,n\}$

$\sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,\forall k\in\{1,...,n\}$

$\sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,\forall k\in\{1,...,n\}$

$x_{i,j,k} \in \mathbb{N}_0, \forall i,j,k$

Since an animal can't travel without the car: $x_{i,j,0} \geq x_{i,j,k}, \forall k\in\{1,...,n\}$

And thus the objective becomes: min $\sum_{i,j} x_{i,j,0}$

The restrictions for the car:

$\sum_i x_{l,i,0}-x_{i,l,0}\leq 0,\forall l\notin\{s_0\}$

$\sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$

Now all that is missing, is the restriction on the car's capacity. How would one do that?

$\endgroup$

1 Answer 1

1
$\begingroup$

PanicSheep,

Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:

http://www.sampledsystems.com/using-solverstudio-for-linear-programming/

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .