param points_file := "plot-points-10000-1";
param edges_file := "plot-edges-10000-0.1-1";

## Read points.

set Labels := { read points_file as "<1n>" comment "#" };

param x_coordinates[Labels] 
  := read points_file as "<1n> 2n" comment "#";

param y_coordinates[Labels]
  := read points_file as "<1n> 3n" comment "#";

## Read graph.

set Edges := { read edges_file as "<1n, 2n>" comment "#" };

## Find odd vertices; add artificial source and sink

param source := -2;
param sink := -1;

set Odd_vertices 
  := { <a> in Labels 
       with card({ <b> in Labels with <a,b> in Edges or <b,a> in Edges }) 
              mod 2 == 1 }
     union { source, sink };

set Odd_edges := { <a,b> in (Odd_vertices cross Odd_vertices) with a < b };

## Drawing and moving times.

param alpha := 1;        # Drawing velocity
param beta := 2;	 # Horizontal movement velocity
param gamma := 1.5;      # Vertical movement velocity

param drawing_time [<a,b> in Edges] 
  := alpha * sqrt( (x_coordinates[a] - x_coordinates[b])^2
     	     	   + (y_coordinates[a] - y_coordinates[b])^2 );

param moving_time [<a,b> in Odd_edges]
  := if (a == source or a == sink or b == source or b == sink) 
     then 0
     else max(beta * abs(x_coordinates[a] - x_coordinates[b]),
     	      gamma * abs(y_coordinates[a] - y_coordinates[b]))
     end;

## Variables.

var y[Odd_edges] binary;

## Objective.

minimize total_drawing_time:
    sum <a, b> in Edges     : drawing_time[a, b]           ### constant!
  + sum <a, b> in Odd_edges : moving_time[a,b] * y[a, b];

## Constraint: Each odd vertex in exactly one matching edge

subto matching:
  forall <a> in Odd_vertices do
    sum <a, b> in Odd_edges: y[a, b] 
    + sum <b, a> in Odd_edges: y[b, a] == 1;