A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling
ABSTRACT 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.
| Main Authors: | , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Matemática Aplicada e Computacional
2018
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512018000300471 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|