13 Search Results for "Hoos, Holger H."

Document
DOI: 10.4230/LIPIcs.CP.2024.5
ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization

Authors: Zhihan Chen, Peng Lin, Hao Hu, and Shaowei Cai

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LS-PBO. In this paper, firstly, we improve LS-PBO by a dynamic scoring mechanism, which dynamically strikes a balance between score on hard constraints and score on the objective function. Moreover, on top of this improved LS-PBO, we develop the first parallel local search PBO solver. The main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi.
Cite as

Zhihan Chen, Peng Lin, Hao Hu, and Shaowei Cai. ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CP.2024.5,
  author =	{Chen, Zhihan and Lin, Peng and Hu, Hao and Cai, Shaowei},
  title =	{{ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.5},
  URN =		{urn:nbn:de:0030-drops-206900},
  doi =		{10.4230/LIPIcs.CP.2024.5},
  annote =	{Keywords: Pseudo-Boolean Optimization, Parallel Solving, Local Search, Scoring Function, Solution Pool}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.6
Deep Cooperation of Local Search and Unit Propagation Techniques

Authors: Xiamin Chen, Zhendong Lei, and Pinyan Lu

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Local search (LS) is an efficient method for solving combinatorial optimization problems such as MaxSAT and Pseudo Boolean Problems (PBO). However, due to a lack of reasoning power and global information, LS methods get stuck at local optima easily. In contrast to the LS, Systematic Search utilizes unit propagation and clause learning techniques with strong reasoning capabilities to avoid falling into local optima. Nevertheless, the complete search is generally time-consuming to obtain a global optimal solution. This work proposes a deep cooperation framework combining local search and unit propagation to address their inherent disadvantages. First, we design a mechanism to detect when LS gets stuck, and then a well-designed unit propagation procedure is called upon to help escape the local optima. To the best of our knowledge, we are the first to integrate unit propagation technique within LS to overcome local optima. Experiments based on a broad range of benchmarks from MaxSAT Evaluations, PBO competitions, the Mixed Integer Programming Library, and three real-life cases validate that our method significantly improves three state-of-the-art MaxSAT and PBO local search solvers.
Cite as

Xiamin Chen, Zhendong Lei, and Pinyan Lu. Deep Cooperation of Local Search and Unit Propagation Techniques. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CP.2024.6,
  author =	{Chen, Xiamin and Lei, Zhendong and Lu, Pinyan},
  title =	{{Deep Cooperation of Local Search and Unit Propagation Techniques}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.6},
  URN =		{urn:nbn:de:0030-drops-206918},
  doi =		{10.4230/LIPIcs.CP.2024.6},
  annote =	{Keywords: PBO, Partial MaxSAT, LS, CDCL}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.19
An Efficient Local Search Solver for Mixed Integer Programming

Authors: Peng Lin, Mengchuan Zou, and Shaowei Cai

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Mixed integer programming (MIP) is a fundamental model in operations research. Local search is a powerful method for solving hard problems, but the development of local search solvers for MIP still needs to be explored. This work develops an efficient local search solver for solving MIP, called Local-MIP. We propose two new operators for MIP to adaptively modify variables for optimizing the objective function and satisfying constraints, respectively. Furthermore, we design a new weighting scheme to dynamically balance the priority between the objective function and each constraint, and propose a two-level scoring function structure to hierarchically guide the search for high-quality feasible solutions. Experiments are conducted on seven public benchmarks to compare Local-MIP with state-of-the-art MIP solvers, which demonstrate that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP and Feasibility Jump, and is competitive with the most powerful commercial solver Gurobi. Moreover, Local-MIP establishes 4 new records for MIPLIB open instances.
Cite as

Peng Lin, Mengchuan Zou, and Shaowei Cai. An Efficient Local Search Solver for Mixed Integer Programming. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.CP.2024.19,
  author =	{Lin, Peng and Zou, Mengchuan and Cai, Shaowei},
  title =	{{An Efficient Local Search Solver for Mixed Integer Programming}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.19},
  URN =		{urn:nbn:de:0030-drops-207041},
  doi =		{10.4230/LIPIcs.CP.2024.19},
  annote =	{Keywords: Mixed Integer Programming, Local Search, Operator, Scoring Function}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.31
Inverting Step-Reduced SHA-1 and MD5 by Parameterized SAT Solvers

Authors: Oleg Zaikin

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
MD5 and SHA-1 are fundamental cryptographic hash functions proposed in 1990s. Given a message of arbitrary finite size, MD5 produces a 128-bit hash in 64 steps, while SHA-1 produces a 160-bit hash in 80 steps. It is computationally infeasible to invert MD5 and SHA-1, i.e. to find a message given a hash. In 2012, 28-step MD5 and 23-step SHA-1 were inverted by CDCL solvers, yet no progress has been made since then. The present paper proposes to construct 31 intermediate inverse problems for any pair of MD5 or SHA-1 steps (i,i+1), such that the first problem is very close to inverting i steps, while the 31st one is almost inverting i+1 steps. We constructed SAT encodings of intermediate problems for MD5 and SHA-1, and tuned a CDCL solver on the simplest of them. Then the tuned solver was used to design a parallel Cube-and-Conquer solver which for the first time inverted 29-step MD5 and 24-step SHA-1.
Cite as

Oleg Zaikin. Inverting Step-Reduced SHA-1 and MD5 by Parameterized SAT Solvers. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zaikin:LIPIcs.CP.2024.31,
  author =	{Zaikin, Oleg},
  title =	{{Inverting Step-Reduced SHA-1 and MD5 by Parameterized SAT Solvers}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.31},
  URN =		{urn:nbn:de:0030-drops-207165},
  doi =		{10.4230/LIPIcs.CP.2024.31},
  annote =	{Keywords: cryptographic hash function, MD5, SHA-1, preimage attack, SAT, Cube-and-Conquer}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.38
Frugal Algorithm Selection (Short Paper)

Authors: Erdem Kuş, Özgür Akgün, Nguyen Dang, and Ian Miguel

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
When solving decision and optimisation problems, many competing algorithms (model and solver choices) have complementary strengths. Typically, there is no single algorithm that works well for all instances of a problem. Automated algorithm selection has been shown to work very well for choosing a suitable algorithm for a given instance. However, the cost of training can be prohibitively large due to running candidate algorithms on a representative set of training instances. In this work, we explore reducing this cost by choosing a subset of the training instances on which to train. We approach this problem in three ways: using active learning to decide based on prediction uncertainty, augmenting the algorithm predictors with a timeout predictor, and collecting training data using a progressively increasing timeout. We evaluate combinations of these approaches on six datasets from ASLib and present the reduction in labelling cost achieved by each option.
Cite as

Erdem Kuş, Özgür Akgün, Nguyen Dang, and Ian Miguel. Frugal Algorithm Selection (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kus_et_al:LIPIcs.CP.2024.38,
  author =	{Ku\c{s}, Erdem and Akg\"{u}n, \"{O}zg\"{u}r and Dang, Nguyen and Miguel, Ian},
  title =	{{Frugal Algorithm Selection}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.38},
  URN =		{urn:nbn:de:0030-drops-207239},
  doi =		{10.4230/LIPIcs.CP.2024.38},
  annote =	{Keywords: Algorithm Selection, Active Learning}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.19
RNA Inverse Folding Can Be Solved in Linear Time for Structures Without Isolated Stacks or Base Pairs

Authors: Théo Boury, Laurent Bulteau, and Yann Ponty

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Inverse folding is a classic instance of negative RNA design which consists in finding a sequence that uniquely folds into a target secondary structure with respect to energy minimization. A breakthrough result of Bonnet et al. shows that, even in simple base pairs-based (BP) models, the decision version of a mildly constrained version of inverse folding is NP-hard. In this work, we show that inverse folding can be solved in linear time for a large collection of targets, including every structure that contains no isolated BP and no isolated stack (or, equivalently, when all helices consist of 3^{+} base pairs). For structures featuring shorter helices, our linear algorithm is no longer guaranteed to produce a solution, but still does so for a large proportion of instances. Our approach introduces a notion of modulo m-separability, generalizing a property pioneered by Hales et al. Separability is a sufficient condition for the existence of a solution to the inverse folding problem. We show that, for any input secondary structure of length n, a modulo m-separated sequence can be produced in time 𝒪(n 2^m) anytime such a sequence exists. Meanwhile, we show that any structure consisting of 3^{+} base pairs is either trivially non-designable, or always admits a modulo-2 separated solution (m = 2). Solution sequences can thus be produced in linear time, and even be uniformly generated within the set of modulo-2 separable sequences.
Cite as

Théo Boury, Laurent Bulteau, and Yann Ponty. RNA Inverse Folding Can Be Solved in Linear Time for Structures Without Isolated Stacks or Base Pairs. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boury_et_al:LIPIcs.WABI.2024.19,
  author =	{Boury, Th\'{e}o and Bulteau, Laurent and Ponty, Yann},
  title =	{{RNA Inverse Folding Can Be Solved in Linear Time for Structures Without Isolated Stacks or Base Pairs}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.19},
  URN =		{urn:nbn:de:0030-drops-206632},
  doi =		{10.4230/LIPIcs.WABI.2024.19},
  annote =	{Keywords: RNA structure, String Design, Parameterized Complexity, Uniform Sampling}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.9
Lazy Reimplication in Chronological Backtracking

Authors: Robin Coutelier, Mathias Fleury, and Laura Kovács

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Chronological backtracking is an interesting SAT solving technique within CDCL reasoning, as it backtracks less aggressively upon conflicts. However, chronological backtracking is more difficult to maintain due to its weaker SAT solving invariants. This paper introduces a lazy reimplication procedure for missed lower implications in chronological backtracking. Our method saves propagations by reimplying literals on demand, rather than eagerly. Due to its modularity, our work can be replicated in other solvers, as shown by our results in the solvers CaDiCaL and Glucose.
Cite as

Robin Coutelier, Mathias Fleury, and Laura Kovács. Lazy Reimplication in Chronological Backtracking. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coutelier_et_al:LIPIcs.SAT.2024.9,
  author =	{Coutelier, Robin and Fleury, Mathias and Kov\'{a}cs, Laura},
  title =	{{Lazy Reimplication in Chronological Backtracking}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.9},
  URN =		{urn:nbn:de:0030-drops-205313},
  doi =		{10.4230/LIPIcs.SAT.2024.9},
  annote =	{Keywords: Chronological Backtracking, CDCL, Invariants, Watcher Lists}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.18
Global Benchmark Database

Authors: Markus Iser and Christoph Jabs

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
This paper presents Global Benchmark Database (GBD), a comprehensive suite of tools for provisioning and sustainably maintaining benchmark instances and their metadata. The availability of benchmark metadata is essential for many tasks in empirical research, e.g., for the data-driven compilation of benchmarks, the domain-specific analysis of runtime experiments, or the instance-specific selection of solvers. In this paper, we introduce the data model of GBD as well as its interfaces and provide examples of how to interact with them. We also demonstrate the integration of custom data sources and explain how to extend GBD with additional problem domains, instance formats and feature extractors.
Cite as

Markus Iser and Christoph Jabs. Global Benchmark Database. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 18:1-18:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{iser_et_al:LIPIcs.SAT.2024.18,
  author =	{Iser, Markus and Jabs, Christoph},
  title =	{{Global Benchmark Database}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{18:1--18:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.18},
  URN =		{urn:nbn:de:0030-drops-205405},
  doi =		{10.4230/LIPIcs.SAT.2024.18},
  annote =	{Keywords: Maintenance and Distribution of Benchmark Instances and their Features}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.27
Revisiting SATZilla Features in 2024

Authors: Hadar Shavit and Holger H. Hoos

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Boolean satisfiability (SAT) is an NP-complete problem with important applications, notably in hardware and software verification. Characterising a SAT instance by a set of features has shown great potential for various tasks, ranging from algorithm selection to benchmark generation. In this work, we revisit the widely used SATZilla features and introduce a new version of the tool used to compute them. In particular, we utilise a new preprocessor and SAT solvers, adjust the code to accommodate larger formulas, and determine better settings of the feature extraction time limits. We evaluate the extracted features on three downstream tasks: satisfiability prediction, running time prediction, and algorithm selection. We observe that our new tool is able to extract features from a broader range of instances than before. We show that the new version of the feature extractor produces features that achieve up to 26% lower RMSE for running time prediction, up to 3% higher accuracy for satisfiability prediction, and up to 15 times higher closed gap for algorithm selection on benchmarks from recent SAT competitions.
Cite as

Hadar Shavit and Holger H. Hoos. Revisiting SATZilla Features in 2024. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 27:1-27:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shavit_et_al:LIPIcs.SAT.2024.27,
  author =	{Shavit, Hadar and Hoos, Holger H.},
  title =	{{Revisiting SATZilla Features in 2024}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{27:1--27:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.27},
  URN =		{urn:nbn:de:0030-drops-205496},
  doi =		{10.4230/LIPIcs.SAT.2024.27},
  annote =	{Keywords: Satisfiability, feature extraction, running time prediction, satisfiability prediction}
}
Document
DOI: 10.4230/DagRep.13.11.72
Space and Artificial Intelligence (Dagstuhl Seminar 23461)

Authors: Sašo Džeroski, Holger H. Hoos, Bertrand Le Saux, Leendert van der Torre, and Ana Kostovska

Published in: Dagstuhl Reports, Volume 13, Issue 11 (2024)

Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 23461 "Space and Artificial Intelligence". The seminar was interdisciplinary, situated at the intersection of research on AI / computer science and space research. Since each of these is a very wide field on its own, we focussed on a selection of topics from each of the two and their intersections. On the artificial intelligence side, we focused on data-driven AI, which makes use of data in order to produce intelligent behaviour and notably includes machine learning approaches. We also considered knowledge-based AI, which is focussed on the explicit formalisation of human knowledge and its use for tasks such as reasoning, planning, and scheduling. On the space research side, we considered the two major branches of space operations (SO) and Earth observation (EO). The seminar brought together a diverse set of players, including researchers from academia, on one hand, and practitioners from space agencies (ESA, NASA) and industry, on the other hand. The seminar included plenary talks and parallel group discussions. Through the plenary talks, we obtained insight into the state-of-the-art in the different areas of AI research and space research, and especially in their intersections. Through the parallel group discussions, we identified obstacles and challenges to further progress and charted directions for further work.
Cite as

Sašo Džeroski, Holger H. Hoos, Bertrand Le Saux, Leendert van der Torre, and Ana Kostovska. Space and Artificial Intelligence (Dagstuhl Seminar 23461). In Dagstuhl Reports, Volume 13, Issue 11, pp. 72-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{dzeroski_et_al:DagRep.13.11.72,
  author =	{D\v{z}eroski, Sa\v{s}o and Hoos, Holger H. and Le Saux, Bertrand and van der Torre, Leendert and Kostovska, Ana},
  title =	{{Space and Artificial Intelligence (Dagstuhl Seminar 23461)}},
  pages =	{72--102},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{11},
  editor =	{D\v{z}eroski, Sa\v{s}o and Hoos, Holger H. and Le Saux, Bertrand and van der Torre, Leendert and Kostovska, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.11.72},
  URN =		{urn:nbn:de:0030-drops-198454},
  doi =		{10.4230/DagRep.13.11.72},
  annote =	{Keywords: Artificial Intelligence, Machine Learning, Data-based AI, Knowledge-based AI, Deep Learning, Foundation Models, Explainable Artificial Intelligence, Space Research, Space Operations, Earth Observation}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.43
Statistical Comparison of Algorithm Performance Through Instance Selection

Authors: Théo Matricon, Marie Anastacio, Nathanaël Fijalkow, Laurent Simon, and Holger H. Hoos

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Empirical performance evaluations, in competitions and scientific publications, play a major role in improving the state of the art in solving many automated reasoning problems, including SAT, CSP and Bayesian network structure learning (BNSL). To empirically demonstrate the merit of a new solver usually requires extensive experiments, with computational costs of CPU years. This not only makes it difficult for researchers with limited access to computational resources to test their ideas and publish their work, but also consumes large amounts of energy. We propose an approach for comparing the performance of two algorithms: by performing runs on carefully chosen instances, we obtain a probabilistic statement on which algorithm performs best, trading off between the computational cost of running algorithms and the confidence in the result. We describe a set of methods for this purpose and evaluate their efficacy on diverse datasets from SAT, CSP and BNSL. On all these datasets, most of our approaches were able to choose the correct algorithm with about 95% accuracy, while using less than a third of the CPU time required for a full comparison; the best methods reach this level of accuracy within less than 15% of the CPU time for a full comparison.
Cite as

Théo Matricon, Marie Anastacio, Nathanaël Fijalkow, Laurent Simon, and Holger H. Hoos. Statistical Comparison of Algorithm Performance Through Instance Selection. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{matricon_et_al:LIPIcs.CP.2021.43,
  author =	{Matricon, Th\'{e}o and Anastacio, Marie and Fijalkow, Nathana\"{e}l and Simon, Laurent and Hoos, Holger H.},
  title =	{{Statistical Comparison of Algorithm Performance Through Instance Selection}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{43:1--43:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.43},
  URN =		{urn:nbn:de:0030-drops-153346},
  doi =		{10.4230/LIPIcs.CP.2021.43},
  annote =	{Keywords: Performance assessment, early stopping, automated reasoning solvers}
}
Document
DOI: 10.4230/DagRep.8.9.154
Automating Data Science (Dagstuhl Seminar 18401)

Authors: Tijl De Bie, Luc De Raedt, Holger H. Hoos, and Padhraic Smyth

Published in: Dagstuhl Reports, Volume 8, Issue 9 (2019)

Abstract
Data science is concerned with the extraction of knowledge and insight, and ultimately societal or economic value, from data. It complements traditional statistics in that its object is data as it presents itself in the wild (often complex and heterogeneous, noisy, loosely structured, biased, etc.), rather than well-structured data sampled in carefully designed studies. It also has a strong computer science focus, and is related to popular areas such as big data, machine learning, data mining and knowledge discovery. Data science is becoming increasingly important with the abundance of big data, while the number of skilled data scientists is lagging. This has raised the question as to whether it is possible to automate data science in several contexts. First, from an artificial intelligence perspective, it is interesting to investigate whether (data) science (or portions of it) can be automated, as it is an activity currently requiring high levels of human expertise. Second, the field of machine learning has a long-standing interest in applying machine learning at the meta-level, in order to obtain better machine learning algorithms, yielding recent successes in automated parameter tuning, algorithm configuration and algorithm selection. Third, there is an interest in automating not only the model building process itself (cf. the Automated Statistician) but also in automating the preprocessing steps (data wrangling). This Dagstuhl seminar brought together researchers from all areas concerned with data science in order to study whether, to what extent, and how data science can be automated.
Cite as

Tijl De Bie, Luc De Raedt, Holger H. Hoos, and Padhraic Smyth. Automating Data Science (Dagstuhl Seminar 18401). In Dagstuhl Reports, Volume 8, Issue 9, pp. 154-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{debie_et_al:DagRep.8.9.154,
  author =	{De Bie, Tijl and De Raedt, Luc and Hoos, Holger H. and Smyth, Padhraic},
  title =	{{Automating Data Science  (Dagstuhl Seminar 18401)}},
  pages =	{154--181},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{9},
  editor =	{De Bie, Tijl and De Raedt, Luc and Hoos, Holger H. and Smyth, Padhraic},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.9.154},
  URN =		{urn:nbn:de:0030-drops-103443},
  doi =		{10.4230/DagRep.8.9.154},
  annote =	{Keywords: artificial intelligence, automated machine learning, automated scientific discovery, data science, inductive programming}
}
Document
DOI: 10.4230/DagRep.6.10.33
Automated Algorithm Selection and Configuration (Dagstuhl Seminar 16412)

Authors: Holger H. Hoos, Frank Neumann, and Heike Trautmann

Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 16412 "Automated Algorithm Selection and Configuration", which was held October 9--14, 2016 and attended by 34 experts from 10 countries. Research on automated algorithm selection and configuration has lead to some of the most impressive successes within the broader area of empirical algorithmics, and has proven to be highly relevant to industrial applications. Specifically, high-performance algorithms for cnp-hard problems, such as propositional satisfiability (SAT) and mixed integer programming (MIP), are known to have a huge impact on sectors such as manufacturing, logistics, healthcare, finance, agriculture and energy systems, and algorithm selection and configuration techniques have been demonstrated to achieve substantial improvements in the performance of solvers for these problems. Apart from creating synergy through close interaction between the world's leading groups in the area, the seminar pursued two major goals: to promote and develop deeper understanding of the behaviour of algorithm selection and configuration techniques and to lay the groundwork for further improving their efficacy. Towards these ends, the organisation team brought together a group of carefully chosen researchers with strong expertise in computer science, statistics, mathematics, economics and engineering; a particular emphasis was placed on bringing together theorists, empiricists and experts from various application areas, with the goal of closing the gap between theory and practice.
Cite as

Holger H. Hoos, Frank Neumann, and Heike Trautmann. Automated Algorithm Selection and Configuration (Dagstuhl Seminar 16412). In Dagstuhl Reports, Volume 6, Issue 10, pp. 33-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{hoos_et_al:DagRep.6.10.33,
  author =	{Hoos, Holger H. and Neumann, Frank and Trautmann, Heike},
  title =	{{Automated Algorithm Selection and Configuration (Dagstuhl Seminar 16412)}},
  pages =	{33--74},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{10},
  editor =	{Hoos, Holger H. and Neumann, Frank and Trautmann, Heike},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.10.33},
  URN =		{urn:nbn:de:0030-drops-69569},
  doi =		{10.4230/DagRep.6.10.33},
  annote =	{Keywords: algorithm configuration, algorithm selection, features, machine learning, optimisation, performance prediction}
}
  • Refine by Author
  • 5 Hoos, Holger H.
  • 2 Cai, Shaowei
  • 2 Lin, Peng
  • 1 Akgün, Özgür
  • 1 Anastacio, Marie
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Constraint and logic programming
  • 2 Theory of computation → Automated reasoning
  • 2 Theory of computation → Randomized local search
  • 1 Applied computing → Aerospace
  • 1 Applied computing → Astronomy
  • Show More...

  • Refine by Keyword
  • 2 CDCL
  • 2 Local Search
  • 2 Scoring Function
  • 1 Active Learning
  • 1 Algorithm Selection
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 10 2024
  • 1 2017
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact