Bicriteria weighted latin square problem
Brief description
In this variant of the Weighted latin square problem, the objective (sum of the costs of the cells) is decomposed into two criteria: the sum of the cells in the first half of the chessboard and the sum of the cells in the second half. A subset of the pareto solutions can be obtained by solving linear combinations of the two criteria with various weights on the objectives. This can be achieved in ToulBar2 via a MultiCFN object.
CFN model
Similarly to the Weighted latin square problem, NxN variables are created with a domain size N. In this model, the permutation of every row and every column is ensured through infinite costs in binary cost functions. Two different CFN are created to represent the two objectives: a first CFN where unary costs are added only for the first half of the chessboard, and a second one with unary costs for the remaining cells.
Toulbar2 allows to either solve for a chosen weighted sum of the two cost function networks as input, or approximate the pareto front by enumerating a complete set of non-redundant weights. As it is shown below, the method allows to compute solutions which costs lie in the convex hull of the pareto front. However, potential solutions belonging to the triangles will be missed with this approach.
Python model
The following code using the pytoulbar2 library solves the bicriteria weighted latin square problem with two different pairs of weights for the two objectives.
import sys
from random import seed, randint
seed(123456789)
import pytoulbar2
from matplotlib import pyplot as plt
N = int(sys.argv[1])
top = N**3 +1
# printing a solution as a grid
def print_solution(sol, N):
grid = [0 for _ in range(N*N)]
for k,v in sol.items():
grid[ int(k[5])*N+int(k[7]) ] = int(v[1:])
output = ''
for var_ind in range(len(sol)):
output += str(grid[var_ind]) + ' '
if var_ind % N == N-1:
output += '\n'
print(output, end='')
# creation of the base problem: variables and hard constraints (alldiff must be decomposed into binary constraints)
def create_base_cfn(cfn, N, top):
# variable creation
var_indexes = []
# create N^2 variables, with N values in their domains
for row in range(N):
for col in range(N):
index = cfn.AddVariable('Cell_' + str(row) + '_' + str(col), ['v' + str(val) for val in range(N)])
var_indexes.append(index)
# all permutation constraints: pairwise all different
# forbidden values are enforced by infinite costs
alldiff_costs = [ top if row == col else 0 for row in range(N) for col in range(N) ]
for index in range(N):
for var_ind1 in range(N):
for var_ind2 in range(var_ind1+1, N):
# permutations in the rows
cfn.AddFunction([var_indexes[N*index+var_ind1], var_indexes[N*index+var_ind2]], alldiff_costs)
# permutations in the columns
cfn.AddFunction([var_indexes[index+var_ind1*N], var_indexes[index+var_ind2*N]], alldiff_costs)
split_index = (N*N)//2
# generation of random costs
cell_costs = [[randint(1,N) for _ in range(N)] for _ in range(N*N)]
# multicfn is the main object for combining multiple cost function networks
multicfn = pytoulbar2.MultiCFN()
# first cfn: first half of the grid
cfn = pytoulbar2.CFN(ubinit = top, resolution=6)
cfn.SetName('first half')
create_base_cfn(cfn, N, top)
for variable_index in range(split_index):
cfn.AddFunction([variable_index], cell_costs[variable_index])
multicfn.PushCFN(cfn)
# second cfn: second half of the grid
cfn = pytoulbar2.CFN(ubinit = top, resolution=6)
cfn.SetName('second half')
create_base_cfn(cfn, N, top)
for variable_index in range(split_index+1, N*N):
cfn.AddFunction([variable_index], cell_costs[variable_index])
multicfn.PushCFN(cfn)
# solve with a first pair of weights
weights = (1., 2.)
multicfn.SetWeight(0, weights[0])
multicfn.SetWeight(1, weights[1])
cfn = pytoulbar2.CFN()
cfn.InitFromMultiCFN(multicfn) # the final cfn is initialized from the combined cfn
# cfn.Dump('python_latin_square_bicriteria.cfn')
result = cfn.Solve()
if result:
print('Solution found with weights', weights, ':')
sol_costs = multicfn.GetSolutionCosts()
solution = multicfn.GetSolution()
print_solution(solution, N)
print('with costs:', sol_costs, '(sum=', result[1], ')')
print('\n')
# solve a second time with other weights
weights = (2.5, 1.)
multicfn.SetWeight(0, weights[0])
multicfn.SetWeight(1, weights[1])
cfn = pytoulbar2.CFN()
cfn.InitFromMultiCFN(multicfn) # the final cfn is initialized from the combined cfn
# cfn.Dump('python_latin_square_bicriteria.cfn')
result = cfn.Solve()
if result:
print('Solution found with weights', weights, ':')
sol_costs = multicfn.GetSolutionCosts()
solution = multicfn.GetSolution()
print_solution(solution, N)
print('with costs:', sol_costs, '(sum=', result[1], ')')
# approximate the pareto front
(solutions, costs) = multicfn.ApproximateParetoFront(0, 'min', 1, 'min')
fig, ax = plt.subplots()
ax.scatter([c[0] for c in costs], [c[1] for c in costs], marker='x')
for index in range(len(costs)-1):
ax.plot([costs[index][0], costs[index+1][0]], [costs[index][1],costs[index+1][1]], '--', c='k')
ax.plot([costs[index][0], costs[index+1][0]], [costs[index][1],costs[index][1]], '--', c='red')
ax.plot([costs[index+1][0], costs[index+1][0]], [costs[index][1],costs[index+1][1]], '--', c='red')
ax.set_xlabel('first half cost')
ax.set_ylabel('second half cost')
ax.set_title('approximation of the pareto front')
ax.set_aspect('equal')
plt.grid()
plt.show()