-
"Computing Equivalent Transformations for Combinatorial
Optimization by Branch-and-Buond Search"
Eric I. Hsu and Sheila A. McIlraith
SoCS 2010
Presents "Minimum-Height Equivalent Transformation" process for
shifting fractional weights between constraint extensions within a
(MaxSAT) constraint optimization problem. Result is an equivalent
problem that induces a tighter lower bound during branch-and-bound
search, when using a specific height-based bounding technique.
Paper:
(.pdf)
Poster Describing Project:
(.pdf)
BibTeX:
(.bib)
-
"VARSAT: Integrating Probabilistic Inference with DPLL Search"
Eric I. Hsu and Sheila A. McIlraith
SAT 2009
Presents four novel message-passing techniques for approximating
marginal probabilities over Boolean satisfiability problems.
Introduces a complete backtracking (DPLL) solver that exploits such
techniques to guide its search process.
Paper:
(.pdf)
Presentation:
(.pdf)
BibTeX:
(.bib)
-
"Probabilistically Estimating Backbones and Variable Bias"
Eric I. Hsu, Christian J. Muise, J. Christopher Beck, and
Sheila A. McIlraith
CP 2008 (shorter version)
STAIR 2008, Technical Report CSRG-577 (longer versions)
Examines the concept variable bias, or the percentage of
solutions where a given variable holds a particular value. First
measures the ability of various probabilistic techniques to estimate
bias in isolation. Secondly, studies effective ways to embed bias
estimators within a full-featured DPLL SAT-solver, thus assessing the
importance of bias to heuristic search.
Shorter Paper:
(.pdf)
Longer Paper:
(.pdf)
Technical Report (Longest):
(.pdf)
Poster Describing Project:
(.pdf)
BibTeX:
(.bib)
Online Appendix
presents detailed experimental results and derivations.
-
"Using EM to Find Likely Assignments for Solving Constraint
Satisfaction Problems"
Eric I. Hsu, Matthew Kitching, Fahiem Bacchus, and Sheila A. McIlraith
AAAI 2007 (shorter, revised version)
NESCAI 2007 (longer, preliminary version)
Derives a variable and value ordering heuristic for solving
constraint satisfaction problems, using the Expecation Maximization
(EM) framework. Focuses on the "Quasigroup with Holes" combinatorial
problem, whose heavy-tailed empirical behavior is especially sensitive
to such ordering heuristics. Characterizes the operation of EM as
probabilistic local search alternating over the primal and dual
versions of a problem.
Shorter Paper:
(.pdf)
Shorter Presentation:
(.pdf)
Longer Paper:
(.pdf)
Longer Presentation:
(.pdf)
BibTeX:
(.bib)
-
"Characterizing Propagation Methods for Boolean Satisfiabilty"
Eric I. Hsu and Sheila A. McIlraith
SAT 2006
Presents Survey Propagation (SP) in standard Computer Science
terms, exhibiting connections to Belief Propagation (BP), local
search, and backbones/backdoors. Re-derives BP/SP within the
Expectation Maximization (EM) statistical framework, resulting in a
new version that always converges. More generally, suggests the
grouping of a variety of artificial intelligence, constraint
programming, and logical reasoning techniques within a single class of
primal/dual discrete optimization methods.
Paper: (.pdf)
Presentation: (.pdf)
BibTeX:
(.bib)
|
