/* Minimum Spanning Tree Problem */

var x12, binary;
var x13, binary;
var x14, binary;
var x15, binary;
var x23, binary;
var x24, binary;
var x25, binary;
var x34, binary;
var x35, binary;
var x45, binary;

minimize z: x12 + 4*x13 + 5*x14 + 3*x15 + 2*x23 + 6*x24 + 7*x45;

s.t. SPANNING: x12 + x13 + x14 + x15 + x23 + x24 + x45 = 4;
s.t. Loop_3_1: x12 + x13 + x14 + x23 + x24 + x34 <= 3;
s.t. Loop_3_2: x12 + x13 + x15 + x23 + x25 + x35 <= 3;
s.t. Loop_3_3: x12 + x14 + x15 + x24 + x25 + x45 <= 3;
s.t. Loop_3_4: x13 + x14 + x15 + x34 + x35 + x45 <= 3;
s.t. Loop_3_5: x23 + x24 + x25 + x34 + x35 + x45 <= 3;
s.t. Loop_2_1: x12 + x13 + x23 <= 2;
s.t. Loop_2_2: x12 + x14 + x24 <= 2;
s.t. Loop_2_3: x13 + x14 + x34 <= 2;
s.t. Loop_2_4: x23 + x24 + x34 <= 2;
s.t. Loop_2_5: x12 + x15 + x25 <= 2;
s.t. Loop_2_6: x13 + x15 + x35 <= 2;
s.t. Loop_2_7: x23 + x25 + x35 <= 2;
s.t. Loop_2_8: x14 + x15 + x45 <= 2;
s.t. Loop_2_9: x24 + x25 + x45 <= 2;
s.t. Loop_2_10: x34 + x35 + x45 <= 2;

end;