Título: Solutions  for  Hard   and  Soft  Constraints  Using  Optimized
Probabilistic  Satisfiability

Palestrante: Marcelo Finger

Abstract:
  Practical  problems often combine  real-world hard  constraints with
  soft  constraints involving  preferences, uncertainties  or flexible
  requirements.  A probability distribution  over the models that meet
  the hard  constraints is an answer  to such problems that  is in the
  spirit of incorporating soft constraints.

  We  propose  a   method  using  SAT-based  reasoning,  probabilistic
  reasoning and  linear programming that computes  such a distribution
  when soft constraints are interpreted as constraints whose violation
  is bound  by a  given probability.  The  method, called Optimized
  Probabilistic  Satisfiability (oPSAT), consists  of  a two-phase
  computation of a probability distribution over the set of valuations
  of  a SAT  formula.  Algorithms  for both  phases are  presented and
  their complexity is discussed.

  We also describe an application of the oPSAT technique to the problem of
  combinatorial materials discovery.