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

Hugo José Lara, Abel Soares Siqueira, Jinyun Yuan

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.

Full Text:

PDF

References


“Introducing the MOSEK Optimization Suite 8.1.0.47” (2018 (accessed February 10, 2018)). URL https://www.mosek.com/documentation/.

“CPLEX Optimization” (2018 (accessed February 3, 2018)). URL https://www.ibm.com/ analytics/data-science/prescriptive-analytics/cplex-optimizer.

T.Achterberg.“Solvingconstraintsintegerprograms”,volume1(1)(2009),pp.1–41.

J. Bezanson, A. Edelman, S. Karpinski & S. Viral B. Julia: A Fresh Approach to Numerical Com- puting. SIAM Review, 59 (2017), 65–98. doi:10.1137/141000671. URL http://julialang.org/ publications/julia-fresh-approach-BEKS.pdf.

I. Dunning, J. Huchette & M. Lubin. JuMP: A Modeling Language for Mathematical Optimization. SIAM Review, 59(2) (2017), 295–320. doi:10.1137/15M1020575.

K.Easton,G.Nemhauser&M.Trick.Thetravelingtournamentproblem:descriptionandbenchmarks. In T. Walsh (editor), “Principles and Practice of Constraint Programming, Volume 2239 of Lecture Notes in Computer Science”. Springer, Berlin (2001).

K. Easton, G. Nemhauser & M. Trick. Solving the travelling tournament problem: a combined integer programming and constraint programming approach. In J.Y.T. Leung & J.H. Anderson (editors), “In Handbook of Scheduling: Algorithms, Models and Performance Analysis”. Chapman and Hall (2004).

M.Elf, M.Junger & G.Rinaldi. Minimizing breaks by maximizing cuts. Operations Research Letters, 31 (2003), 343–349.

M.X. Goemans & D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 41 (1995), 1115–1145.

H. Lara Urdaneta, J. Yuan & A. Siqueira. Alternative linear and quadratic programming formula- tions for HA-Assignment problems. In “Proceeding Series of the Brazilian Society of Applied and Computational Mathematics”. SBMAC, Sa ̃o Jose dos Campos, SP. (2018), pp. 1–8.

M. Laurent & F. Rendl. Semidefinite Programming and Integer Programming. Austria, 2002., KUniversita ̈t Klagenfurt, Institut fu ̈r Mathematik (2002).

R. Miyashiro & T. Matsui. Semidefinite programming based approaches to the break minimization problem. Computers and Operations Research, 33 (2006), 1975 – 1982.

J. Perdomo & H. Lara. A combinatorial optimization formulation for the HA-Assignment problem. Publicaciones en Ciencias y Tecnolog ́ıa, 7(2) (2013), 127–141.

C. Ribeiro. Sport Scheduling: a tutorial on fundamental problems and applications. Technical report, Department of Computer Science, Universidade Federal Fluminense, Brazil (2010). URL http:// www.ic.uff.br/~celso/artigas/sport-scheduling.

A. Suzuka, R. Miyashiro, A. Yoshise & T. Matsui. Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling. Mathematical engineering technical reports, Department of Mathematical Informatics, The University of Tokyo. Japan. (2005). URL http:// www.i.u- tokyo.ac.jp/mi/mi- e.htm.

M. Trick. A Schedule-then-Break Approach to Sport Timetabling. Technical report, GSIA, Carnegie Mellon, Pittsburgh (2006). URL http://mat.gsia.cmu.edu.




DOI: https://doi.org/10.5540/tema.2018.019.03.471

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia