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.
Na minha lista:
| Principais autores: | , , |
|---|---|
| Formato: | Digital revista |
| Idioma: | English |
| Publicado em: |
Sociedade Brasileira de Matemática Aplicada e Computacional
2018
|
| Acesso em linha: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512018000300471 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
oai:scielo:S2179-84512018000300471 |
|---|---|
| record_format |
ojs |
| spelling |
oai:scielo:S2179-845120180003004712018-12-13A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport SchedulingLARA,H. J.SIQUEIRA,A.S.YUAN,J. Sports scheduling Integer quadratic programming Semidefinite programming 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.info:eu-repo/semantics/openAccessSociedade Brasileira de Matemática Aplicada e ComputacionalTEMA (São Carlos) v.19 n.3 20182018-12-01info:eu-repo/semantics/articletext/htmlhttp://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512018000300471en10.5540/tema.2018.019.03.0471 |
| institution |
SCIELO |
| collection |
OJS |
| country |
Brasil |
| countrycode |
BR |
| component |
Revista |
| access |
En linea |
| databasecode |
rev-scielo-br |
| tag |
revista |
| region |
America del Sur |
| libraryname |
SciELO |
| language |
English |
| format |
Digital |
| author |
LARA,H. J. SIQUEIRA,A.S. YUAN,J. |
| spellingShingle |
LARA,H. J. SIQUEIRA,A.S. YUAN,J. A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| author_facet |
LARA,H. J. SIQUEIRA,A.S. YUAN,J. |
| author_sort |
LARA,H. J. |
| title |
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| title_short |
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| title_full |
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| title_fullStr |
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| title_full_unstemmed |
A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling |
| title_sort |
reduced semidefinite programming formulation for ha assignment problems in sport scheduling |
| description |
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. |
| publisher |
Sociedade Brasileira de Matemática Aplicada e Computacional |
| publishDate |
2018 |
| url |
http://old.scielo.br/scielo.php?script=sci_arttext&pid=S2179-84512018000300471 |
| work_keys_str_mv |
AT larahj areducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling AT siqueiraas areducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling AT yuanj areducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling AT larahj reducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling AT siqueiraas reducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling AT yuanj reducedsemidefiniteprogrammingformulationforhaassignmentproblemsinsportscheduling |
| _version_ |
1756439523472965632 |