Logo: University of Southern California

Events Calendar



Select a calendar:



Filter May Events by Event Type:


SUNMONTUEWEDTHUFRISAT
27
28
30
2
3

4
5
6
7
8
9
10

11
12
13
14
15
16
17

18
19
20
21
22
23
24

25
26
27
28
29
30
31


Conferences, Lectures, & Seminars
Events for May

  • CS Colloq: AND/OR Search Strategies for Combinatorial Optimization in Graphical Models

    Thu, May 01, 2008 @ 03:30 PM - 04:30 PM

    Thomas Lord Department of Computer Science

    Conferences, Lectures, & Seminars


    Title: AND/OR Search Strategies for Combinatorial Optimization in Graphical ModelsSpeaker: Radu Marinescu (UCI)Abstract:
    The AND/OR search space for graphical models is a new framework for search that is sensitive to the independencies in the model, often resulting in exponentially reduced complexities. The AND/OR search tree search is in most cases exponentially smaller (and never larger) than the OR search tree. The AND/OR search graph is exponential in the treewidth of the graph, while the OR search graph is exponential in the pathwidth. We introduce a new generation of depth-first Branch-and-Bound as well as best-first AND/OR search algorithms that explore the context minimal AND/OR graph for solving general constraint optimization problems over graphical models. In conjunction with the AND/OR search space we also investigate a class of partitioning-based heuristic functions, based on the Mini-Bucket approximation that was shown to be powerful for optimization problems in the context of OR search spaces. Since variable selection can have a dramatic impact on search performance, we also introduce a class of depth-first AND/OR Branch-and-Bound and best-first AND/OR search algorithms that can accommodate various dynamic variable ordering heuristics. An extensive empirical evaluation showed conclusively that the new AND/OR search approach improves considerably over the traditional OR search, on a variety of probabilistic and deterministic benchmarks. We next apply the AND/OR perspective to decision diagrams. We extend them with AND nodes capturing function structure decomposition, resulting in AND/OR Multi-Valued Decision Diagrams (AOMDDs). The AOMDD is a canonical form that compiles a graphical model and has size bounded exponentially by the treewidth, rather than pathwidth (as is the case for OR decision diagrams). We present an AND/OR search based algorithm for compiling AOMDDs, as representations of the optimal set of solutions of a constraint optimization problem. An extensive experimental evaluation proved the efficiency of the weighted AOMDD data structure.

    Location: Seaver Science Library (SSL) - 150

    Audiences: Everyone Is Invited

    Contact: CS Colloquia

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File