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
:= { in Labels
with card({ ** in Labels with in Edges or **** in Edges })
mod 2 == 1 }
union { source, sink };
set Odd_edges := { 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 [ in Edges]
:= alpha * sqrt( (x_coordinates[a] - x_coordinates[b])^2
+ (y_coordinates[a] - y_coordinates[b])^2 );
param moving_time [ 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 in Edges : drawing_time[a, b] ### constant!
+ sum in Odd_edges : moving_time[a,b] * y[a, b];
## Constraint: Each odd vertex in exactly one matching edge
subto matching:
forall **** in Odd_vertices do
sum in Odd_edges: y[a, b]
+ sum **** in Odd_edges: y[b, a] == 1;
**