A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling

Abstract

Home-Away Assignment problems are naturally cast as quadraticpro gramming models in binary variables. In this work we compare alternative formulations for this kind of problems. First, write a quadratic programming formulation with linear constraints, and then a quadratically constrained version. We also propose another formulation by manipulating their special structure to obtain versions with 1/4 of the original size. The quadratic programming formulations leads to semidefinite relaxations, which allows us to approximately solve the models. We compare our SDP relaxation with the MIN-RES-CUT based formulation. Numerical experiments exhibit the characteristics of each model.

Keywords

• Sports scheduling
• Integer quadratic programming. Semidefinite programming.