Numbrix puzzle via TSP

 In [1], I demonstrated a small and rather elegant MIP model to solve Numbrix puzzles. Here is the comment by Austin Buchanan:

It would also be interesting to see how this compares to an MTZ-like model. And how well the two models scale to larger grids.

The Miller-Tucker-Zemlin [2,3] formulation for the Traveling Salesman Problem (TSP) starts with a standard assignment problem, and then adds some sub-tour elimination constraints. From [3]:

Note:  here \(\color{darkblue}p\ge \color{darkblue}n\). This 1960 paper has some interesting computational tests. Many runs ended with: "the machine was stopped after over 250 pivot steps had failed to produce the solution."

Numbrix puzzle via MIP

The puzzle of numbrix [1,2] is simple to state.

• We have a 9x9 board with 81 cells. 
• We need to fill each cell with a unique integer value between 1 and 81.
• There are some prefilled cells.
• We should be able to start with the cell containing value 1 and then following a path (only going one up, down, left or right) to the next values and thus eventually arriving at the cell with value 81.  

Example

Below is an example of an input (the "given" cells) and a solution. The colors may help to see that we have a path from the cell with value 1 to the cell with value 81.

Of course, we want to see if we can create a MIP model for this.

GAMS + R Markdown scripting

In [1] I discussed a small script that exported GAMS data to R for plotting. Here I expand on that and show how we can use R Markdown [2] to generate documents that contain GAMS data and results. Here we have just a small example with just a parameter. But it is easy to see that this can also be used with larger models, where we have a document built around more complex model results. 

R Markdown can handle as input text, R code, R graphics and LaTeX math (among others). Output can be HTML, PDF (via LaTeX), and DOCX (MS Word).

GAMS + R scripting

 I like to automate things. That means in practice: I write scripts. I prefer to spend a little more time to develop a script, basically for two reasons:

• A script can be executed again with little or no effort.
• A script serves as documentation. 

This helps to make things reproducible.

Here is a setup I often use for post-processing GAMS results with R. 

Modeling a simple implication

From [1]:

How to model:  

if \(\color{darkred}\delta=0\) then \(\color{darkred}x=0\) else \(\color{darkred}x=\color{darkred}x\)

where \(\color{darkred}\delta\in \{0,1\}\) is a binary variable and \(\color{darkred}x\ge 0\) is a non-negative continuous variable. 

The else part looks strange, but it is meant to indicate: unrestricted. So better is to just drop the else part:

if \(\color{darkred}\delta=0\) then \(\color{darkred}x=0\)

Let's list some possible formulations. 

Electronic Amoeba for solving TSPs?

Abstract

Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.

Picture of the electronic amoeba (from [2])

"Electronic amoeba" sounds awful. Furthermore, the paper talks about "legal solutions". Now the lawyers even get involved... 

 

References

1. 'Electronic amoeba' finds approximate solution to traveling salesman problem in linear time, https://www.sciencedaily.com/releases/2020/12/201210112050.htm
2. Kenta Saito, Masashi Aono and Seiya Kasai, Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem, https://www.nature.com/articles/s41598-020-77617-7

 

Directed vs undirected networks in math programming models

Many practical optimization models contain some network structures. In virtually all cases, these networks are modeled as directed graphs. I.e., between nodes \(i\) and \(j\), we consider arcs \(i \rightarrow j\) and \(j \rightarrow i\). In graph theory, it is very customary to talk about undirected graphs. In this case, there is just one link between nodes \(i\) and \(j\). Why am I using directed graphs, with two uni-directional arcs for each pair of nodes? I will try to answer this in this post.

As an example, let's consider the shortest path problem. This is really the same as a min-cost problem. I took the following data (from [1]):