Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Algorithm Portfolios for Noisy Optimization: Compare Solvers Early Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Portfolio Approaches for Constraint Optimization Problems

verfasst von : Roberto Amadini, Maurizio Gabbrielli, Jacopo Mauro

Erschienen in: Learning and Intelligent Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Within the Constraints Satisfaction Problems (CSP) context, a methodology that has proven to be particularly performant consists in 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. Experimental results confirm the effectiveness of portfolios even in the optimization field, and could give rise to some interesting future research.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Ranking Algorithms by Performance
Nächstes Kapitel AClib: A Benchmark Library for Algorithm Configuration
Fußnoten
1
Formally, \(\mathtt{MIN }(i) = \min V_i\) and \(\mathtt{MAX }(i) = \max V_i\) where \(V_i = \{ \mathtt{val }(s, i, T) \ . \ s \in U \}\). Note that a portfolio solver executing more than one solver for \(t < T\) seconds could produce a solution that is worse than \(\mathtt{MIN }(i)\). This however is very uncommon: in our experiments we noticed that the 0 score was assigned only to the solvers that did not find any solution.
 
2
FlatZinc [6] is the low level language that each solver uses for solving a given MiniZinc instance. A key feature of FlatZinc is that, starting from a general MiniZinc model, every solver can produce a specialized FlatZinc by redefining the global constraints definitions. We noticed that, especially for huge instances, the time needed for extracting features was strongly dominated by the FlatZinc conversion. However, for the instances of the final dataset this time was in average 10.36 s, with a maximum value of 504 s and a median value of 3.17 s.
 
3
Following [1] methodology, CPX won all the elections we simulated using different criteria, viz.: Borda, Approval, and Plurality.
 
4
The objective function of the best approach considered was obtained by replacing that of the IP problem defined in [18] (we use the very same notation) with:
$$\begin{aligned} \max \left[ C_1 \sum _y y_i + C_2 \sum _{i, S, t} \mathtt{score }(S, i, t) \cdot x_{S, t} + C_3 \sum _{S,t} t \cdot x_{S, t} \right] \end{aligned}$$
where \(C_1 = -C^2\), \(C_2 = C\), \(C_3 = -\frac{1}{C}\), and adding the constraint \(\sum _t x_{S,t} \le 1\), \(\forall S\).
 
5
For more details, we defer the interested reader to [37].
 
6
To conduct the experiments we used Intel Dual-Core 2.93 GHz computers with 3 MB of CPU cache, 2 GB of RAM, and Ubuntu 12.04 operating system. For keeping track of the solving times we considered the CPU time by exploiting Unix time command.
 
Literatur
1.
Amadini, R., Gabbrielli, M., Mauro, J.: An empirical evaluation of portfolios approaches for solving CSPs. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 316–324. Springer, Heidelberg (2013) CrossRef
2.
Amadini, R., Gabbrielli, M., Mauro, J.: SUNNY: a Simple and dynamic algorithm portfolio for solving CSPs. CoRR, abs/1311.3353 (2013)
3.
Amadini, R., Gabbrielli, M., Jacopo M.: An Enhanced Features Extractor for a Portfolio of Constraint Solvers. In: SAC (2014)
4.
5.
Baral, C.: Knowledge Representation Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge (2003)CrossRefMATH
6.
7.
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press, Amsterdam (2009)
8.
Borenstein, Y., Poli, R.: Kolmogorov complexity, Optimization and Hardness pp. 12–119. In Evolutionary Computation (2006)
9.
Carchrae, T., Beck, J.C.: Applying machine learning to low-knowledge control of optimization algorithms. Comput. Intell. 21(4), 372–387 (2005)CrossRefMathSciNet
10.
11.
12.
13.
Gomes, C.P., Selman, B., Crato, N.: Heavy-tailed distributions in combinatorial search. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330. Springer, Heidelberg (1997)
14.
Guo, H., Hsu, W.H.: A machine learning approach to algorithm selection for NP-hard optimization problems: a case study on the MPE problem. Ann. Oper. Res. 156(1), 61–82 (2007)CrossRefMATHMathSciNet
15.
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), 10–18 (2009)CrossRef
16.
Hoos, H.H., Kaufmann, B., Schaub, T., Schneider, M.: Robust benchmark set selection for boolean constraint solvers. In: Nicosia, G., Pardalos, P. (eds.) LION 7. LNCS, vol. 7997, pp. 138–152. Springer, Heidelberg (2013) CrossRef
17.
Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K.: Algorithm Runtime Prediction: The State of the Art. CoRR, abs/1211.0906 (2012)
18.
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 454–469. Springer, Heidelberg (2011) CrossRef
19.
Kadioglu, S., Malitsky, Y., Sellmann, M., Kevin T.: ISAC - Instance-specific algorithm configuration. In: ECAI (2010)
20.
Knowles, J.D., Corne, D.W: Towards landscape analyses to inform the design of hybrid local search for the multiobjective quadratic assignment problem. In: HIS (2002)
21.
Kotthoff, L.: Algorithm Selection for Combinatorial Search Problems: A Survey. CoRR, abs/1210.7959 (2012)
22.
Kroer, C., Malitsky, Y.: Feature filtering for instance-specific algorithm configuration. In: ICTAI (2011)
23.
Leyton-Brown, K., Nudelman, E., Shoham, Y.: The case of combinatorial auctions. In: CP, Learning the Empirical Hardness of Optimization Problems (2002)
24.
Lobjois, L., Lemaître, M.: Branch and bound algorithm selection by performance prediction. In: AAAI/IAAI (1998)
25.
26.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: IJCAI (2013)
27.
28.
Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004)CrossRefMathSciNet
29.
30.
31.
O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: AICS 08 (2009)
32.
Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)CrossRef
33.
34.
Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1), 1–25 (2008)CrossRef
35.
Smith-Miles, K.A.: Towards insightful algorithm selection for optimisation using meta-learning concepts. In: IJCNN (2008)
36.
Telelis, O., Stamatopoulos, P.: Combinatorial optimization through statistical instance-based learning. In: ICTAI (2001)
37.
Xu, L., Hutter, F., Shen, J., Hoos, H., Leyton-Brown, K.: SATzilla2012: improved algorithm selection based on cost-sensitive classification models. In: SAT Challenge, Solver description (2012)
38.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla-07: The design and analysis of an algorithm portfolio for SAT. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 712–727. Springer, Heidelberg (2007) CrossRef
39.
Xu, L., 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)
Metadaten
Titel
Portfolio Approaches for Constraint Optimization Problems
verfasst von
Roberto Amadini
Maurizio Gabbrielli
Jacopo Mauro
Copyright-Jahr
2014
Buch
Learning and Intelligent Optimization

Print ISBN: 978-3-319-09583-7

Electronic ISBN: 978-3-319-09584-4

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-09584-4_3