• Previous Article
    A semidefinite relaxation algorithm for checking completely positive separable matrices
  • JIMO Home
  • This Issue
  • Next Article
    Multiperiod portfolio optimization for asset-liability management with quadratic transaction costs
doi: 10.3934/jimo.2018109

CP and MIP approaches for soccer analysis

1. 

AVISPA Research Group, Escuela de Ingeniería de Sistemas y Computación, Universidad del Valle, Colombia

2. 

Riomh Research Group, Department of Computer Science, Cork Institute of Technology, Ireland

* Corresponding author: Robinson Duque

Received  December 2016 Revised  August 2017 Published  July 2018

Soccer is one of the most popular sports in the world with millions of fans that usually raise interesting questions when the competition is partially completed. One interesting question relates to the elimination problem which consists in checking at some stage of the competition if a team i still has a theoretical chance to finish first in a league or be within the first k teams in a tournament to qualify to the playoffs (e.g., become the champion if k = 1). Some other interesting problems from the literature are the guaranteed qualification problem, the possible qualification problem, the score vector problem, promotion and relegation problem. These problems are NP-complete for the actual FIFA pointing rule system (0 points-loss, 1 point-tie, 3 points-win). SABIO is an online platform that helps users discover information related to soccer by letting them formulate questions in form of constraints and go beyond the classical soccer computational problems. In this paper we considerably improve the performance of an existing constraint programming (CP) model and combine the use of mixed integer programming (MIP) and CP to answer general soccer queries in a real-time application.

Citation: Robinson Duque, Alejandro Arbelaez, Juan Francisco Díaz. CP and MIP approaches for soccer analysis. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018109
References:
[1]

I. AdlerA. L. EreraD. S. Hochbaum and E. V. Olinick, Baseball, optimization, and the world wide web, Interfaces, 32 (2002), 12-22. doi: 10.1287/inte.32.2.12.67.

[2]

F. AlarcónG. DuránM. GuajardoJ. MirandaH. MuñozL. RamírezM. RamírezD. SauréM. SiebertS. SouyrisA. WeintraubR. Wolf-Yadlin and G. Zamorano, Operations research transforms the scheduling of Chilean soccer leagues and South American World Cup qualifiers, Interfaces, 47 (2017), 52-69.

[3]

T. BartschA. Drexl and S. Kröger, Scheduling the professional soccer leagues of Austria and Germany, Computers & Operations Research, 33 (2006), 1907-1937. doi: 10.1016/j.cor.2004.09.037.

[4]

T. BernholtA. GälichT. Hofmeister and N. Schmitt, Football elimination is hard to decide under the 3-point-rule, International Symposium on Mathematical Foundations of Computer Science, (1999), 410-418. doi: 10.1007/3-540-48340-3_37.

[5]

J. Borrett, E. P. Tsang and N. R. Walsh, Adaptive constraint satisfaction: The quickest first principle, in European Conference on Artificial Intelligence, (1996).

[6]

F. Boussemart, F. Hemery, C. Lecoutre and L. Sais, Boosting systematic search by weighting constraints, in ECAI, (2004), 146–150.

[7]

S. K. Card, G. G. Robertson and J. D. Mackinlay, The information visualizer, an information workspace, in SIGCHI Conference on Human Factors in Computing Systems (ACM), (1991), 181–186.

[8]

J. ChristensenA. N. Knudsen and K. S. Larsen, Soccer is harder than football, International Journal of Foundations of Computer Science, 26 (2015), 477-486. doi: 10.1142/S0129054115500264.

[9]

M. Consortium, The mozart programming system, 2013. Available from http://mozart.github.io/.

[10]

D. Costa, An evolutionary tabu search algorithm and the NHL scheduling problem, INFOR: Information Systems and Operational Research, 33 (1995), 161-178. doi: 10.1080/03155986.1995.11732279.

[11]

R. Duque, J. F. Díaz and A. Arbelaez, Constraint programming and machine learning for interactive soccer analysis, in Learning and Intelligent Optimization, (2016), 240–246. doi: 10.1007/978-3-319-50349-3_18.

[12]

R. Duque, J. F. Díaz and A. Arbelaez, SABIO: An implementation of MIP and CP for interactive soccer queries, in International Conference on Principles and Practice of Constraint Programming, (2016), 575–583.

[13]

G. DuránM. GuajardoJ. MirandaD. SauréS. SouyrisA. Weintraub and R. Wolf, Scheduling the Chilean soccer league by integer programming, Interfaces, 37 (2007), 539-552.

[14]

G. DuránM. Guajardo and D. Sauré, Scheduling the South American Qualifiers to the 2018 FIFA World Cup by integer programming, European Journal of Operational Research, 262 (2017), 1109-1115. doi: 10.1016/j.ejor.2017.04.043.

[15]

G. DuránM. Guajardo and R. Wolf-Yadlin, Operations research techniques for scheduling Chile's second division soccer league, Interfaces, 42 (2012), 273-285.

[16]

Gecode Team, Gecode: Generic constraint development environment, 2016. Available from http://www.gecode.org.

[17]

D. Goossens and F. Spieksma, Scheduling the Belgian soccer league, Interfaces, 39 (2009), 109-118. doi: 10.1287/inte.1080.0402.

[18]

D. R. GoossensJ. Beliën and F. C. Spieksma, Comparing league formats with respect to match importance in Belgian football, Annals of Operations Research, 194 (2012), 223-240. doi: 10.1007/s10479-010-0764-4.

[19]

J. C. Guedes and F. S. Machado, Changing rewards in contests: Has the three-point rule brought more offense to soccer? Empirical Economics, 27 (2002), 607–630. doi: 10.1007/s001810100106.

[20]

D. Gusfield and C. Martel, The structure and complexity of sports elimination numbers, Algorithmica, 32 (2002), 73-86. doi: 10.1007/s00453-001-0074-y.

[21]

R. M. Haralick and G. L. Elliott, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14 (1980), 263-313. doi: 10.1016/0004-3702(80)90051-X.

[22]

A. Hoffman and T. Rivlin, When is a team "mathematically" eliminated?, Princeton Symposium on Mathematical Programming, (1967), 391-401.

[23]

H. Kellerer, U. Pferschy and D. Pisinger, The subset sum problem, in Knapsack Problems, (2004), 73–115.

[24]

W. Kern and D. Paulusma, The new FIFA rules are hard: Complexity aspects of sports competitions, Discrete Applied Mathematics, 108 (2001), 317-323. doi: 10.1016/S0166-218X(00)00241-9.

[25]

W. Kern and D. Paulusma, The computational complexity of the elimination problem in generalized sports competitions, Discrete Optimization, 1 (2004), 205-214. doi: 10.1016/j.disopt.2003.12.003.

[26]

J. Kyngas and K. Nurmi, Scheduling the Finnish major ice hockey league, in Computational Intelligence in Scheduling, (2009), 84–89. doi: 10.1109/SCIS.2009.4927019.

[27]

C. Lucena, T. Noronha, S. Urrutia and C. Ribeiro, A multi-agent framework to retrieve and publish information on qualification and elimination data in sports tournaments, Monografias em Ciênca da Computação, (2006).

[28]

S. T. McCormick, Fast algorithms for parametric scheduling come from extensions to parametric maximum flow, Operations Research, 47 (1999), 744-756. doi: 10.1287/opre.47.5.744.

[29]

R. B. Miller, Response time in man-computer conversational transactions, Joint Computer Conference, part I, (1968), 267-277. doi: 10.1145/1476589.1476628.

[30]

Monash University, Data61 Decision Sciences and University of Melbourne. Minizinc, 2014, Available from http://www.minizinc.org/.

[31]

T. F. Noronha, C. C. Ribeiro, G. Duran, S. Souyris and A. Weintraub. A branch-and-cut algorithm for scheduling the highly-constrained Chilean soccer tournament, in International Conference on the Practice and Theory of Automated Timetabling, (2006), 174–186. doi: 10.1007/978-3-540-77345-0_12.

[32]

D. Pálvölgyi, Deciding soccer scores and partial orientations of graphs, Acta Univ. Sapientiae, Math, 1 (2009), 51-71.

[33]

C. RaackA. RaymondT. Schlechte and A. Werner, Standings in sports competitions using integer programming, Journal of Quantitative Analysis in Sports, 10 (2014), 131-137. doi: 10.1515/jqas-2013-0111.

[34]

R. V. Rasmussen, Scheduling a triple round robin tournament for the best danish soccer league, European Journal of Operational Research, 185 (2008), 795-810. doi: 10.1016/j.ejor.2006.12.050.

[35]

R. V. Rasmussen and M. A. Trick, Round robin scheduling-a survey, European Journal of Operational Research, 188 (2008), 617-636. doi: 10.1016/j.ejor.2007.05.046.

[36]

P. Refalo, Impact-based search strategies for constraint programming, in International Conference on Principles and Practice of Constraint Programming, (2004), 557–571. doi: 10.1007/978-3-540-30201-8_41.

[37]

C. C. Ribeiro and S. Urrutia, An application of integer programming to playoff elimination in football championships, International Transactions in Operational Research, 12 (2005), 375-386. doi: 10.1111/j.1475-3995.2005.00513.x.

[38]

C. C. Ribeiro and S. Urrutia, Scheduling the Brazilian soccer tournament with fairness and broadcast objectives, in International Conference on the Practice and Theory of Automated Timetabling, (2006), 147–157. doi: 10.1007/978-3-540-77345-0_10.

[39]

C. C. Ribeiro and S. Urrutia, Scheduling the Brazilian soccer tournament: Solution approach and practice, Interfaces, 42 (2012), 260-272. doi: 10.1287/inte.1110.0566.

[40]

F. Rossi, P. van Beek and T. Walsh, Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence, Elsevier, 2006.

[41]

R. A. Russell and J. M. Leung, Devising a cost effective schedule for a baseball league, Operations Research, 42 (1994), 614-625. doi: 10.1287/opre.42.4.614.

[42]

B. L. Schwartz, Possible winners in partially completed tournaments, SIAM Review, 8 (1966), 302-308. doi: 10.1137/1008062.

[43]

P. J. Stuckey, M. G. de la Banda, M. Maher, K. Marriott, J. Slaney, Z. Somogyi, M. Wallace and T. Walsh, The G12 project: Mapping solver independent models to efficient solutions, in International Conference on Logic Programming, (2005), 9–13.

[44]

T. Van Voorhis, Highly constrained college basketball scheduling, Journal of the Operational Research Society, 53 (2002), 603-609. doi: 10.1057/palgrave.jors.2601356.

[45]

M. Veksler, HaifaCSP - constraints-satisfaction problem (CSP) solver, 2016. Available from http://strichman.net.technion.ac.il/haifacsp/.

[46]

K. D. Wayne, A new property and a faster algorithm for baseball elimination, SIAM Journal on Discrete Mathematics, 14 (2001), 223-229. doi: 10.1137/S0895480198348847.

[47]

I. H. Witten and E. Frank, Data mining: Practical machine learning tools and techniques, ACM SIGMOD Record, 31 (2002), 76-77. doi: 10.1145/507338.507355.

[48]

M. B. Wright, Scheduling fixtures for basketball New Zealand, Computers & Operations Research, 33 (2006), 1875-1893. doi: 10.1016/j.cor.2004.09.024.

[49]

J. T. Yang, H.-D. Huang and J.-T. Horng, Devising a cost effective baseball scheduling by evolutionary algorithms, in Evolutionary Computation, (2002), 1660–1665.

show all references

References:
[1]

I. AdlerA. L. EreraD. S. Hochbaum and E. V. Olinick, Baseball, optimization, and the world wide web, Interfaces, 32 (2002), 12-22. doi: 10.1287/inte.32.2.12.67.

[2]

F. AlarcónG. DuránM. GuajardoJ. MirandaH. MuñozL. RamírezM. RamírezD. SauréM. SiebertS. SouyrisA. WeintraubR. Wolf-Yadlin and G. Zamorano, Operations research transforms the scheduling of Chilean soccer leagues and South American World Cup qualifiers, Interfaces, 47 (2017), 52-69.

[3]

T. BartschA. Drexl and S. Kröger, Scheduling the professional soccer leagues of Austria and Germany, Computers & Operations Research, 33 (2006), 1907-1937. doi: 10.1016/j.cor.2004.09.037.

[4]

T. BernholtA. GälichT. Hofmeister and N. Schmitt, Football elimination is hard to decide under the 3-point-rule, International Symposium on Mathematical Foundations of Computer Science, (1999), 410-418. doi: 10.1007/3-540-48340-3_37.

[5]

J. Borrett, E. P. Tsang and N. R. Walsh, Adaptive constraint satisfaction: The quickest first principle, in European Conference on Artificial Intelligence, (1996).

[6]

F. Boussemart, F. Hemery, C. Lecoutre and L. Sais, Boosting systematic search by weighting constraints, in ECAI, (2004), 146–150.

[7]

S. K. Card, G. G. Robertson and J. D. Mackinlay, The information visualizer, an information workspace, in SIGCHI Conference on Human Factors in Computing Systems (ACM), (1991), 181–186.

[8]

J. ChristensenA. N. Knudsen and K. S. Larsen, Soccer is harder than football, International Journal of Foundations of Computer Science, 26 (2015), 477-486. doi: 10.1142/S0129054115500264.

[9]

M. Consortium, The mozart programming system, 2013. Available from http://mozart.github.io/.

[10]

D. Costa, An evolutionary tabu search algorithm and the NHL scheduling problem, INFOR: Information Systems and Operational Research, 33 (1995), 161-178. doi: 10.1080/03155986.1995.11732279.

[11]

R. Duque, J. F. Díaz and A. Arbelaez, Constraint programming and machine learning for interactive soccer analysis, in Learning and Intelligent Optimization, (2016), 240–246. doi: 10.1007/978-3-319-50349-3_18.

[12]

R. Duque, J. F. Díaz and A. Arbelaez, SABIO: An implementation of MIP and CP for interactive soccer queries, in International Conference on Principles and Practice of Constraint Programming, (2016), 575–583.

[13]

G. DuránM. GuajardoJ. MirandaD. SauréS. SouyrisA. Weintraub and R. Wolf, Scheduling the Chilean soccer league by integer programming, Interfaces, 37 (2007), 539-552.

[14]

G. DuránM. Guajardo and D. Sauré, Scheduling the South American Qualifiers to the 2018 FIFA World Cup by integer programming, European Journal of Operational Research, 262 (2017), 1109-1115. doi: 10.1016/j.ejor.2017.04.043.

[15]

G. DuránM. Guajardo and R. Wolf-Yadlin, Operations research techniques for scheduling Chile's second division soccer league, Interfaces, 42 (2012), 273-285.

[16]

Gecode Team, Gecode: Generic constraint development environment, 2016. Available from http://www.gecode.org.

[17]

D. Goossens and F. Spieksma, Scheduling the Belgian soccer league, Interfaces, 39 (2009), 109-118. doi: 10.1287/inte.1080.0402.

[18]

D. R. GoossensJ. Beliën and F. C. Spieksma, Comparing league formats with respect to match importance in Belgian football, Annals of Operations Research, 194 (2012), 223-240. doi: 10.1007/s10479-010-0764-4.

[19]

J. C. Guedes and F. S. Machado, Changing rewards in contests: Has the three-point rule brought more offense to soccer? Empirical Economics, 27 (2002), 607–630. doi: 10.1007/s001810100106.

[20]

D. Gusfield and C. Martel, The structure and complexity of sports elimination numbers, Algorithmica, 32 (2002), 73-86. doi: 10.1007/s00453-001-0074-y.

[21]

R. M. Haralick and G. L. Elliott, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14 (1980), 263-313. doi: 10.1016/0004-3702(80)90051-X.

[22]

A. Hoffman and T. Rivlin, When is a team "mathematically" eliminated?, Princeton Symposium on Mathematical Programming, (1967), 391-401.

[23]

H. Kellerer, U. Pferschy and D. Pisinger, The subset sum problem, in Knapsack Problems, (2004), 73–115.

[24]

W. Kern and D. Paulusma, The new FIFA rules are hard: Complexity aspects of sports competitions, Discrete Applied Mathematics, 108 (2001), 317-323. doi: 10.1016/S0166-218X(00)00241-9.

[25]

W. Kern and D. Paulusma, The computational complexity of the elimination problem in generalized sports competitions, Discrete Optimization, 1 (2004), 205-214. doi: 10.1016/j.disopt.2003.12.003.

[26]

J. Kyngas and K. Nurmi, Scheduling the Finnish major ice hockey league, in Computational Intelligence in Scheduling, (2009), 84–89. doi: 10.1109/SCIS.2009.4927019.

[27]

C. Lucena, T. Noronha, S. Urrutia and C. Ribeiro, A multi-agent framework to retrieve and publish information on qualification and elimination data in sports tournaments, Monografias em Ciênca da Computação, (2006).

[28]

S. T. McCormick, Fast algorithms for parametric scheduling come from extensions to parametric maximum flow, Operations Research, 47 (1999), 744-756. doi: 10.1287/opre.47.5.744.

[29]

R. B. Miller, Response time in man-computer conversational transactions, Joint Computer Conference, part I, (1968), 267-277. doi: 10.1145/1476589.1476628.

[30]

Monash University, Data61 Decision Sciences and University of Melbourne. Minizinc, 2014, Available from http://www.minizinc.org/.

[31]

T. F. Noronha, C. C. Ribeiro, G. Duran, S. Souyris and A. Weintraub. A branch-and-cut algorithm for scheduling the highly-constrained Chilean soccer tournament, in International Conference on the Practice and Theory of Automated Timetabling, (2006), 174–186. doi: 10.1007/978-3-540-77345-0_12.

[32]

D. Pálvölgyi, Deciding soccer scores and partial orientations of graphs, Acta Univ. Sapientiae, Math, 1 (2009), 51-71.

[33]

C. RaackA. RaymondT. Schlechte and A. Werner, Standings in sports competitions using integer programming, Journal of Quantitative Analysis in Sports, 10 (2014), 131-137. doi: 10.1515/jqas-2013-0111.

[34]

R. V. Rasmussen, Scheduling a triple round robin tournament for the best danish soccer league, European Journal of Operational Research, 185 (2008), 795-810. doi: 10.1016/j.ejor.2006.12.050.

[35]

R. V. Rasmussen and M. A. Trick, Round robin scheduling-a survey, European Journal of Operational Research, 188 (2008), 617-636. doi: 10.1016/j.ejor.2007.05.046.

[36]

P. Refalo, Impact-based search strategies for constraint programming, in International Conference on Principles and Practice of Constraint Programming, (2004), 557–571. doi: 10.1007/978-3-540-30201-8_41.

[37]

C. C. Ribeiro and S. Urrutia, An application of integer programming to playoff elimination in football championships, International Transactions in Operational Research, 12 (2005), 375-386. doi: 10.1111/j.1475-3995.2005.00513.x.

[38]

C. C. Ribeiro and S. Urrutia, Scheduling the Brazilian soccer tournament with fairness and broadcast objectives, in International Conference on the Practice and Theory of Automated Timetabling, (2006), 147–157. doi: 10.1007/978-3-540-77345-0_10.

[39]

C. C. Ribeiro and S. Urrutia, Scheduling the Brazilian soccer tournament: Solution approach and practice, Interfaces, 42 (2012), 260-272. doi: 10.1287/inte.1110.0566.

[40]

F. Rossi, P. van Beek and T. Walsh, Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence, Elsevier, 2006.

[41]

R. A. Russell and J. M. Leung, Devising a cost effective schedule for a baseball league, Operations Research, 42 (1994), 614-625. doi: 10.1287/opre.42.4.614.

[42]

B. L. Schwartz, Possible winners in partially completed tournaments, SIAM Review, 8 (1966), 302-308. doi: 10.1137/1008062.

[43]

P. J. Stuckey, M. G. de la Banda, M. Maher, K. Marriott, J. Slaney, Z. Somogyi, M. Wallace and T. Walsh, The G12 project: Mapping solver independent models to efficient solutions, in International Conference on Logic Programming, (2005), 9–13.

[44]

T. Van Voorhis, Highly constrained college basketball scheduling, Journal of the Operational Research Society, 53 (2002), 603-609. doi: 10.1057/palgrave.jors.2601356.

[45]

M. Veksler, HaifaCSP - constraints-satisfaction problem (CSP) solver, 2016. Available from http://strichman.net.technion.ac.il/haifacsp/.

[46]

K. D. Wayne, A new property and a faster algorithm for baseball elimination, SIAM Journal on Discrete Mathematics, 14 (2001), 223-229. doi: 10.1137/S0895480198348847.

[47]

I. H. Witten and E. Frank, Data mining: Practical machine learning tools and techniques, ACM SIGMOD Record, 31 (2002), 76-77. doi: 10.1145/507338.507355.

[48]

M. B. Wright, Scheduling fixtures for basketball New Zealand, Computers & Operations Research, 33 (2006), 1875-1893. doi: 10.1016/j.cor.2004.09.024.

[49]

J. T. Yang, H.-D. Huang and J.-T. Horng, Devising a cost effective baseball scheduling by evolutionary algorithms, in Evolutionary Computation, (2002), 1660–1665.

Figure 1.  Data set sample with 10 records to train a machine learning model for value selection
Figure 2.  Colombian league runtime comparison (time in seconds for parallel executions)
Figure 3.  Argentine league runtime comparison (time in seconds for parallel executions)
Figure 4.  Colombian league runtime comparison for mixed solver executions (time in seconds for parallel executions)
Figure 5.  Argentine league runtime comparison for mixed solver (time in seconds for parallel executions)
Table 1.  Solvers and model configurations used in the empirical tests
Model Short Name Oz CPLEX HaifaCSP G12/FD Gecode
CP model CP $\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$
CP model + Redundant Constraints CP-R $\checkmark$ $\checkmark$ $\checkmark$
MIP model MIP $\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$
Model Short Name Oz CPLEX HaifaCSP G12/FD Gecode
CP model CP $\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$
CP model + Redundant Constraints CP-R $\checkmark$ $\checkmark$ $\checkmark$
MIP model MIP $\checkmark$ $\checkmark$ $\checkmark$ $\checkmark$
Table 2.  Oz Solvers and model configurations using Var/Val heuristics
Model Short Name Oz
CP model + Var/Val Heuristics including Machine Learning CP-ML $\checkmark$
Extended CP (CP model + Redundant Constraints + Var/Val Heuristics including Machine Learning) E-CP $\checkmark$
Model Short Name Oz
CP model + Var/Val Heuristics including Machine Learning CP-ML $\checkmark$
Extended CP (CP model + Redundant Constraints + Var/Val Heuristics including Machine Learning) E-CP $\checkmark$
Table 3.  Unsolved instances and average running times for the Colombian league (18 teams) evaluated sequentially and in parallel with the CP, CP-ML, and E-CP models using Mozart-Oz
1 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Oz CP 24 28 38 46 50 52 0 0 0 0 0 0 0 2 0 0 6 3
Fixture 7 Oz CP-ML 5 9 14 21 27 35 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 1 3 4 5 11 15 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 28 35 46 49 44 0 0 0 0 0 0 0 0 0 0 1 1
Fixture 9 Oz CP-ML 1 4 9 18 27 31 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 2 1 4 6 11 15 0 0 0 0 0 0 0 0 0 0 0 1
Oz CP 25 27 31 44 49 47 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 11 Oz CP-ML 2 7 11 18 31 34 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 3 4 8 17 16 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 33 38 41 51 45 0 0 0 0 0 0 0 0 0 1 0 0
Fixture 14 Oz CP-ML 8 22 25 34 44 42 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 2 7 9 14 8 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 31 29 31 25 13 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 16 Oz CP-ML 19 25 25 33 28 17 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP 1069 0 14
Instances Oz CP-ML 626 0 1
Oz E-CP 170 0 1
Oz CP 0.22 0.48 0.32 0.41 0.77 1.1 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.23 0.22
Fixture 7 Oz CP-ML 1.21 1.35 1.84 2.41 3.29 3.09 0.06 0.06 0.06 0.06 0.06 0.05 0.05 0.11 0.05 0.05 0.26 0.2
Oz E-CP 0.89 0.94 1.05 1.06 0.95 1.19 0.06 0.06 0.07 0.07 0.06 0.06 0.07 0.12 0.06 0.06 0.27 0.22
Oz CP 0.09 0.42 0.23 0.66 0.32 0.73 0.07 0.07 0.07 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.22
Fixture 9 Oz CP-ML 1.69 1.48 2.26 2.81 2.79 1.67 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.07 0.07
Oz E-CP 0.81 0.56 1.16 1.16 1.9 0.46 0.07 0.06 0.06 0.06 0.07 0.06 0.06 0.06 0.05 0.05 0.08 0.08
Oz CP 0.56 0.1 0.76 0.69 0.87 0.45 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.08 0.05 0.05 0.05
Fixture 11 Oz CP-ML 1.53 1.09 2.02 2.68 2.57 2.47 0.06 0.06 0.05 0.06 0.05 0.05 0.05 0.06 0.08 0.06 0.05 0.04
Oz E-CP 0.4 0.4 0.75 0.64 0.78 0.23 0.06 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.07 0.05 0.05 0.04
Oz CP 0.42 0.14 0.49 1.02 1.54 0.74 0.05 0.05 0.05 0.05 0.05 0.04 0.05 0.05 0.05 0.05 0.05 0.04
Fixture 14 Oz CP-ML 1.17 1.3 1.46 1.49 1.08 1.48 0.04 0.03 0.03 0.03 0.03 0.03 0.04 0.03 0.03 0.06 0.03 0.03
Oz E-CP 0.07 0.37 0.11 0.16 0.44 0.54 0.05 0.05 0.04 0.04 0.05 0.04 0.05 0.04 0.04 0.07 0.04 0.04
Oz CP 0.12 0.05 0.9 0.56 0.46 0.66 0.04 0.04 0.04 0.04 0.04 0.04 0.05 0.04 0.04 0.04 0.04 0.04
Fixture 16 Oz CP-ML 0.56 0.5 0.93 0.05 0.12 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.05 0.04 0.03 0.07 0.04 0.05 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz CP 0.51 0.06 0.07
Avg. Time Oz CP-ML 1.61 0.05 0.06
Oz E-CP 0.57 0.05 0.07
4 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Fixture 7 Oz CP-ML 4 8 15 18 26 37 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 1 3 4 5 11 18 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 9 Oz CP-ML 2 4 9 14 23 28 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 0 1 3 5 10 13 0 0 0 0 0 0 0 0 0 0 0 1
Fixture 11 Oz CP-ML 2 6 11 17 29 32 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 3 4 7 16 16 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 14 Oz CP-ML 8 21 24 34 42 44 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 2 7 9 13 9 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 16 Oz CP-ML 19 25 26 33 28 17 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP-ML 606 0 1
Instances Oz E-CP 165 0 1
Fixture 7 Oz CP-ML 0.63 0.77 0.55 1.37 2.28 1.35 0.08 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.06 0.09
Oz E-CP 0.35 0.44 0.45 0.28 0.49 0.69 0.08 0.07 0.08 0.07 0.07 0.07 0.08 0.08 0.07 0.07 0.07 0.09
Fixture 9 Oz CP-ML 0.53 0.38 0.54 1.24 2.92 1.9 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.06 0.06 0.06 0.05 0.05
Oz E-CP 0.43 0.25 0.55 0.34 1.03 0.82 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.06 0.06 0.06 0.06
Fixture 11 Oz CP-ML 0.38 0.45 0.92 1.0 1.46 1.6 0.07 0.06 0.06 0.06 0.06 0.05 0.06 0.06 0.05 0.05 0.05 0.05
Oz E-CP 0.16 0.15 0.31 0.35 0.69 0.32 0.07 0.06 0.06 0.06 0.07 0.06 0.06 0.06 0.06 0.05 0.05 0.05
Fixture 14 Oz CP-ML 0.38 0.88 0.78 0.68 0.54 1.23 0.05 0.04 0.05 0.04 0.04 0.04 0.05 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.05 0.21 0.06 0.08 0.35 0.51 0.05 0.05 0.04 0.04 0.04 0.04 0.05 0.05 0.04 0.04 0.04 0.04
Fixture 16 Oz CP-ML 0.19 0.18 0.28 0.05 0.22 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Avg. Time Oz CP-ML 0.83 0.06 0.05
Oz E-CP 0.31 0.06 0.05
1 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Oz CP 24 28 38 46 50 52 0 0 0 0 0 0 0 2 0 0 6 3
Fixture 7 Oz CP-ML 5 9 14 21 27 35 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 1 3 4 5 11 15 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 28 35 46 49 44 0 0 0 0 0 0 0 0 0 0 1 1
Fixture 9 Oz CP-ML 1 4 9 18 27 31 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 2 1 4 6 11 15 0 0 0 0 0 0 0 0 0 0 0 1
Oz CP 25 27 31 44 49 47 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 11 Oz CP-ML 2 7 11 18 31 34 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 3 4 8 17 16 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 33 38 41 51 45 0 0 0 0 0 0 0 0 0 1 0 0
Fixture 14 Oz CP-ML 8 22 25 34 44 42 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 2 7 9 14 8 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 23 31 29 31 25 13 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 16 Oz CP-ML 19 25 25 33 28 17 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP 1069 0 14
Instances Oz CP-ML 626 0 1
Oz E-CP 170 0 1
Oz CP 0.22 0.48 0.32 0.41 0.77 1.1 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.23 0.22
Fixture 7 Oz CP-ML 1.21 1.35 1.84 2.41 3.29 3.09 0.06 0.06 0.06 0.06 0.06 0.05 0.05 0.11 0.05 0.05 0.26 0.2
Oz E-CP 0.89 0.94 1.05 1.06 0.95 1.19 0.06 0.06 0.07 0.07 0.06 0.06 0.07 0.12 0.06 0.06 0.27 0.22
Oz CP 0.09 0.42 0.23 0.66 0.32 0.73 0.07 0.07 0.07 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.22
Fixture 9 Oz CP-ML 1.69 1.48 2.26 2.81 2.79 1.67 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.07 0.07
Oz E-CP 0.81 0.56 1.16 1.16 1.9 0.46 0.07 0.06 0.06 0.06 0.07 0.06 0.06 0.06 0.05 0.05 0.08 0.08
Oz CP 0.56 0.1 0.76 0.69 0.87 0.45 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.06 0.08 0.05 0.05 0.05
Fixture 11 Oz CP-ML 1.53 1.09 2.02 2.68 2.57 2.47 0.06 0.06 0.05 0.06 0.05 0.05 0.05 0.06 0.08 0.06 0.05 0.04
Oz E-CP 0.4 0.4 0.75 0.64 0.78 0.23 0.06 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.07 0.05 0.05 0.04
Oz CP 0.42 0.14 0.49 1.02 1.54 0.74 0.05 0.05 0.05 0.05 0.05 0.04 0.05 0.05 0.05 0.05 0.05 0.04
Fixture 14 Oz CP-ML 1.17 1.3 1.46 1.49 1.08 1.48 0.04 0.03 0.03 0.03 0.03 0.03 0.04 0.03 0.03 0.06 0.03 0.03
Oz E-CP 0.07 0.37 0.11 0.16 0.44 0.54 0.05 0.05 0.04 0.04 0.05 0.04 0.05 0.04 0.04 0.07 0.04 0.04
Oz CP 0.12 0.05 0.9 0.56 0.46 0.66 0.04 0.04 0.04 0.04 0.04 0.04 0.05 0.04 0.04 0.04 0.04 0.04
Fixture 16 Oz CP-ML 0.56 0.5 0.93 0.05 0.12 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.05 0.04 0.03 0.07 0.04 0.05 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz CP 0.51 0.06 0.07
Avg. Time Oz CP-ML 1.61 0.05 0.06
Oz E-CP 0.57 0.05 0.07
4 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Fixture 7 Oz CP-ML 4 8 15 18 26 37 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 1 3 4 5 11 18 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 9 Oz CP-ML 2 4 9 14 23 28 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 0 1 3 5 10 13 0 0 0 0 0 0 0 0 0 0 0 1
Fixture 11 Oz CP-ML 2 6 11 17 29 32 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 3 4 7 16 16 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 14 Oz CP-ML 8 21 24 34 42 44 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 2 2 7 9 13 9 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 16 Oz CP-ML 19 25 26 33 28 17 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP-ML 606 0 1
Instances Oz E-CP 165 0 1
Fixture 7 Oz CP-ML 0.63 0.77 0.55 1.37 2.28 1.35 0.08 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.06 0.09
Oz E-CP 0.35 0.44 0.45 0.28 0.49 0.69 0.08 0.07 0.08 0.07 0.07 0.07 0.08 0.08 0.07 0.07 0.07 0.09
Fixture 9 Oz CP-ML 0.53 0.38 0.54 1.24 2.92 1.9 0.07 0.07 0.07 0.07 0.07 0.06 0.07 0.06 0.06 0.06 0.05 0.05
Oz E-CP 0.43 0.25 0.55 0.34 1.03 0.82 0.07 0.07 0.07 0.07 0.07 0.07 0.07 0.06 0.06 0.06 0.06 0.06
Fixture 11 Oz CP-ML 0.38 0.45 0.92 1.0 1.46 1.6 0.07 0.06 0.06 0.06 0.06 0.05 0.06 0.06 0.05 0.05 0.05 0.05
Oz E-CP 0.16 0.15 0.31 0.35 0.69 0.32 0.07 0.06 0.06 0.06 0.07 0.06 0.06 0.06 0.06 0.05 0.05 0.05
Fixture 14 Oz CP-ML 0.38 0.88 0.78 0.68 0.54 1.23 0.05 0.04 0.05 0.04 0.04 0.04 0.05 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.05 0.21 0.06 0.08 0.35 0.51 0.05 0.05 0.04 0.04 0.04 0.04 0.05 0.05 0.04 0.04 0.04 0.04
Fixture 16 Oz CP-ML 0.19 0.18 0.28 0.05 0.22 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Oz E-CP 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04 0.04
Avg. Time Oz CP-ML 0.83 0.06 0.05
Oz E-CP 0.31 0.06 0.05
Table 4.  Unsolved instances and average running times for the Argentine league (30 teams) evaluated sequentially and in parallel with the CP, CP-ML, and E-CP models using Mozart-Oz
1 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Oz CP 31 37 44 52 68 67 0 0 0 0 0 0 0 0 0 0 0 7
Fixture 5 Oz CP-ML 11 16 24 28 47 49 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 9 14 15 21 36 33 0 0 0 0 0 0 0 0 0 0 0 1
Oz CP 28 37 45 56 69 67 0 0 0 0 0 0 0 0 0 1 4 3
Fixture 10 Oz CP-ML 6 12 18 27 42 46 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 5 9 10 19 27 30 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 29 35 46 57 65 73 0 0 0 0 0 0 0 0 1 0 2 5
Fixture 15 Oz CP-ML 5 11 14 24 31 40 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 3 6 12 20 24 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 33 36 43 65 67 63 0 0 0 0 0 0 0 0 0 0 1 3
Fixture 20 Oz CP-ML 8 14 17 30 41 47 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 9 10 30 33 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 29 39 35 38 37 28 0 0 0 0 0 0 0 0 0 0 1 0
Fixture 25 Oz CP-ML 23 27 28 36 34 26 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 1 2 4 3 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP 1419 0 28
Instances Oz CP-ML 782 0 1
Oz E-CP 396 0 1
Oz CP 0.23 0.46 0.21 0.23 0.31 0.89 0.56 0.53 0.51 0.5 0.5 0.49 0.43 0.44 0.4 0.39 0.38 0.34
Fixture 5 Oz CP-ML 2.1 2.98 2.72 3.38 3.98 3.82 0.28 0.27 0.27 0.28 0.3 0.34 0.32 0.31 0.3 0.28 0.26 0.44
Oz E-CP 1.82 1.88 2.54 2.26 2.79 3.84 0.49 0.49 0.49 0.49 0.47 0.46 0.44 0.41 0.41 0.38 0.37 0.51
Oz CP 0.33 0.2 0.24 0.35 0.18 0.41 0.37 0.39 0.39 0.39 0.38 0.37 0.34 0.34 0.32 0.32 0.28 0.25
Fixture 10 Oz CP-ML 1.69 2.35 2.55 3.3 3.4 3.85 0.27 0.28 0.29 0.29 0.28 0.27 0.25 0.24 0.23 0.26 0.45 0.29
Oz E-CP 1.35 1.51 2.26 2.17 2.69 2.4 0.38 0.37 0.38 0.36 0.37 0.34 0.32 0.32 0.3 0.32 0.51 0.33
Oz CP 0.48 0.2 0.14 0.56 0.43 0.14 0.29 0.29 0.33 0.32 0.29 0.31 0.27 0.28 0.26 0.23 0.19 0.21
Fixture 15 Oz CP-ML 1.59 1.79 2.85 3.38 4.36 5.03 0.21 0.21 0.22 0.22 0.21 0.2 0.19 0.19 0.23 0.17 0.23 0.4
Oz E-CP 1.27 1.26 2.04 2.39 2.9 3.12 0.28 0.28 0.28 0.28 0.27 0.25 0.23 0.2 0.19 0.15 0.19 0.38
Oz CP 0.12 0.71 0.26 0.7 0.12 0.24 0.19 0.21 0.22 0.22 0.2 0.18 0.19 0.18 0.18 0.16 0.14 0.12
Fixture 20 Oz CP-ML 1.49 1.7 2.43 4.33 3.05 2.81 0.15 0.14 0.14 0.14 0.14 0.13 0.14 0.14 0.14 0.13 0.14 0.19
Oz E-CP 0.8 1.28 1.41 2.33 1.95 1.49 0.14 0.14 0.14 0.13 0.12 0.12 0.11 0.11 0.12 0.11 0.13 0.18
Oz CP 0.07 0.22 0.42 0.13 0.12 0.07 0.09 0.08 0.08 0.07 0.06 0.06 0.1 0.1 0.1 0.09 0.07 0.08
Fixture 25 Oz CP-ML 0.59 1.3 0.68 0.24 0.28 0.18 0.06 0.05 0.05 0.05 0.04 0.04 0.07 0.07 0.06 0.06 0.08 0.05
Oz E-CP 0.17 0.06 0.21 0.21 0.44 0.09 0.09 0.08 0.08 0.07 0.06 0.06 0.09 0.09 0.09 0.08 0.11 0.07
Oz CP 0.29 0.3 0.24
Avg. Time Oz CP-ML 2.38 0.19 0.21
Oz E-CP 1.6 0.26 0.24
4 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Fixture 5 Oz CP-ML 10 17 21 26 48 49 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 9 15 16 18 37 32 0 0 0 0 0 0 0 0 0 0 0 1
Fixture 10 Oz CP-ML 6 12 17 26 38 47 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 4 8 11 19 25 28 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 15 Oz CP-ML 5 10 12 19 33 38 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 4 3 5 11 21 26 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 20 Oz CP-ML 8 16 17 30 40 44 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 3 9 10 30 32 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 25 Oz CP-ML 22 27 28 36 34 26 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 1 2 4 3 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP-ML 762 0 1
Instances Oz E-CP 393 0 1
Fixture 5 Oz CP-ML 1.02 1.22 1.35 2.15 1.72 1.91 0.46 0.45 0.47 0.45 0.45 0.44 0.4 0.4 0.39 0.37 0.36 0.32
Oz E-CP 0.78 0.74 1.41 2.01 1.63 2.13 0.45 0.44 0.45 0.46 0.44 0.43 0.39 0.39 0.39 0.36 0.35 0.32
Fixture 10 Oz CP-ML 0.86 0.88 0.91 1.72 2.37 1.69 0.36 0.36 0.36 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.33 0.25
Oz E-CP 0.95 0.62 0.77 0.69 0.92 1.2 0.3 0.32 0.34 0.34 0.34 0.33 0.33 0.31 0.29 0.29 0.31 0.25
Fixture 15 Oz CP-ML 0.57 0.7 1.42 2.18 1.58 3.19 0.28 0.27 0.27 0.27 0.26 0.25 0.23 0.23 0.23 0.21 0.2 0.23
Oz E-CP 0.32 0.42 1.07 0.9 1.23 1.32 0.27 0.27 0.27 0.27 0.26 0.25 0.23 0.24 0.23 0.21 0.2 0.22
Fixture 20 Oz CP-ML 0.45 0.46 0.81 2.21 0.69 2.43 0.19 0.18 0.18 0.18 0.17 0.15 0.17 0.16 0.16 0.16 0.14 0.11
Oz E-CP 0.25 0.62 0.54 1.21 0.82 1.59 0.18 0.17 0.17 0.17 0.15 0.15 0.15 0.14 0.15 0.14 0.12 0.11
Fixture 25 Oz CP-ML 0.49 0.51 0.25 0.16 0.32 0.13 0.08 0.07 0.07 0.07 0.05 0.05 0.08 0.09 0.08 0.08 0.08 0.07
Oz E-CP 0.08 0.07 0.19 0.07 0.08 0.08 0.07 0.06 0.07 0.06 0.05 0.05 0.08 0.08 0.08 0.07 0.07 0.06
Avg. Time Oz CP-ML 1.15 0.26 0.22
Oz E-CP 0.77 0.25 0.22
1 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Oz CP 31 37 44 52 68 67 0 0 0 0 0 0 0 0 0 0 0 7
Fixture 5 Oz CP-ML 11 16 24 28 47 49 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 9 14 15 21 36 33 0 0 0 0 0 0 0 0 0 0 0 1
Oz CP 28 37 45 56 69 67 0 0 0 0 0 0 0 0 0 1 4 3
Fixture 10 Oz CP-ML 6 12 18 27 42 46 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 5 9 10 19 27 30 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 29 35 46 57 65 73 0 0 0 0 0 0 0 0 1 0 2 5
Fixture 15 Oz CP-ML 5 11 14 24 31 40 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 3 6 12 20 24 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 33 36 43 65 67 63 0 0 0 0 0 0 0 0 0 0 1 3
Fixture 20 Oz CP-ML 8 14 17 30 41 47 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 9 10 30 33 0 0 0 0 0 0 0 0 0 0 0 0
Oz CP 29 39 35 38 37 28 0 0 0 0 0 0 0 0 0 0 1 0
Fixture 25 Oz CP-ML 23 27 28 36 34 26 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 1 2 4 3 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP 1419 0 28
Instances Oz CP-ML 782 0 1
Oz E-CP 396 0 1
Oz CP 0.23 0.46 0.21 0.23 0.31 0.89 0.56 0.53 0.51 0.5 0.5 0.49 0.43 0.44 0.4 0.39 0.38 0.34
Fixture 5 Oz CP-ML 2.1 2.98 2.72 3.38 3.98 3.82 0.28 0.27 0.27 0.28 0.3 0.34 0.32 0.31 0.3 0.28 0.26 0.44
Oz E-CP 1.82 1.88 2.54 2.26 2.79 3.84 0.49 0.49 0.49 0.49 0.47 0.46 0.44 0.41 0.41 0.38 0.37 0.51
Oz CP 0.33 0.2 0.24 0.35 0.18 0.41 0.37 0.39 0.39 0.39 0.38 0.37 0.34 0.34 0.32 0.32 0.28 0.25
Fixture 10 Oz CP-ML 1.69 2.35 2.55 3.3 3.4 3.85 0.27 0.28 0.29 0.29 0.28 0.27 0.25 0.24 0.23 0.26 0.45 0.29
Oz E-CP 1.35 1.51 2.26 2.17 2.69 2.4 0.38 0.37 0.38 0.36 0.37 0.34 0.32 0.32 0.3 0.32 0.51 0.33
Oz CP 0.48 0.2 0.14 0.56 0.43 0.14 0.29 0.29 0.33 0.32 0.29 0.31 0.27 0.28 0.26 0.23 0.19 0.21
Fixture 15 Oz CP-ML 1.59 1.79 2.85 3.38 4.36 5.03 0.21 0.21 0.22 0.22 0.21 0.2 0.19 0.19 0.23 0.17 0.23 0.4
Oz E-CP 1.27 1.26 2.04 2.39 2.9 3.12 0.28 0.28 0.28 0.28 0.27 0.25 0.23 0.2 0.19 0.15 0.19 0.38
Oz CP 0.12 0.71 0.26 0.7 0.12 0.24 0.19 0.21 0.22 0.22 0.2 0.18 0.19 0.18 0.18 0.16 0.14 0.12
Fixture 20 Oz CP-ML 1.49 1.7 2.43 4.33 3.05 2.81 0.15 0.14 0.14 0.14 0.14 0.13 0.14 0.14 0.14 0.13 0.14 0.19
Oz E-CP 0.8 1.28 1.41 2.33 1.95 1.49 0.14 0.14 0.14 0.13 0.12 0.12 0.11 0.11 0.12 0.11 0.13 0.18
Oz CP 0.07 0.22 0.42 0.13 0.12 0.07 0.09 0.08 0.08 0.07 0.06 0.06 0.1 0.1 0.1 0.09 0.07 0.08
Fixture 25 Oz CP-ML 0.59 1.3 0.68 0.24 0.28 0.18 0.06 0.05 0.05 0.05 0.04 0.04 0.07 0.07 0.06 0.06 0.08 0.05
Oz E-CP 0.17 0.06 0.21 0.21 0.44 0.09 0.09 0.08 0.08 0.07 0.06 0.06 0.09 0.09 0.09 0.08 0.11 0.07
Oz CP 0.29 0.3 0.24
Avg. Time Oz CP-ML 2.38 0.19 0.21
Oz E-CP 1.6 0.26 0.24
4 Core Experiments
Constraint Type $P$ Queries $R$ Queries $S$ Queries
Fixture 5 Oz CP-ML 10 17 21 26 48 49 0 0 0 0 0 0 0 0 0 0 0 1
Oz E-CP 9 15 16 18 37 32 0 0 0 0 0 0 0 0 0 0 0 1
Fixture 10 Oz CP-ML 6 12 17 26 38 47 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 4 8 11 19 25 28 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 15 Oz CP-ML 5 10 12 19 33 38 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 4 3 5 11 21 26 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 20 Oz CP-ML 8 16 17 30 40 44 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 3 9 10 30 32 0 0 0 0 0 0 0 0 0 0 0 0
Fixture 25 Oz CP-ML 22 27 28 36 34 26 0 0 0 0 0 0 0 0 0 0 0 0
Oz E-CP 3 1 1 2 4 3 0 0 0 0 0 0 0 0 0 0 0 0
Unsolved Oz CP-ML 762 0 1
Instances Oz E-CP 393 0 1
Fixture 5 Oz CP-ML 1.02 1.22 1.35 2.15 1.72 1.91 0.46 0.45 0.47 0.45 0.45 0.44 0.4 0.4 0.39 0.37 0.36 0.32
Oz E-CP 0.78 0.74 1.41 2.01 1.63 2.13 0.45 0.44 0.45 0.46 0.44 0.43 0.39 0.39 0.39 0.36 0.35 0.32
Fixture 10 Oz CP-ML 0.86 0.88 0.91 1.72 2.37 1.69 0.36 0.36 0.36 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.33 0.25
Oz E-CP 0.95 0.62 0.77 0.69 0.92 1.2 0.3 0.32 0.34 0.34 0.34 0.33 0.33 0.31 0.29 0.29 0.31 0.25
Fixture 15 Oz CP-ML 0.57 0.7 1.42 2.18 1.58 3.19 0.28 0.27 0.27 0.27 0.26 0.25 0.23 0.23 0.23 0.21 0.2 0.23
Oz E-CP 0.32 0.42 1.07 0.9 1.23 1.32 0.27 0.27 0.27 0.27 0.26 0.25 0.23 0.24 0.23 0.21 0.2 0.22
Fixture 20 Oz CP-ML 0.45 0.46 0.81 2.21 0.69 2.43 0.19 0.18 0.18 0.18 0.17 0.15 0.17 0.16 0.16 0.16 0.14 0.11
Oz E-CP 0.25 0.62 0.54 1.21 0.82 1.59 0.18 0.17 0.17 0.17 0.15 0.15 0.15 0.14 0.15 0.14 0.12 0.11
Fixture 25 Oz CP-ML 0.49 0.51 0.25 0.16 0.32 0.13 0.08 0.07 0.07 0.07 0.05 0.05 0.08 0.09 0.08 0.08 0.08 0.07
Oz E-CP 0.08 0.07 0.19 0.07 0.08 0.08 0.07 0.06 0.07 0.06 0.05 0.05 0.08 0.08 0.08 0.07 0.07 0.06
Avg. Time Oz CP-ML 1.15 0.26 0.22
Oz E-CP 0.77 0.25 0.22
Table 5.  Test results using MiniZinc solvers and CPLEX for the Colombian League with 18 teams
Colombian League - 1 Core Test
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
G12/FD 8592 408 0.85 2.44 5851 2741
CP Gecode 8300 700 0.67 2.21 5584 2716
HaifaCSP 8949 51 0.36 1.79 6178 2771
G12/FD 8475 525 0.79 2.25 5701 2774
CP-R Gecode 8199 801 0.82 2.56 5664 2535
HaifaCSP 8997 3 0.15 0.75 6220 2777
CPLEX 8995 5 0.45 0.29 6216 2779
MIP G12/FD 8468 532 1.36 3.4 5769 2699
Gecode 8198 802 0.77 1.93 5499 2699
HaifaCSP 8916 84 0.61 2.07 6150 2766
Colombian League - 4 Core Test
CP Gecode 8427 573 0.49 1.99 5704 2723
HaifaCSP 8961 39 0.45 1.7 6202 2759
CP-R HaifaCSP 8994 6 0.16 0.34 6220 2774
MIP CPLEX 8999 1 0.47 0.28 6220 2779
HaifaCSP 8960 40 0.54 1.82 6207 2753
Colombian League - 1 Core Test
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
G12/FD 8592 408 0.85 2.44 5851 2741
CP Gecode 8300 700 0.67 2.21 5584 2716
HaifaCSP 8949 51 0.36 1.79 6178 2771
G12/FD 8475 525 0.79 2.25 5701 2774
CP-R Gecode 8199 801 0.82 2.56 5664 2535
HaifaCSP 8997 3 0.15 0.75 6220 2777
CPLEX 8995 5 0.45 0.29 6216 2779
MIP G12/FD 8468 532 1.36 3.4 5769 2699
Gecode 8198 802 0.77 1.93 5499 2699
HaifaCSP 8916 84 0.61 2.07 6150 2766
Colombian League - 4 Core Test
CP Gecode 8427 573 0.49 1.99 5704 2723
HaifaCSP 8961 39 0.45 1.7 6202 2759
CP-R HaifaCSP 8994 6 0.16 0.34 6220 2774
MIP CPLEX 8999 1 0.47 0.28 6220 2779
HaifaCSP 8960 40 0.54 1.82 6207 2753
Table 6.  Test results using MiniZinc solvers and CPLEX for the Argentine League with 30 teams
Argentine League - 1 Core Test
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
G12/FD 7635 1365 2.14 2.35 6166 1469
CP Gecode 7406 1594 1.5 1.72 5973 1433
HaifaCSP 8363 637 1.07 3.23 6821 1542
G12/FD 7389 1611 1.8 2.14 5839 1550
CP-R Gecode 7752 1248 1.48 2.12 6197 1555
HaifaCSP 8858 142 0.94 2.63 7280 1578
CPLEX 8979 21 1.42 1.63 7411 1568
MIP G12/FD 6401 2599 3.66 3.58 5176 1225
Gecode 6745 2255 1.56 2.54 5428 1317
HaifaCSP 8263 737 1.8 3.58 6742 1521
Argentine League - 4 Core Test
CP Gecode 7537 1463 0.93 1.77 6101 1436
HaifaCSP 8541 459 1.69 3.96 7017 1524
CP-R HaifaCSP 8912 88 1.36 2.98 7333 1579
MIP CPLEX 8921 79 1.12 2.19 7338 1583
HaifaCSP 8491 509 2.56 4.38 6988 1503
Argentine League - 1 Core Test
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
G12/FD 7635 1365 2.14 2.35 6166 1469
CP Gecode 7406 1594 1.5 1.72 5973 1433
HaifaCSP 8363 637 1.07 3.23 6821 1542
G12/FD 7389 1611 1.8 2.14 5839 1550
CP-R Gecode 7752 1248 1.48 2.12 6197 1555
HaifaCSP 8858 142 0.94 2.63 7280 1578
CPLEX 8979 21 1.42 1.63 7411 1568
MIP G12/FD 6401 2599 3.66 3.58 5176 1225
Gecode 6745 2255 1.56 2.54 5428 1317
HaifaCSP 8263 737 1.8 3.58 6742 1521
Argentine League - 4 Core Test
CP Gecode 7537 1463 0.93 1.77 6101 1436
HaifaCSP 8541 459 1.69 3.96 7017 1524
CP-R HaifaCSP 8912 88 1.36 2.98 7333 1579
MIP CPLEX 8921 79 1.12 2.19 7338 1583
HaifaCSP 8491 509 2.56 4.38 6988 1503
Table 7.  CPLEX(MIP) vs. Oz(E-CP) common solved instances comparison
Colombian League CPLEX(MIP) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
MIP CPLEX 89 83 6
E-CP Oz 8745 6091 2654
Argentine League CPLEX(MIP) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
MIP CPLEX 230 226 3
E-CP Oz 8320 6837 1481
Colombian League CPLEX(MIP) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
MIP CPLEX 89 83 6
E-CP Oz 8745 6091 2654
Argentine League CPLEX(MIP) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
MIP CPLEX 230 226 3
E-CP Oz 8320 6837 1481
Table 8.  HaifaCSP(CP-R) vs. Oz(E-CP) common solved instances comparison
Colombian League HaifaCSP(CP-R) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
CP-R HaifaCSP 1171 399 772
E-CP Oz 7223 5500 1723
Argentine League HaifaCSP(CP-R) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
CP-R HaifaCSP 599 231 368
E-CP Oz 7927 6809 1116
Colombian League HaifaCSP(CP-R) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
CP-R HaifaCSP 1171 399 772
E-CP Oz 7223 5500 1723
Argentine League HaifaCSP(CP-R) 4 cores vs Oz(E-CP) 4 cores
Model Solver Faster in SAT UNSAT
CP-R HaifaCSP 599 231 368
E-CP Oz 7927 6809 1116
Table 9.  Test results using MiniZinc solvers and CPLEX for the Colombian League with 18 teams
Colombian League - 4 Core Mixed Solvers Tests
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
E-CP & MIP Oz & CPLEX 8999 1 0.11 0.3 6220 2779
E-CP & CP-R Oz & HaifaCSP 8994 6 0.1 0.25 6220 2774
Colombian League - 4 Core Mixed Solvers Tests
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
E-CP & MIP Oz & CPLEX 8999 1 0.11 0.3 6220 2779
E-CP & CP-R Oz & HaifaCSP 8994 6 0.1 0.25 6220 2774
Table 10.  Test results using MiniZinc solvers and CPLEX for the Argentine League with 30 teams
Argentine League - 4 Core Mixed Solvers Tests
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
E-CP & MIP Oz & CPLEX 8958 42 0.56 1.74 7376 1582
E-CP & CP-R Oz & HaifaCSP 8940 60 0.62 2.05 7361 1579
Argentine League - 4 Core Mixed Solvers Tests
Model Solver Solved Instances Unsolved Instances Avg T. Solved Instances Std T. Solved Instances Solved SAT Instances Solved UNSAT Instances
E-CP & MIP Oz & CPLEX 8958 42 0.56 1.74 7376 1582
E-CP & CP-R Oz & HaifaCSP 8940 60 0.62 2.05 7361 1579
Table 11.  Number of solved instances at different time limits using the best model-solver configurations
Colombian League - 4 Core Test
Model Solver 1sec 10sec 20sec 30sec -(Total) Unsolved Instances
CP HaifaCSP 8279 8896 8948 8961 39
CP-R HaifaCSP 8845 8994 8994 8994 6
E-CP OZ 8756 8804 8832 8834 166
MIP CPLEX 8708 8998 8999 8999 1
E-CP & MIP OZ & CPLEX 8755 8999 8999 8999 1
Argentine League - 4 Core Test
CP HaifaCSP 6598 8157 8422 8541 459
CP-R HaifaCSP 6866 8673 8853 8912 88
E-CP OZ 8399 8571 8588 8606 394
MIP CPLEX 7481 8784 8900 8921 79
E-CP & MIP OZ & CPLEX 8399 8877 8946 8958 42
Colombian League - 4 Core Test
Model Solver 1sec 10sec 20sec 30sec -(Total) Unsolved Instances
CP HaifaCSP 8279 8896 8948 8961 39
CP-R HaifaCSP 8845 8994 8994 8994 6
E-CP OZ 8756 8804 8832 8834 166
MIP CPLEX 8708 8998 8999 8999 1
E-CP & MIP OZ & CPLEX 8755 8999 8999 8999 1
Argentine League - 4 Core Test
CP HaifaCSP 6598 8157 8422 8541 459
CP-R HaifaCSP 6866 8673 8853 8912 88
E-CP OZ 8399 8571 8588 8606 394
MIP CPLEX 7481 8784 8900 8921 79
E-CP & MIP OZ & CPLEX 8399 8877 8946 8958 42
[1]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[2]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-16. doi: 10.3934/jimo.2018079

[3]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[4]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[5]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-17. doi: 10.3934/jimo.2018058

[6]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[7]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[8]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[9]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[10]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[11]

Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial & Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347

[12]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[13]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[14]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

[15]

Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059

[16]

Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031

[17]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

[18]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[19]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497

[20]

James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (30)
  • HTML views (263)
  • Cited by (0)

[Back to Top]