Follow this link to a summary table of results
and links to problem data. The set
partitioning problem is a minimization, however, our tabu search codes are
maximizations, therefore the set partitioning Q matrix is modified accordingly.
To guarantee feasibility, a new variable is appended to each row, but is given a
2*max_coefficient penalty in the objective function.
The 3 formats provided are cplex .lp, upper triangular Q matrix in row/col/value
format, and the full Q matrix. An example of a small problem with Penalty
= 50 is given below.
1) the cplex .lp format e.g.
\\ Set partitioning with 5 vars Minimize + 1 x_1 + 3 x_2 + 7 x_3 + 20 x_4 + 20 x_5 st \\ Sum x_i = 1 for j = 1 to m = 2 constraints + x_1 + x_2 + x_4 = 1 + x_1 + x_3 + x_5 = 1
Binaries x_1 x_2 x_3 x_4 x_5 end
2) the row column value format describing the
upper triangular portion of the Q matrix (with the first two rows describing
Palubeckis multi-start tabu search parameters) with the diagonal elements
doubled (e.g. 2*(50-1) = 98)
1 5 100 4000 4000
5 17
1 1 98
1 2 -50
1 3 -50
1 4 -50
1 5 -50
2 1 -50
2 2 94
2 4 -50
3 1 -50
3 3 86
3 5 -50
4 1 -50
4 2 -50
4 4 60
5 1 -50
5 3 -50
5 5 60
and 3) the full Q matrix where the first row and the last three rows are
Kochenberger tabu search parameters.
xqx_3_2_30_0.dat
5 0
99 -50 -50 -50 -50
-50 47 0 -50 0
-50 0 43 0 -50
-50 -50 0 30 0
-50 0 -50 0 30
3 5 5 1 0 0 0
7 3 5 500 -99 100 100 1.0 0.01 0.0
99 1371 1 1