Fusion and the art of harvesting potatoes

Week 42 in Denmark was "kartoffelferie" - fall school vacation originally designed to allow children help with the potato harvest on the farm. The vacation is still present even though kids no longer collect potatoes, except for...

... Lærke. Lærke has her own little potato field arranged in an $n\times n$ grid. For some squares of the grid she knows the exact number of potatoes that can be harvested from that square, between $0$ and $3$. She wants to design a round trip around her little field so that each of those squares will be passed by just the right number of times to pick the potatoes, one on each pass. Other squares can be passed by any number of times. A picture with a sample layout and its solution is worth a thousand words:

Now Lærke notices that she can easily write a mixed-integer model of her problem. She will associate a binary variable with each edge of the grid, to indicate if it appears in the tour, and then needs to ensure that:

• (1) every vertex of the grid meets either 0 or 2 of the tour edges,
• (2) every square with $i$ potatoes has exactly $i$ tour edges on its boundary.

That will not necessarily give Lærke one closed tour, but possibly a disjoint union of cycles. A subtour elimination scheme similar to the one used for TSP could be built on top to get a single tour. Luckily, Lærke is not so worried about that - her basket is quite small so she is happy to make a few trips anyway. What she is much more interested in is that each of the constraints (1) and (2) can be implemented basically as a one-liner in Fusion by appropriate stacking and slicing and that she can see it all and try it out live here:

https://solve.mosek.com/fusion.html?ex=slitherlink

Finally, as much as Lærke is just our imaginary MIP user in the food industry, the puzzle actually exists and is known as Slitherlink.

Bon appétit!

(images by GLmathgrant, under CC BY-SA 3.0, from Wikipedia)