Best reduction of the quadratic semi-assignment problem (Q5931788)

The quadratic semi-assignment problem is stated, that is a quadratic assignment problem simplification, in which one of the sets of unique assignment constraints is relaxed. For the quadratic problem a reduction is defined as a pair, which consists of a real constant and a quadratic function with nonnegative coefficients. This pair constitutes the reduction if the sum of the constant and function is equal to the original objective function of the problem for each feasible solution. The authors focus on the best reduction of a quadratic semi-assignment problem, what is a reduction with the greatest constant. They prove that the best reduction can be obtained by solving a linear program. The optimal value of the linear program objective function yields the constant of the best reduction and reduced costs associated with the optimal solution constitute the nonnegative coefficients of the quadratic function. In the sequel of the paper, the authors prove that their best reduction is strictly better than some other reductions. In the same sequel, results of numerical experiments are reported, which show that employment of the best reduction in quadratic semi-assignment problem resolution can reduce the associated computational time several times.