Solving the Team Composition Problem in a Classroom

• Autorzy: Manyà Felip , Negrete Santiago , Roig Carme , Soler Joan Ramon

Identyfikatory

DOI

10.3233/FI-2020-1933

• Języki publikacji: EN

Abstrakty

EN

Given a classroom containing a fixed number of students and a fixed number of tables that can be of different sizes, as well as a list of preferred classmates to sit with for each student, the team composition problem in a classroom (TCPC) is the problem of finding an assignment of students to tables in such a way that the preferences of students are maximally-satisfied. In this paper, we first formally define the TCPC, prove that it is NP-hard and define two different MaxSAT models of the problem, called maximizing and minimizing encoding. Then, we report on the results of an empirical investigation that show that solving the TCPC with MaxSAT solvers is a promising approach and provide evidence that the minimizing encoding outperforms the maximizing encoding. Finally, we illustrate how the proposed MaxSAT-based modeling approach is also well-suited for modeling other more complex team formation problems.

Słowa kluczowe

EN

encoding; MaxSAT; NP-hard; optimization solver; team creation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 174, nr 1
• Strony: 83--101
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Manyà Felip

• Artificial Intelligence Research Institute (IIIA, CSIC), Bellaterra, Spain

autor

Negrete Santiago

• Universidad Autónoma Metropolitana (DCCD, Cuajimalpa), CDMX, Mexico

autor

Roig Carme

• INS Torres i Bages, Hospitalet de Llobregat, Spain

autor

Soler Joan Ramon

• Artificial Intelligence Research Institute (IIIA, CSIC), Bellaterra, Spain

Bibliografia

• [1] Abramé A, Habet D. On the Resiliency of Unit Propagation to Max-Resolution. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI-2015, Buenos Aires, Argentina. 2015 pp. 268-274.
• [2] Alsinet T, Manyà F, Planes J. A Max-SAT Solver with Lazy Data Structures. In: Proceedings of the 9th Ibero-American Conference on Artificial Intelligence, IBERAMIA 2004, Puebla, México. Springer LNCS 3315, 2004 pp. 334-342. doi:10.1007/978-3-540-30498-2_34.
• [3] Alsinet T, Manyà F, Planes J. An efficient solver for Weighted Max-SAT. Journal of Global Optimization, 2008. 41:61-73. doi:10.1007/s10898-007-9166-9.
• [4] Ansótegui C, Didier F, Gabàs J. Exploiting the Structure of Unsatisfiable Cores in MaxSAT. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI, Buenos Aires, Argentina. 2015 pp. 283-289. ISBN:978-1-57735-738-4.
• [5] Ansótegui C, Gabàs J, Malitsky Y, Sellmann M. MaxSAT by improved instance-specific algorithm configuration. Artificial Intelligence, 2016. 235:26-39. URL https://doi.org/10.1016/j.artint.2015.12.006.
• [6] Argelich J, Li CM, Manyà F, Planes J. The First and Second Max-SAT Evaluations. Journal on Satisfiability, Boolean Modeling and Computation, 2008. 4:251-278. f88bc073bc50ab748bea3077a320a8a36133.pdf.
• [7] Argelich J, Li CM, Manyà F, Planes J. Analyzing the Instances of the MaxSAT Evaluation. In: Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT-2011, Ann Arbor, MI, USA. Springer LNCS 6695, 2011 pp. 360-361. doi:10.1007/978-3-642-21581-0_29.
• [8] Argelich J, Manyà F. Exact Max-SAT Solvers for Over-Constrained Problems. Journal of Heuristics, 2006. 12(4-5):375-392. doi:10.1007/s10732-006-7234-9.
• [9] Bonet ML, Levy J, Manyà F. A Complete Calculus for Max-SAT. In: Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, SAT-2006, Seattle, USA. Springer LNCS 4121, 2006 pp. 240-251. doi:10.1007/11814948_24.
• [10] Li CM, Manyà F. MaxSAT, Hard and Soft Constraints. In: Biere A, van Maaren H, Walsh T (eds.), Handbook of Satisfiability, pp. 613-631. IOS Press, 2009. doi:10.3233/978-1-58603-929-5-613.
• [11] Li CM, Manyà F, Planes J. New Inference Rules for Max-SAT. Journal of Artificial Intelligence Research, 2007. 30:321-359. doi:10.1613/jair.2215.
• [12] Li CM, Manyà F, Soler JR. A Clause Tableaux Calculus for MaxSAT. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI-2016, New York City, NY, USA. 2016 pp. 766-772. ISBN:978-1-57735-770-4.
• [13] Martins R, Joshi S, Manquinho VM, Lynce I. Incremental Cardinality Constraints for MaxSAT. In: Principles and Practice of Constraint Programming - 20th International Conference, CP, Lyon, France. 2014 pp. 531-548. doi:10.1007/978-3-319-10428-7_39.
• [14] Morgado A, Heras F, Liffiton MH, Planes J, Marques-Silva J. Iterative and core-guided MaxSAT solving: A survey and assessment. Constraints, 2013. 18(4):478-534. doi:10.1007/s10601-013-9146-2.
• [15] Alberola JM, del Val Noguera E, Sánchez-Anguix V, Julián V. Simulating a Collective Intelligence Approach to Student Team Formation. In: Hybrid Artificial Intelligent Systems - 8th International Conference, HAIS 2013, Salamanca, Spain. Proceedings. 2013 pp. 161-170. doi:10.1007/978-3-642-40846-5_17.
• [16] Andrejczuk E, Rodríguez-Aguilar JA, Roig C, Sierra C. Synergistic Team Composition. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS, São Paulo, Brazil. 2017 pp. 1463-1465.
• [17] Andrejczuk E, Rodríguez-Aguilar JA, Roig C, Sierra C. Synergistic Team Composition. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’17. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2017 pp. 1463-1465. URL http://dl.acm.org/citation.cfm?id=3091125.3091330.
• [18] Manyà F, Negrete S, Roig C, Soler JR. A MaxSAT-Based Approach to the Team Composition Problem in a Classroom. In: Autonomous Agents and Multiagent Systems - AAMAS 2017 Workshops, Visionary Papers, São Paulo, Brazil, Revised Selected Papers. Springer LNCS 10643, 2017 pp. 164-173. doi:10.1007/978-3-319-71679-4_11.
• [19] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979. ISBN-10:0716710455, 13:978-0716710455.
• [20] Sinz C. Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. In: Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming, CP-2005, Sitges, Spain. Springer LNCS 3709, 2005 pp. 827-831. doi:10.1007/11564751_73.
• [21] Abío I, Nieuwenhuis R, Oliveras A, Rodríguez-Carbonell E. A Parametric Approach for Smaller and Better Encodings of Cardinality Constraints. In: Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming, CP, Uppsala, Sweden. 2013 pp. 80-96. doi:10.1007/978-3-642-40627-0_9.
• [22] Bofill M, Coll J, Suy J, Villaret M. SAT Encodings of Pseudo-Boolean Constraints with At-Most-One Relations. In: Proceedings of the 16th International Conference, CPAIOR 2019, Thessaloniki, Greece. Springer LNCS 11494, 2019 pp. 112-128. doi:10.1007/978-3-030-19212-9_8.
• [23] Jung C. Psychological types. Princeton University Press. Princeton, 1971.
• [24] Wilde D. Teamology: The Construction and Organization of Effective Teams. Springer-Verlag, London, 2009. ISBN: 978-1-84800-386-6.
• [25] Wilde D. Post-Jungian Personality Theory for Individuals and Teams. SYDROSE LP, 2013. ISBN-061594454X, 9780615944548.
• [26] Gardner H, Hatch T. Educational implications of the theory of multiple intelligences. Educational researcher, 1989. 18(8):4-10. URL https://doi.org/10.3102/0013189X018008004.
• [27] Ahuja R, Magnanti T, Orlin J. Network flows: theory, algorithms, and applications. Prentice hall, 1993. ISBN: 0-13-617549-X.
• [28] Orlin JB. A faster strongly polynomial minimum cost flow algorithm. Operations research, 1993. 41(2):338-350. URL https://doi.org/10.1287/opre.41.2.338.
• [29] Irving RW. An efficient algorithm for the "stable roommates" problem. Journal of Algorithms, 1985. 6(4):577-595. URL https://doi.org/10.1016/0196-6774(85)90033-1.
• [30] Iwama K, Miyazaki S, Okamoto K. Stable roommates problem with triple rooms. In: Proceedings of the 10th Korea-Japan Joint Workshop on Algorithms and Computation. 2007 pp. 105-112.
• [31] Belbin R. Team Roles at Work: A Strategy for Human Resource Management. Butterworth-Heinemann, Oxford, 1993.
• [32] Aritzeta A, Swailes S, Senior B. Belbin’s team role model: Development, validity and applications for team building. Journal of Management Studies, 2007. 44(1):96-118. URL https://doi.org/10.1111/j.1467-6486.2007.00666.x.
• [33] Alberola JM, del Val E, Sánchez-Anguix V, Palomares A, Teruel MD. An artificial intelligence tool for heterogeneous team formation in the classroom. Knowl.-Based Syst., 2016. 101:1-14. doi:10.1016/j.knosys.2016.02.010.
• [34] Li CM, Zhu Z, Manyà F, Simon L. Minimum Satisfiability and Its Applications. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI-2011, Barcelona, Spain. 2011 pp. 605-610. doi:10.5591/978-1-57735-516-8/IJCAI11-108.
• [35] Li CM, Zhu Z, Manyà F, Simon L. Optimizing with Minimum Satisfiability. Artificial Intelligence, 2012. 190:32-44. URL https://doi.org/10.1016/j.artint.2012.05.004.
• [36] Costaguta R. Algorithms and Machine Learning Techniques in Collaborative Group Formation. In: Advances in Artificial Intelligence and Its Applications - 14th Mexican International Conference on Artificial Intelligence, MICAI 2015, Cuernavaca, Morelos, Mexico. Proceedings, Part II. 2015 pp. 249-258. doi:10.1007/978-3-319-27101-9_18.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).