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

Title:
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling
Authors:
LARA,H. J., SIQUEIRA,A.S., YUAN,J.
Source:
TEMA (São Carlos) v.19 n.3 2018
Publisher Information:
Sociedade Brasileira de Matemática Aplicada e Computacional
Publication Year:
2018
Collection:
SciELO Brazil (Scientific Electronic Library Online)
Subject Terms:
Sports scheduling, Integer quadratic programming, Semidefinite programming
Document Type:
Academic journal article in journal/newspaper
File Description:
text/html
Language:
English
Availability:
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512018000300471
Rights:
info:eu-repo/semantics/openAccess
Accession Number:
edsbas.27846B07
Database:
BASE

Further Information

Home-Away Assignment problems are naturally considered as quadratic programming models in binary variables. For solving the problem, different formulations are studied here. First, the problem is rewritten as a quadratic programming formulation with linear constraints, and a quadratically constrained version respectively. For large scale problem, some reduced formulation are proposed by manipulating their special structure, with 1/4 of the original size. Note that the quadratic programming formulations lead to semidefinite relaxations solved approximately by semidefinite programming method. Comparison between our SDP relaxation and the MIN-RES-CUT based formulation is given. Finally some numerical experiments are given to illustrate the characteristics of each model.