Abstract
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 preferences are maximally-satisfied. In this paper, we formally define the TCPC, prove that it is NP-hard and define a MaxSAT model of the problem. Moreover, we report on the results of an empirical investigation that show that solving the TCPC with MaxSAT solvers is a promising approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
The out-degree of a vertex is the number of edges going out of a vertex in a directed graph.
- 3.
Since most of the MaxSAT solvers deal with weights that are positive integers, in the experiments we multiply the weights by 100 and take the integer part.
References
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, pp. 80–96 (2013)
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, pp. 268–274 (2015)
Alberola, J.M., del Val, E., Sánchez-Anguix, V., Palomares, A., Teruel, M.D.: An artificial intelligence tool for heterogeneous team formation in the classroom. Knowl. Based Syst. 101, 1–14 (2016)
Alberola, J.M., del Val, E., Sanchez-Anguix, V., Julian, V.: Simulating a collective intelligence approach to student team formation. In: Pan, J.-S., Polycarpou, M.M., Woźniak, M., de Carvalho, A.C.P.L.F., Quintián, H., Corchado, E. (eds.) HAIS 2013. LNCS (LNAI), vol. 8073, pp. 161–170. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40846-5_17
Alsinet, T., Manyà, F., Planes, J.: An efficient solver for weighted Max-SAT. J. Glob. Optim. 41, 61–73 (2008)
Andrejczuk, E., Rodríguez-Aguilar, J.A., Roig, C., Sierra, C.: Synergistic team composition. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS, São Paulo, Brazil, pp. 1463–1465 (2017)
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, pp. 283–289 (2015)
Ansótegui, C., Gabàs, J., Malitsky, Y., Sellmann, M.: MaxSAT by improved instance-specific algorithm configuration. Artif. Intell. 235, 26–39 (2016)
Argelich, J., Li, C.M., Manyà, F., Planes, J.: The first and second Max-SAT evaluations. J. Satisfiability Boolean Model. Comput. 4, 251–278 (2008)
Argelich, J., Li, C.M., Manyà, F., Planes, J.: Analyzing the instances of the MaxSAT evaluation. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 360–361. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21581-0_29
Argelich, J., Manyà, F.: Exact Max-SAT solvers for over-constrained problems. J. Heuristics 12(4–5), 375–392 (2006)
Bonet, M.L., Levy, J., Manyà, F.: A complete calculus for Max-SAT. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 240–251. Springer, Heidelberg (2006). https://doi.org/10.1007/11814948_24
Costaguta, R.: Algorithms and machine learning techniques in collaborative group formation. In: Lagunas, O.P., Alcántara, O.H., Figueroa, G.A. (eds.) MICAI 2015. LNCS (LNAI), vol. 9414, pp. 249–258. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27101-9_18
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Li, C.M., 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)
Li, C.M., Manyà, F., Planes, J.: New inference rules for Max-SAT. J. Artif. Intell. Res. 30, 321–359 (2007)
Li, C.M., Manyà, F., Soler, J.R.: A clause tableaux calculus for MaxSAT. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI-2016, New York City, NY, USA, pp. 766–772 (2016)
Li, C.M., 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, pp. 605–610 (2011)
Li, C.M., Zhu, Z., Manyà, F., Simon, L.: Optimizing with minimum satisfiability. In: Artificial Intelligence, vol. 190, pp. 32–44 (2012)
Martins, R., Joshi, S., Manquinho, V., Lynce, I.: Incremental cardinality constraints for MaxSAT. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 531–548. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10428-7_39
Morgado, A., Heras, F., Liffiton, M.H., Planes, J., Marques-Silva, J.: Iterative and core-guided MaxSAT solving: a survey and assessment. Constraints 18(4), 478–534 (2013)
Sinz, C.: Towards an optimal CNF encoding of Boolean cardinality constraints. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 827–831. Springer, Heidelberg (2005). https://doi.org/10.1007/11564751_73
Acknowledgements
This work was supported by the Generalitat de Catalunya grant AGAUR 2014-SGR-118, and the MINECO-FEDER project RASO TIN2015-71799-C2-1-P. The second author is supported by grant PSPA-PNB-CGVyDI.324.2016 from Universidad Autónoma Metropolitana (Cuajimalpa), Mexico.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Manyà, F., Negrete, S., Roig, C., Soler, J.R. (2017). A MaxSAT-Based Approach to the Team Composition Problem in a Classroom. In: Sukthankar, G., Rodriguez-Aguilar, J. (eds) Autonomous Agents and Multiagent Systems. AAMAS 2017. Lecture Notes in Computer Science(), vol 10643. Springer, Cham. https://doi.org/10.1007/978-3-319-71679-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-71679-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71678-7
Online ISBN: 978-3-319-71679-4
eBook Packages: Computer ScienceComputer Science (R0)