×

zbMATH — the first resource for mathematics

Portfolio approaches for constraint optimization problems. (English) Zbl 1335.90077
Summary: Within the Constraint Satisfaction Problems (CSP) context, a methodology that has proven to be particularly performant consists of using a portfolio of different constraint solvers. Nevertheless, comparatively few studies and investigations have been done in the world of Constraint Optimization Problems (COP). In this work, we provide a generalization to COP as well as an empirical evaluation of different state of the art existing CSP portfolio approaches properly adapted to deal with COP. The results obtained by measuring several evaluation metrics confirm the effectiveness of portfolios even in the optimization field, and could give rise to some interesting future research.

MSC:
90C27 Combinatorial optimization
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amadini, R., Gabbrielli, M., Mauro, J.: An empirical evaluation of portfolios approaches for solving CSPs. In: CPAIOR, Volume 7874 of Lecture Notes in Computer Science. Springer (2013) · Zbl 1382.68219
[2] Amadini, R., Gabbrielli, M., Mauro, J.: An enhanced features extractor for a portfolio of constraint solvers. In: SAC, pp. 1357-1359. ACM (2014)
[3] Amadini, R., Gabbrielli, M., Mauro, J.: Portfolio approaches for constraint optimization problems. In: LION, Volume 8426 of Lecture Notes in Computer Science, pp. 21-35. Springer (2014) · Zbl 1335.90077
[4] Amadini, R; Gabbrielli, M; Mauro, J, SUNNY: A lazy portfolio approach for constraint solving, TPLP, 14, 509-524, (2014) · Zbl 1307.68077
[5] Amadini, R., Stuckey, P.: Sequential time splitting and bounds communication for a portfolio of optimization solvers. In: CP. http://ww2.cs.mu.oz.au/pjs/papers/cp2014d.pdf (2014) · Zbl 1190.62080
[6] Arlot, S; Celisse, A, A survey of cross-validation procedures for model selection, Stat. Surv., 4, 40-79, (2010) · Zbl 1190.62080
[7] Algorithm Selection Library (COSEAL project). https://code.google.com/p/coseal/wiki/AlgorithmSelectionLibrary · Zbl 1190.62080
[8] Baral, C: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press (2003) · Zbl 1056.68139
[9] Becket, R: Specification of FlatZinc - Version 1.6. http://www.minizinc.org/downloads/doc-1.6/flatzinc-spec.pdf
[10] Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press (2009) · Zbl 1183.68568
[11] Borenstein, Y., Riccardo, P.: Kolmogorov complexity, optimization and hardness. In: Evolutionary Computation, pp. 112-119 (2006)
[12] Carchrae, T; Beck, JC, Applying machine learning to low-knowledge control of optimization algorithms, Comput. Intell., 21, 372-387, (2005)
[13] Chevaleyre, Y., Endriss, U., Lang, J., Maudet, N.: A short introduction to computational social choice. In: SOFSEM, volume 4362 of LNCS, pp. 51-69. Springer (2007) · Zbl 1131.91316
[14] Third International CSP Solver Competition 2008. http://www.cril.univ-artois.fr/CPAI09/ · Zbl 1307.68077
[15] Gomes, CP; Selman, B, Algorithm portfolios, Artif. Intell., 126, 43-62, (2001) · Zbl 0969.68047
[16] Gomes, C.P., Selman, B., Crato, N.: Heavy-tailed distributions in combinatorial search. In: CP, Volume 1330 of Lecture Notes in Computer Science, pp. 121-135. Springer (1997)
[17] Guo, H; Hsu, WH, A machine learning approach to algorithm selection for NP-hard optimization problems: A case study on the MPE problem, Annals OR, 156, 61-82, (2007) · Zbl 1145.68043
[18] Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The WEKA data mining software: An update. SIGKDD Explor. Newsl. 11(1) (2009)
[19] Hebrard, E., O’Mahony, E., O’Sullivan, B.: Constraint programming and combinatorial optimisation in numberjack. In: CPAIOR-10, Volume 6140 of LNCS, pp. 181-185. Springer-Verlag (2010)
[20] Hoos, H.H., Kaufmann, B., Schaub, T., Schneider, M.: Robust benchmark set selection for boolean constraint solvers. In: LION, Volume 7997 of Lecture Notes in Computer Science, pp. 138-152. Springer (2013)
[21] Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K.: Algorithm runtime prediction: The state of the art. CoRR, arXiv:1211.0906 (2012)
[22] Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: CP, Volume 6876 of Lecture Notes in Computer Science. Springer (2011)
[23] Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC - instance-specific algorithm configuration. In: ECAI, Volume 215 of Frontiers in Artificial Intelligence and Applications. IOS Press (2010)
[24] Knowles, J.D., Corne, D.: Towards landscape analyses to inform the design of hybrid local search for the multiobjective quadratic assignment problem. In: HIS, Volume 87 of Frontiers in Artificial Intelligence and Applications, pp. 271-279. IOS Press (2002)
[25] Kotthoff, L.: Algorithm selection for combinatorial search problems: A survey. CoRR, arXiv:1210.7959 (2012)
[26] Kroer, C., Malitsky, Y.: Feature filtering for instance-specific algorithm configuration. In: ICTAI, pp. 849-855. IEEE (2011)
[27] Leyton-Brown, K., Nudelman, E., Shoham, Y.: Learning the empirical hardness of optimization problems: The case of combinatorial auctions. In: CP, Volume 2470 of Lecture Notes in Computer Science, pp. 556-572. Springer (2002)
[28] Lobjois, L., Lemaître, M.: Branch and bound algorithm selection by performance prediction. In: AAAI/IAAI, pp. 353-358. AAAI Press / The MIT Press (1998) · Zbl 0341.68061
[29] Mackworth, AK, Consistency in networks of relations, Artif. Intell., 8, 99-118, (1977) · Zbl 0341.68061
[30] Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: IJCAI. IJCAI/AAAI (2013)
[31] Max-SAT 2013. http://maxsat.ia.udl.cat/introduction/
[32] Merz, P, Advanced fitness landscape analysis and the performance of memetic algorithms, Evol. Comput., 12, 303-325, (2004)
[33] Minizinc version 1.6. http://www.minizinc.org/download.html
[34] MiniZinc Challenge. http://www.minizinc.org/challenge2014/rules2014.html
[35] OMahony, E., Hebrard, E., Holland, A., Nugent, C., OSullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: AICS 08 (2009)
[36] Rice, JR, The algorithm selection problem, Adv. Comput., 15, 65-118, (1976)
[37] SAT Challenge 2012. http://baldur.iti.kit.edu/SAT-Challenge-2012/
[38] Smith-Miles, K.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1) (2008)
[39] Smith-Miles, K.A.: Towards insightful algorithm selection for optimisation using meta-learning concepts. In: IJCNN, pp. 4118-4124. IEEE (2008)
[40] Telelis, O., Stamatopoulos, P.: Combinatorial optimization through statistical instance-based learning. In: ICTAI, pp. 203-209 (2001) · Zbl 0341.68061
[41] Xu, L., Hutter, F., Shen, J., Hoos, H., Leyton-Brown, K.: SATzilla2012: Improved algorithm selection based on cost-sensitive classification models. Solver description, SAT Challenge 2012 (2012)
[42] Lin, X., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla-07: The design and analysis of an algorithm portfolio for SAT. In: CP, Volume 4741 of Lecture Notes in Computer Science. Springer (2007) · Zbl 0969.68047
[43] Lin, X., Hutter, F., Hoos, H.H., Leyton-brown, K.: Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming. In: RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.