Please use this identifier to cite or link to this item:
http://repositorio.udec.cl/jspui/handle/11594/11588
Title: | Anytime automatic algorithm selection for the Pseudo-Boolean Optimization problem. |
Authors: | Godoy del Campo, Julio Asín Achá, Roberto Pezo Vergara, Catalina |
Issue Date: | 2023 |
Publisher: | Universidad de Concepción |
Abstract: | Machine learning (ML) techniques have been proposed to automatically select the best solver from a portfolio of solvers, based on predicted performance. These techniques have been applied to various problems, such as Boolean Satisfiability, Traveling Salesperson, Graph Coloring, and others. These methods, known as meta-solvers, take an instance of a problem and a portfolio of solvers as input, then predict the best-performing solver and execute it to deliver a solution. Typically, the quality of the solution improves with a longer computational time. This has led to the development of anytime selectors, which consider both the instance and a user-prescribed computational time limit. Anytime meta-solvers predict the best-performing solver within the specified time limit. In this study, we focus on the task of designing anytime meta-solvers for the NP-hard optimization problem of Pseudo-Boolean Optimization (PBO). The effectiveness of our approach is demonstrated via extensive empirical study in which our anytime meta-solver improves dramatically on the performance of Mixed Integer Programming solver Gurobi, the best-performing single solver in the portfolio. |
Description: | Tesis presentada para optar al grado de Magíster en Ciencias de la Computación. |
URI: | http://repositorio.udec.cl/jspui/handle/11594/11588 |
Appears in Collections: | Ingeniería Informática y Ciencias de la Computación - Tesis Magister |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Pezo Vergara_Catalina Tesis.pdf | 1,96 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License