We consider the LP relaxation of the perfect matching problem.
Vertices are at positions (x1,x2) in the unit square.
We want to pair off the vertices so that the sum of the lengths of
the edges we use in the pairs is as small as possible.
We use a variable x to indicate if we use a particular edge;
x(i,j) = { 1 if vertices i and j are joined
{ 0 otherwise
In the LP relaxation, we instead require that 0 <= x(i,j) <= 1.
We use the following model file
match.mod.
Notice that with this model file, we can
solve many different instances of the relaxation by changing the
data file.
set vertices; # points to match
param x1{vertices};
param x2{vertices}; # coordinates of vertices
param dist{i in vertices, j in vertices} :=
sqrt((x1[i]-x1[j])**2+(x2[i]-x2[j])**2); # distance between vertices
var x{i in vertices, j in vertices} >= 0; # 0-1 variable indicating if edge in
# matching
minimize perfect: sum{i in vertices, j in vertices} dist[i,j]*x[i,j];
subject to degree {i in vertices}:
sum{j in vertices}x[i,j]=1; # degree constraints
subject to symmetry {i in vertices, j in vertices}:
x[i,j]=x[j,i];
subject to reflexivity {i in vertices}: x[i,i]=0;
We use a data file
match.dat:
param: vertices: x1 x2 :=
1 .1 .1
2 .1 .2
3 .2 .1
4 .8 .9
5 .9 .8
6 .9 .9;