Skip to main content

RAZONAMIENTO FORMAL PARA TECNOLOGIAS FACILITADORAS Y EMERGENTES

RTI2018-094403-B-C33

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos I+D+i Retos de Investigación
Call year 2018
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Choosing the root of the tree decomposition when solving WCSPs: preliminary results

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Rollón Rico, Emma|||0000-0001-8021-9464
In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques., Projects RTI2018-094403-B-C33, funded by: FEDER/Ministerio de Ciencia e Innovación Agencia Estatal de Investigación,Spain, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Decision levels are stable: towards better SAT heuristics

  • Nieuwenhuis, Robert Lukas Mario|||0000-0002-6489-2138
  • Lozano Navarro, Adrián
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
We shed new light on the Literal Block Distance (LBD) and glue-based heuristics used in current SAT solvers. For this, we first introduce the concept of stickiness: given a run of a CDCL SAT solver, for each pair of literals we define, by a real value between 0 and 1, how sticky they are, basically, how frequently they are set at the same decision level. By means of a careful and detailed experimental setup and analysis, we confirm the following quite surprising fact: given a SAT instance, when running different CDCL SAT solvers on it, no matter their settings or random seeds, the stickiness relation between literals is always very similar, in a precisely defined sense. We analyze how quickly stickiness stabilizes in a run (quite quickly), and show that it is stable even under different encodings of cardinality constraints. We then describe how and why these solid new insights lead to heuristics refinements for SAT (and extensions, such as SMT) and improved information sharing in parallel solvers., Projects TIN2015-69175-C4-3-R (funded by FEDER/MINECO) and RTI2018-094403-B-C33 (funded by FEDER/Ministerio de Ciencia e Innovacion, Agencia Estatal de Investigacion, Spain), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Augmenting the power of (partial) MaxSat resolution with extension

  • Larrosa Bondia, Francisco Javier|||0000-0002-8322-0505
  • Rollón Rico, Emma|||0000-0001-8021-9464
The refutation power of SAT and MaxSAT resolution is challenged by problems like the soft and hard Pigeon Hole Problem PHP for which short refutations do not exist. In this paper we augment the MaxSAT resolution proof system with an extension rule. The new proof system MaxResE is sound and complete, and more powerful than plain MaxSAT resolution, since it can refute the soft and hard PHP in polynomial time. We show that MaxResE refutations actually subtract lower bounds from the objective function encoded by the formulas. The resulting formula is the residual after the lower bound extraction. We experimentally show that the residual of the soft PHP (once its necessary cost of 1 has been efficiently subtracted with MaxResE) is a concise, easy to solve, satisfiable problem., This work was funded partially by the Spanish MINECO and MICINN projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Choosing the root of the tree decomposition when solving WCSPs: preliminary results

  • Petrova, Aleksandra
  • Larrosa Bondia, Francisco Javier
  • Rollón Rico, Emma
In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques., Projects RTI2018-094403-B-C33, funded by: FEDER/Ministerio de Ciencia e Innovación Agencia Estatal de Investigación,Spain, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Augmenting the power of (partial) MaxSat resolution with extension

  • Larrosa Bondia, Francisco Javier
  • Rollón Rico, Emma
The refutation power of SAT and MaxSAT resolution is challenged by problems like the soft and hard Pigeon Hole Problem PHP for which short refutations do not exist. In this paper we augment the MaxSAT resolution proof system with an extension rule. The new proof system MaxResE is sound and complete, and more powerful than plain MaxSAT resolution, since it can refute the soft and hard PHP in polynomial time. We show that MaxResE refutations actually subtract lower bounds from the objective function encoded by the formulas. The resulting formula is the residual after the lower bound extraction. We experimentally show that the residual of the soft PHP (once its necessary cost of 1 has been efficiently subtracted with MaxResE) is a concise, easy to solve, satisfiable problem., This work was funded partially by the Spanish MINECO and MICINN projects TIN2015-69175-C4-3-R and RTI2018-094403-B-C33., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Decision levels are stable: towards better SAT heuristics

  • Nieuwenhuis, Robert Lukas Mario
  • Lozano Navarro, Adrián
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
We shed new light on the Literal Block Distance (LBD) and glue-based heuristics used in current SAT solvers. For this, we first introduce the concept of stickiness: given a run of a CDCL SAT solver, for each pair of literals we define, by a real value between 0 and 1, how sticky they are, basically, how frequently they are set at the same decision level. By means of a careful and detailed experimental setup and analysis, we confirm the following quite surprising fact: given a SAT instance, when running different CDCL SAT solvers on it, no matter their settings or random seeds, the stickiness relation between literals is always very similar, in a precisely defined sense. We analyze how quickly stickiness stabilizes in a run (quite quickly), and show that it is stable even under different encodings of cardinality constraints. We then describe how and why these solid new insights lead to heuristics refinements for SAT (and extensions, such as SMT) and improved information sharing in parallel solvers., Projects TIN2015-69175-C4-3-R (funded by FEDER/MINECO) and RTI2018-094403-B-C33 (funded by FEDER/Ministerio de Ciencia e Innovacion, Agencia Estatal de Investigacion, Spain), Peer Reviewed, Postprint (published version)