Arrow Research search

Author name cluster

Lars Otten

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

JAIR Journal 2017 Journal Article

AND/OR Branch-and-Bound on a Computational Grid

  • Lars Otten
  • Rina Dechter

We present a parallel AND/OR Branch-and-Bound scheme that uses the power of a computational grid to push the boundaries of feasibility for combinatorial optimization. Two variants of the scheme are described, one of which aims to use machine learning techniques for parallel load balancing. In-depth analysis identifies two inherent sources of parallel search space redundancies that, together with general parallel execution overhead, can impede parallelization and render the problem far from embarrassingly parallel. We conduct extensive empirical evaluation on hundreds of CPUs, the first of its kind, with overall positive results. In a significant number of cases parallel speedup is close to the theoretical maximum and we are able to solve many very complex problem instances orders of magnitude faster than before; yet analysis of certain results also serves to demonstrate the inherent limitations of the approach due to the aforementioned redundancies.

PDF Details DOI

SoCS Conference 2015 Conference Paper

Caching in Context-Minimal OR Spaces

  • Rina Dechter
  • Levi H. S. Lelis
  • Lars Otten

In empirical studies we observed that caching can have very little impact in reducing the search effort in Branch and Bound search over context-minimal OR spaces. For example, in one of the problem domains used in our experiments we reduce only by 1% the number of nodes expanded when using caching in context-minimal OR spaces. By contrast, we reduce by 74% the number of nodes expanded when using caching in context-minimal AND/OR spaces on the same instances. In this work we document this unexpected empirical finding and provide explanations for the phenomenon.

Details

IJCAI Conference 2013 Conference Paper

Predicting the Size of Depth-First Branch and Bound Search Trees

  • Levi H. S. Lelis
  • Lars Otten
  • Rina Dechter

This paper provides algorithms for predicting the size of the Expanded Search Tree (EST) of Depthfirst Branch and Bound algorithms (DFBnB) for optimization tasks. The prediction algorithm is implemented and evaluated in the context of solving combinatorial optimization problems over graphical models such as Bayesian and Markov networks. Our methods extend to DFBnB the approaches provided by Knuth-Chen schemes that were designed and applied for predicting the EST size of backtracking search algorithms. Our empirical results demonstrate good predictions which are superior to competing schemes.

PDF Details DOI

UAI Conference 2012 Conference Paper

A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models

  • Lars Otten
  • Rina Dechter

We study the problem of complexity estimation in the context of parallelizing an advanced Branch and Bound-type algorithm over graphical models. The algorithm’s pruning power makes load balancing, one crucial element of every distributed system, very challenging. We propose using a statistical regression model to identify and tackle disproportionally complex parallel subproblems, the cause of load imbalance, ahead of time. The proposed model is evaluated and analyzed on various levels and shown to yield robust predictions. We then demonstrate its effectiveness for load balancing in practice.

Details

ECAI Conference 2012 Conference Paper

Advances in Distributed Branch and Bound

  • Lars Otten
  • Rina Dechter

We describe a distributed version of an advanced branch and bound algorithm over graphical models. The crucial issue of load balancing is addressed by estimating subproblem complexity through learning, yielding impressive speedups on various hard problems using hundreds of parallel CPUs.

Details

UAI Conference 2012 Conference Paper

Join-graph based cost-shifting schemes

  • Alexander Ihler
  • Natalia Flerova
  • Rina Dechter
  • Lars Otten

We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.

Details

SoCS Conference 2011 Conference Paper

Anytime AND/OR Depth-First Search for Combinatorial Optimization

  • Lars Otten
  • Rina Dechter

One popular and efficient scheme for solving exactly combinatorial optimization problems over graphical models is depth-first Branch and Bound. However, when the algorithm exploits problem decomposition using AND/OR search spaces, its anytime behavior breaks down. This paper 1) analyzes and demonstrates this inherent conflict between effective exploitation of problem decomposition (through AND/OR search spaces) and the anytime behavior of depth-first search (DFS), 2) presents a first scheme to address this issue while maintaining desirable DFS memory properties, 3) analyzes and demonstrates its effectiveness. Our work is applicable to any problem that can be cast as search over an AND/OR search space.

Details

AAAI Conference 2011 Conference Paper

Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models

  • Kalev Kask
  • Andrew Gelfand
  • Lars Otten
  • Rina Dechter

We study iterative randomized greedy algorithms for generating (elimination) orderings with small induced width and state space size - two parameters known to bound the complexity of inference in graphical models. We propose and implement the Iterative Greedy Variable Ordering (IGVO) algorithm, a new variant within this algorithm class. An empirical evaluation using different ranking functions and conditions of randomness, demonstrates that IGVO finds significantly better orderings than standard greedy ordering implementations when evaluated within an anytime framework. Additional order of magnitude improvements are demonstrated on a multicore system, thus further expanding the set of solvable graphical models. The experiments also confirm the superiority of the MinFill heuristic within the iterative scheme.

PDF Details

UAI Conference 2008 Conference Paper

Bounding Search Space Size via (Hyper)tree Decompositions

  • Lars Otten
  • Rina Dechter

This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.

Details

ECAI Conference 2008 Conference Paper

On the Practical Significance of Hypertree vs. TreeWidth

  • Rina Dechter
  • Lars Otten
  • Radu Marinescu 0002

The recently introduced notion of hypertree width has been shown to provide a broader characterization of tractable constraint and probabilistic networks than the tree width. This paper demonstrates empirically that in practice the bounding power of the tree width is still superior to the hypertree width for many benchmark instances of both probabilistic and deterministic networks.

Details
v2026.09.13