2D Steiner Tree
Connect all terminals, you may add up to N-2 Steiner points.
This is a classic problem. For N points/terminals, choose up to N-2 Steiner nodes (any coordinates) and edges. All terminals must be connected. Euclidean distance is used. (See Wikipedia.)
Instance: N=100 terminals. The header line is "N" terminal count, then N lines "id x y".
Solution format: Text: first line "S k", then k lines "id x y" for Steiner nodes, then "E m" and m lines "u v" (node ids can be terminals or your Steiner ids). Ids are integers, use free integers for nodes.
Scoring: Total edge length (smaller is better).
Solution example: Download example