Miquel Bofill
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Miquel Bofill has a total of 68 co-authors. Here are the top co-authors by number of shared publications:
- Mateu Villaret
Universitat de Girona, Girona, Spain
22 shared publications Mateu Villaret
11 shared publications- Albert Rubio
Complutense University of Madrid
9 shared publications - Josep Suy
Universitat de Girona
9 shared publications Josep Suy
7 shared publications- Felip Manyà
IIIA-CSIC, Bellaterra, Spain
6 shared publications
Latest Publications
- Open Access
- 9 July 2026
- Published by Elsevier in Journal of Logical and Algebraic Methods in Programming
- Vol. 151
Efficient SMT Formulations for Classical Planning
- 9 July 2026
- Published by Elsevier in Journal of Logical and Algebraic Methods in Programming
- Vol. 151
Open AccessEfficient SMT Formulations for Classical Planning
- Open Access
A Good Snowman is Hard to Plan
In this work we face a challenging puzzle video game: A Good Snowman is Hard to Build. The objective of the game is to build snowmen by moving and stacking snowballs on a discrete grid. For the sake of player engagement with the game, it is interesting to avoid that a player finds a much easier solution than the one the designer expected. Therefore, having tools that are able to certify the optimality of solutions is crucial. Although the game can be stated as a planning problem and can be naturally modelled in PDDL, we show that a direct translation to SAT clearly outperforms off-the-shelf state-of-the-art planners. As we show, this is mainly due to the fact that reachability properties can be easily modelled in SAT, allowing for shorter plans, whereas using axioms to express a reachability derived predicate in PDDL does not result in any significant reduction of solving time with the considered planners. We deal with a set of 51 levels, both original and crafted, solving 43 and with 8 challenging instances still remaining to be solved.
Open AccessA Good Snowman is Hard to Plan
In this work we face a challenging puzzle video game: A Good Snowman is Hard to Build. The objective of the game is to build snowmen by moving and stacking snowballs on a discrete grid. For the sake of player engagement with the game, it is interesting to avoid that a player finds a much easier solution than the one the designer expected. Therefore, having tools that are able to certify the optimality of solutions is crucial. Although the game can be stated as a planning problem and can be naturally modelled in PDDL, we show that a direct translation to SAT clearly outperforms off-the-shelf state-of-the-art planners. As we show, this is mainly due to the fact that reachability properties can be easily modelled in SAT, allowing for shorter plans, whereas using axioms to express a reachability derived predicate in PDDL does not result in any significant reduction of solving time with the considered planners. We deal with a set of 51 levels, both original and crafted, solving 43 and with 8 challenging instances still remaining to be solved.
- Open Access
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 6, 6853-6857
SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One Constraints (Extended Abstract)
When solving a combinatorial problem using propositional satisfiability (SAT), the encoding of the constraints is of vital importance. Pseudo-Boolean (PB) constraints appear frequently in a wide variety of problems. When PB constraints occur together with at-most-one (AMO) constraints over the same variables, they can be combined into PB(AMO) constraints. In this paper we present new encodings for PB(AMO) constraints. Our experiments show that these encodings can be substantially smaller than those of PB constraints and allow many more instances to be solved within a time limit. We also observed that there is no single overall winner among the considered encodings, but efficiency of each encoding may depend on PB(AMO) characteristics such as the magnitude of coefficient values.
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 6, 6853-6857
Open AccessSAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One Constraints (Extended Abstract)
When solving a combinatorial problem using propositional satisfiability (SAT), the encoding of the constraints is of vital importance. Pseudo-Boolean (PB) constraints appear frequently in a wide variety of problems. When PB constraints occur together with at-most-one (AMO) constraints over the same variables, they can be combined into PB(AMO) constraints. In this paper we present new encodings for PB(AMO) constraints. Our experiments show that these encodings can be substantially smaller than those of PB constraints and allow many more instances to be solved within a time limit. We also observed that there is no single overall winner among the considered encodings, but efficiency of each encoding may depend on PB(AMO) characteristics such as the magnitude of coefficient values.
- Open Access
- 11 August 2022
- Published by Springer Nature in International Journal of Computational Intelligence Systems
- Vol. 15 (1) , 1-12
The Impact of Implied Constraints on MaxSAT B2B Instances
The B2B scheduling optimization problem consists of finding a schedule of a set of meetings between pairs of participants, minimizing their number of idle time periods. Recent works have shown that SAT-based approaches are state-of-the-art on this problem. One interesting feature of such approaches is the use of implied constraints. In this work, we provide an experimental setting to study the impact of using these implied constraints in MaxSAT B2B instances. To this purpose and due to the reduced number of existing real-world B2B instances, we propose a random B2B instance generation model, which reproduces certain features of these problems. In our experimental analysis, we show that the impact of using some implied constraints in the MaxSAT encodings depends on the characteristics of the problem, and we also analyze the benefits of combining them. Finally, we give some insights on how a MaxSAT solver is able to exploit these implied constraints.
- 11 August 2022
- Published by Springer Nature in International Journal of Computational Intelligence Systems
- Vol. 15 (1) , 1-12
Open AccessThe Impact of Implied Constraints on MaxSAT B2B Instances
The B2B scheduling optimization problem consists of finding a schedule of a set of meetings between pairs of participants, minimizing their number of idle time periods. Recent works have shown that SAT-based approaches are state-of-the-art on this problem. One interesting feature of such approaches is the use of implied constraints. In this work, we provide an experimental setting to study the impact of using these implied constraints in MaxSAT B2B instances. To this purpose and due to the reduced number of existing real-world B2B instances, we propose a random B2B instance generation model, which reproduces certain features of these problems. In our experimental analysis, we show that the impact of using some implied constraints in the MaxSAT encodings depends on the characteristics of the problem, and we also analyze the benefits of combining them. Finally, we give some insights on how a MaxSAT solver is able to exploit these implied constraints.
- Open Access
- 8 February 2022
- Published by Elsevier in Computers & Operations Research
- Vol. 142
The Sample Analysis Machine Scheduling Problem: Definition and comparison of exact solving approaches
- 8 February 2022
- Published by Elsevier in Computers & Operations Research
- Vol. 142
Open AccessThe Sample Analysis Machine Scheduling Problem: Definition and comparison of exact solving approaches
- 1 January 2022
- Published by Elsevier in Artificial Intelligence
- Vol. 302
SAT encodings for Pseudo-Boolean constraints together with at-most-one constraints
- 1 January 2022
- Published by Elsevier in Artificial Intelligence
- Vol. 302
SAT encodings for Pseudo-Boolean constraints together with at-most-one constraints
- Open Access
- 1 November 2020
- Published by Elsevier in Computers & Industrial Engineering
- Vol. 149
SMT encodings for Resource-Constrained Project Scheduling Problems
- 1 November 2020
- Published by Elsevier in Computers & Industrial Engineering
- Vol. 149
Open AccessSMT encodings for Resource-Constrained Project Scheduling Problems
- 18 February 2020
- Published by Springer Nature in Artificial Intelligence Review
- Vol. 53 (7) , 5157-5188
An MDD-based SAT encoding for pseudo-Boolean constraints with at-most-one relations
- 18 February 2020
- Published by Springer Nature in Artificial Intelligence Review
- Vol. 53 (7) , 5157-5188
An MDD-based SAT encoding for pseudo-Boolean constraints with at-most-one relations
- 23 September 2019
- Published by Springer Nature
- p. 20-36
Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints
- 23 September 2019
- Published by Springer Nature
- p. 20-36
Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints
- 20 September 2019
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 19 (5-6) , 722-739
Resource Analysis driven by (Conditional) Termination Proofs
When programs feature a complex control flow, existing techniques for resource analysis produce cost relation systems (CRS) whose cost functions retain the complex flow of the program and, consequently, might not be solvable into closed-form upper bounds. This paper presents a novel approach to resource analysis that is driven by the result of a termination analysis. The fundamental idea is that the termination proof encapsulates the flows of the program which are relevant for the cost computation so that, by driving the generation of the CRS using the termination proof, we produce a linearly-bounded CRS (LB-CRS). A LB-CRS is composed of cost functions that are guaranteed to be locally bounded by linear ranking functions and thus greatly simplify the process of CRS solving. We have built a new resource analysis tool, named MaxCore, that is guided by the VeryMax termination analyzer and uses CoFloCo and PUBS as CRS solvers. Our experimental results on the set of benchmarks from the Complexity and Termination Competition 2019 for C Integer programs show that MaxCore outperforms all other resource analysis tools.
- 20 September 2019
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 19 (5-6) , 722-739
Resource Analysis driven by (Conditional) Termination Proofs
When programs feature a complex control flow, existing techniques for resource analysis produce cost relation systems (CRS) whose cost functions retain the complex flow of the program and, consequently, might not be solvable into closed-form upper bounds. This paper presents a novel approach to resource analysis that is driven by the result of a termination analysis. The fundamental idea is that the termination proof encapsulates the flows of the program which are relevant for the cost computation so that, by driving the generation of the CRS using the termination proof, we produce a linearly-bounded CRS (LB-CRS). A LB-CRS is composed of cost functions that are guaranteed to be locally bounded by linear ranking functions and thus greatly simplify the process of CRS solving. We have built a new resource analysis tool, named MaxCore, that is guided by the VeryMax termination analyzer and uses CoFloCo and PUBS as CRS solvers. Our experimental results on the set of benchmarks from the Complexity and Termination Competition 2019 for C Integer programs show that MaxCore outperforms all other resource analysis tools.