Exploiting Partial-Assignment Enumeration in Optimization Modulo Theories
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910949544296448 |
|---|---|
| author | Masina, Gabriele Sebastiani, Roberto |
| author_facet | Masina, Gabriele Sebastiani, Roberto |
| contents | Optimization Modulo Theories (OMT) extends Satisfiability Modulo Theories (SMT) with the task of optimizing some objective function(s). In OMT solvers, a CDCL-based SMT solver enumerates theory-satisfiable total truth assignments, and a theory-specific procedure finds an optimum model for each of them; the current optimum is then used to tighten the search space for the next assignments, until no better solution is found.
In this paper, we analyze the role of truth-assignment enumeration in OMT. First, we spotlight that the enumeration of total truth assignments is suboptimal, since they may over-restrict the search space for the optimization procedure, whereas using partial truth assignments instead can improve the effectiveness of the optimization. Second, we propose some assignment-reduction techniques for exploiting partial-assignment enumeration within the OMT context. We implemented these techniques in the OptiMathSAT solver, and conducted an experimental evaluation on OMT benchmarks. The results confirm the improvement in both the efficiency of optimal solving and the quality of the obtained solutions for anytime solving. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_19963 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exploiting Partial-Assignment Enumeration in Optimization Modulo Theories Masina, Gabriele Sebastiani, Roberto Logic in Computer Science I.2.8 Optimization Modulo Theories (OMT) extends Satisfiability Modulo Theories (SMT) with the task of optimizing some objective function(s). In OMT solvers, a CDCL-based SMT solver enumerates theory-satisfiable total truth assignments, and a theory-specific procedure finds an optimum model for each of them; the current optimum is then used to tighten the search space for the next assignments, until no better solution is found. In this paper, we analyze the role of truth-assignment enumeration in OMT. First, we spotlight that the enumeration of total truth assignments is suboptimal, since they may over-restrict the search space for the optimization procedure, whereas using partial truth assignments instead can improve the effectiveness of the optimization. Second, we propose some assignment-reduction techniques for exploiting partial-assignment enumeration within the OMT context. We implemented these techniques in the OptiMathSAT solver, and conducted an experimental evaluation on OMT benchmarks. The results confirm the improvement in both the efficiency of optimal solving and the quality of the obtained solutions for anytime solving. |
| title | Exploiting Partial-Assignment Enumeration in Optimization Modulo Theories |
| topic | Logic in Computer Science I.2.8 |
| url | https://arxiv.org/abs/2502.19963 |