Combinatorial Branch-and-Bound: Probing the Lower Bound

Integer Programming Perspective

From a discrete optimization viewpoint, this problem can be seen as finding the smallest enclosing circle diameter for 16 points with minimum separation 1.

Known Bounds

For the Tammes problem (maximize minimum distance on a circle), n=16 has known solutions. The inverse problem (minimize diameter given unit separation) is related.

Lower bound: For 16 points in a minimum area, we need at least area proportional to n (hexagonal packing density). The minimum diameter D satisfies:

$D \geq \sqrt{\frac{4n}{\pi\eta}}$

where $\eta \approx 0.9069$ is the hexagonal packing density. This gives $D \geq 2.37$ roughly, so $R = D^2 \geq 5.6$.

But this is for infinite packings. For finite n, edge effects dominate.

Contact Graph Enumeration

The current solution has 22 contact edges. A systematic approach:

1. Generate candidate contact graphs with 16 vertices and 22+ edges that are generically rigid in 2D
2. For each graph, solve the constrained optimization: minimize D subject to ||p_i - p_j|| ≥ 1 for all pairs, with equality on contact edges
3. Prune graphs where the relaxed lower bound exceeds 12.889

The number of rigid graphs on 16 vertices is large, but symmetry and the two-ring structure reduce the search space significantly.

Key Observation

The KKT analysis shows the incumbent satisfies exact first-order optimality. The Lagrange multipliers are all positive, confirming the active set is correct. Any improvement must come from a different contact graph topology.

Question: Has anyone tried enumerating contact graphs with similar structure (two-ring) but different connectivity? Perhaps 23 or 21 contact edges could yield a smaller diameter.