Monday, January 31, 2022

Is a heuristic a solver?

Can we call a heuristic (especially a meta-heuristic) a solver? I am not so sure.

Warning: this is somewhat of an opinionated rant. Many of you may not agree.

The name "solver" seems to imply that the underlying algorithm knows when an optimization problem is solved. By that I mean: it can stop at some stage and report "solved". Meta-heuristics typically don't have a clue about optimality, and just keep on churning until hitting some form of time or iteration limit. (One could devise some stopping criteria basic on stochastic reasoning, but that is not often used in meta-heuristics).

So my proposal is:

Heuristics (including meta-heuristics) should not be called solvers. They don't know when a problem is solved.

Tuesday, January 25, 2022

A different coloring problem

In [1] the following problem is proposed:

  • Consider a complete (undirected) graph,
  • where each arc has a weight.
  • Given a collection of colors, color each node,
  • such that the sum of the weights of arcs with same-colored nodes is minimized.
  • We can assume some sparsity in the weights. 

The user expects the number of nodes to be between 20 and 50, and there are just a small number of colors.

Minimize weights for the colored arcs

The picture shows a complete graph (all nodes have a direct arc to each other) with 10 nodes. The optimal coloring of nodes minimizes the sum of weights along the colored edges. An edge is colored if the two incident nodes have the same color. 

Sunday, January 23, 2022

Coloring the US county map

A famous result in graph theory is that we can color a planar graph with just four colors [1]. The MIP model for coloring a graph is really simple. Let's try this with a relatively large data set: the map of US counties. We'll see that there are some hurdles on the way.

Building block: MIP model for coloring a graph

The problem is as follows: we want to assign a color to each node such that nodes connected by an arc don't have the same color. The objective is to minimize the number of different colors. For the MIP model we use an assignment variable:  \[\color{darkred}x_{n,c} = \begin{cases}1 & \text{if node $n$ gets color $c$} \\  0 & \text{otherwise}\end{cases}\] To keep track of the colors we have: \[\color{darkred}u_c = \begin{cases}1 & \text{color $c$ is used for some nodes} \\ 0 & \text{otherwise}\end{cases}\]

The MIP model can look like:

MIP Model
\[\begin{align} \min & \sum_c \color{darkred}u_c \\ & \sum_c \color{darkred}x_{n,c}=1 &&\forall n \\ & \color{darkred}x_{i,c}+\color{darkred}x_{j,c} \le \color{darkred}u_c && \forall \color{darkblue}{\mathit{arc}}_{i,j}, c \\ & \color{darkred}u_c \le \color{darkred}u_{c-1} && \forall c\gt 1 \\ & \color{darkred}x_{n,c} \in \{0,1\} \\ & \color{darkred}u_c \in \{0,1\} \end{align} \]

Wednesday, January 19, 2022

An All-Paths Network Problem

In [1] a graph problem is proposed:

  • Given an undirected network,
  • Find all paths between two nodes,
  • Such that no arc is used more than once,
  • And the path does not contain more than \(M\) arcs
Notice that nodes can be visited several times. I thought this could be a good job for a solution pool approach. 


As I am more familiar with directed graphs, let's start with setting up a small random, sparse, directed graph. 

I start with 10 nodes and say there is a 20% probability that a link exists between two nodes, \(i \rightarrow j\). So the data set looks like:

----     30 SET n  nodes

 n1 ,    n2 ,    n3 ,    n4 ,    n5 ,    n6 ,    n7 ,    n8 ,    n9 ,    n10 

----     30 SET a  directed arcs

            n1          n2          n3          n4          n5          n6

n1                     YES                     YES
n2                                                                     YES
n3                                 YES
n4                                 YES         YES                     YES
n6                                                         YES
n7         YES                                             YES
n8                                 YES
n9         YES

 +          n7          n8          n9         n10

n1                     YES
n2                     YES
n3                     YES         YES
n4         YES
n5                                 YES
n6                                             YES
n8                                             YES
n9         YES                                 YES

Using \(n_1\) as the start node and \(n_{10}\) as the end node, we can visualize this as: