Helge von Koch (1870-1924)
Consider a tree graph \(G=(V,E)\) with \(n\) nodes and \(n-1\) arcs. We can label the nodes with unique numbers \(1,\dots,n\) and the arcs with unique numbers \(1,\dots,n-1\) such that each arc has a label equal to the (absolute value) of difference of the labels of the attached nodes. This is also called “Graceful Labeling” [1].
Here is a picture from [2]:
We see that:
- Each node has a unique label between 1 and 7 (the black numbers),
- Each arc has a unique label between 1 and 6 (the red numbers),
- Each arc has a label value equal to the difference in the labels of the associated nodes.
In [3] an interesting MIP formulation is proposed to find such a graceful labeling. There is no objective, i.e. we just look for a feasible solution. The uniqueness of node and arc labels is established by using an assignment block using binary variables (i.e. constraints we recognize from an assignment problem). A formulation can look like:
\[ \bbox[lightcyan,10px,border:3px solid darkblue]{ \begin{align} |
It makes sense to form the set \(E\) only with arcs \(i<j\) to prevent duplication (if we have an arc \(a \rightarrow b\) we don’t want to check also \(b \rightarrow a\)).
The absolute value equation still needs to be linearized, which we detail next.
Linearizing the absolute value
A standard formulation for \(y=|x|\) uses “\(y= -x\) or \(y=x\)”, i.e.
| \[\begin{align} & –x – \delta M \le y \le –x + \delta M\\ & x –(1-\delta) M \le y \le x + (1-\delta) M\\&\delta \in \{0,1\} \end{align} \] |
We can slightly improve, by using:
| \[\begin{align} & –x \le y \le –x + \delta M\\ & x \le y \le x + (1-\delta) M\\&\delta \in \{0,1\} \end{align} \] |
For our model we can get good values for the big-M's:
| \[\begin{align} &v^y_{i,j} \ge v^x_i - v^x_j\\ &v^y_{i,j} \ge v^x_j - v^x_i\\ &v^y_{i,j} \le v^x_j - v^x_i + 2 n \delta_{i,j} \\ &v^y_{i,j} \le v^x_j - v^x_j + 2 n (1-\delta_{i,j}) \\ & \delta_{i,j} \in \{0,1\} \end{align}\] |
This is the formulation presented in [3]. The solution is not unique. I see:
---- 74 VARIABLE vx.L node labels a 7, b 1, c 4, d 2, e 5, f 3, g 6
b c d e f g a 6 5 1 |
This is different from the solution in the picture.
Alternatives?
It seems tempting to try using an alternative approach to the absolute value constraint. May be something like:
| \[\begin{align}\min\>&\sum_{(i,j)\in E} v^y_{i,j}\\ &v^y_{i,j} \ge v^x_i - v^x_j\\ &v^y_{i,j} \ge v^x_j - v^x_i\end{align}\] |
These formulations do not work (in this case the objective is actually constant and does not really drive down the individual \(v^y\)’s).
Enumerate solutions
We already established that the solution is not unique. How many solutions are there for this small example problem?
We can add a simple cut:
| \[\sum_{i,v} \alpha_{i,v} x_{i,v} \le n-1\] |
where \(\alpha_{i,v}=x^*_{i,v}\) is a previously found solution. This will forbid this solution to be found again. If we solve again we will either find a new, different solution, or we see the model has become infeasible. In the latter case we can conclude there are no more solutions to be found.
If we repeat this, we find a surprisingly large number of solutions (I expected to see a dozen or so). Below are the node and arc labels we collected in the solve loop:
---- 124 PARAMETER vxall collected node labels a b c d e f g k1 7 1 4 2 5 3 6
a.b a.d a.g b.c b.e e.f k1 6 5 1 3 4 2 |
Note that there are \(7!=5040\) ways to order seven different labels, so from that perspective this is indeed a small subset of feasible node labels.
Instead of doing this solve loop ourselves we can also use the Solution Pool technology available in some solvers such as Cplex and Gurobi. This automates this loop (and does it way smarter and more efficient).
References
- Graceful Labeling, https://en.wikipedia.org/wiki/Graceful_labeling
- The von Koch conjecture, https://codegolf.stackexchange.com/questions/119263/the-von-koch-conjecture
- Mike Appleby, https://github.com/appleby/graceful-tree
- Helge von Koch, https://en.wikipedia.org/wiki/Helge_von_Koch
- Barbara M. Smith, Jean-Francois Puget, Constraint Models for graceful graphs, Constraints (2010), vol. 15, pp.64-92, https://link.springer.com/article/10.1007/s10601-009-9071-6. This paper discusses some interesting alternative models when attacking this as a Constraint Programming problem.
No comments:
Post a Comment