Irrigation – Optimization challenges

The region contains 2,000 weighted fields. A field with a larger weight is worth more. Build a connected network of straight canal segments. You may place at most 100 nodes anywhere and join them with segments. The total length of all segments must not be greater than 10,000. A field scores according to its distance from the nearest canal segment. Closer fields score more. Place and connect the canals to maximize the total score.

An aerial view of vivid green rice fields.

Show mathematical formulationHide mathematical formulation

Choose a set \(V\) of at most 100 canal nodes and a set \(E\) of straight segments between them. The network \((V,E)\) must be connected and satisfy \(\sum_{\{u,v\}\in E}\lVert u-v\rVert\le 10{,}000\). For each field \(p_i\) with weight \(w_i\), let \(d_i=\min_{\{u,v\}\in E}\operatorname{dist}(p_i,\overline{uv})\). Maximize \(\sum_i w_i\exp(-d_i/40)\).

Instance: The instance contains 2000 weighted points. You may use at most 100 nodes. The length budget is 10000 and the decay distance is 40.

Show data formatHide data format

RULES pointCount nodeBudget lengthBudget decayDistance

POINTS pointCount
  id x y weight

Point ids are consecutive and start at 0.
Lines beginning with # are comments.

Download data (txt) Download local scorer

Solution format: First line: the number of nodes. Then one line per node: x y. Next line: the number of edges. Then one line per edge: nodeA nodeB. Node ids are their positions in the node list and start at 0. Coordinates must use ordinary decimal notation with at most 6 decimal places. Every node must belong to one connected network. Do not repeat edges.

Scoring: \(\text{Score}=\sum_i w_i\exp\left(-\frac{d_i}{40}\right)\) Higher is better. A field on a canal earns its full weight. Its contribution falls as its distance from the nearest segment grows. The server score is authoritative.

Solution example: Download example