Ulrich Junker

KER Journal 2012 Journal Article

Air traffic flow management with heuristic repair

• Ulrich Junker

Abstract The European air traffic flow management problem poses particular challenges on optimization technology as it requires detailed modelling and rapid online optimization capabilities. Constraint programming proved successful in addressing these challenges for departure time slot allocation by offering fine-grained modelling of resource constraints and fast allocation through heuristic-repair strategies.

IS Journal 2007 Journal Article

Configuration

• Carsten Sinz
• Albert Haag
• Nina Narodytska
• Toby Walsh
• Esther Gelle
• Mihaela Sabin
• Ulrich Junker
• Barry O'Sullivan

Over the years, a whole sector of AI dealing with configuration problems has emerged, and since 1996, an annual configuration workshop has been held in affiliation with a major AI conference. This installment of Trends & Controversies presents essays from the configuration workshop held in August 2006 as part of ECAI in Riva del Garda, Italy.

ECAI Conference 2006 Conference Paper

Preference-Based Inconsistency Proving: When the Failure of the Best Is Sufficient

• Ulrich Junker

Inconsistency proving of CSPs is typically achieved by a combination of systematic search and arc consistency, which can both be characterized as resolution. However, it is well-known that there are cases where resolution produces exponential contradiction proofs, although proofs of polynomial size exist. For this reason, we will use optimization methods to reduce the proof size globally by 1. decomposing the original unsatisfiability problem into a conjunction of satisfiable subproblems and by 2. finding an ordering that separates the solution spaces of the subproblems. This principle allows Operation Research methods to prove the inconsistency of overconstrained linear programs even if domains are infinite. We exploit the principle for testing the satisfiability of global user requirements in product configuration problems.

ECAI Conference 2006 Conference Paper

Return of the JTMS: Preferences Orchestrate Conflict Learning and Solution Synthesis

• Ulrich Junker
• Olivier Lhomme

We use a lexicographical preference order on the problem space to combine solution synthesis with conflict learning. Given two preferred solutions of two subproblems, we can either combine them to a solution of the whole problem or learn a ‘fat’ conflict which cuts off a whole subtree. The approach makes conflict learning more pervasive for Constraint Programming as it well exploits efficient support finding and compact representations of Craig interpolants.

AAAI Conference 2004 Conference Paper

QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems

• Ulrich Junker

Over-constrained problems can have an exponential number of conflicts, which explain the failure, and an exponential number of relaxations, which restore the consistency. A user of an interactive application, however, desires explanations and relaxations containing the most important constraints. To address this need, we define preferred explanations and relaxations based on user preferences between constraints and we compute them by a generic method which works for arbitrary CP, SAT, or DL solvers. We significantly accelerate the basic method by a divide-and-conquer strategy and thus provide the technological basis for the explanation facility of a principal industrial constraint programming tool, which is, for example, used in numerous configuration applications.

IJCAI Conference 2003 Conference Paper

Propagate the Right Thing: How Preferences Can Speed-Up Constraint Solving

• Christian Bessiere
• Anai's Fabre
• Ulrich Junker

We present an algorithm Pref-AC that limits arc consistency (AC) to the preferred choices of a tree search procedure and that makes constraint solving more efficient without changing the pruning and shape of the search tree. Arc consistency thus becomes more scalable and usable for many realworld constraint satisfaction problems such as configuration and scheduling. Moreover, Pref-AC directly computes a preferred solution for tree-like constraint satisfaction problems.

AAAI Conference 2002 Conference Paper

Preference-Based Search and Multi-Criteria Optimization

• Ulrich Junker

Many real-world AI problems (e. g. in configuration) are weakly constrained, thus requiring a mechanism for characterizing and finding the preferred solutions. Preferencebased search (PBS) exploits preferences between decisions to focus search to preferred solutions, but does not efficiently treat preferences on defined criteria such as the total price or quality of a configuration. We generalize PBS to compute balanced, extreme, and Pareto-optimal solutions for general CSP’s, thus handling preferences on and between multiple criteria. A master-PBS selects criteria based on trade-offs and preferences and passes them as optimization objective to a sub-PBS that performs a constraint-based Branch-and-Bound search. We project the preferences of the selected criterion to the search decisions to provide a search heuristics and to reduce search effort, thus giving the criterion a high impact on the search. The resulting method will particularly be effective for CSP’s with large domains that arise if configuration catalogs are large.

AAAI Conference 2000 Conference Paper

Preference-Based Search for Scheduling

• Ulrich Junker

Preference-based search (PBS) is a new search procedure for solving combinatorial optimization problems. Given a set of preferences between search decisions, PBS searches through a space of preferred solutions, which is tighter than the space of all solutions. The definition of preferred solutions is based on work in non-monotonic reasoning (Brewka 1989; Geffner & Pearl 1992; Grosof 1991) on priorities between defaults. The basic idea of PBS is quite simple: Always pick a locally best decision α. Either make the decision α or make other locally best decisions that allow to deduce ¬α and thus represent a counterargument for α. If there is no possible counterargument then PBS does not explore the subtree of ¬α. This pruning of the search space is obtained by nonmonotonic inference rules that are inspired by Doyle’s TMS and that detect decisions belonging to all or no preferred solution. We show that PBS can optimally solve various important scheduling problems.

IJCAI Conference 1997 Conference Paper

A Cumulative-Model Semantics for Dynamic Preferences on Assumptions

• Ulrich Junker

Explicit preferences on assumptions as used in prioritized circumscription [McCarthy, 1986; Lifschitz, 1985; Grosof, 1991] and preferred subtheories [Brewka, 1989] provide a clear and declarative method for defining preferred models. In this paper, we show how to embed preferences in the logical theory itself. This gives a high freedom for expressing statements about preferences. Preferences can now depend on other assumptions and are thus dynamic. We elaborate a preferential semantics based on Lehmann's cumulative models, as well as a corresponding constructive characterization, which specifies how to correctly treat dynamic preferences in the default reasoning system EX- CEPT [Junker, 1992].

AAAI Conference 1990 Conference Paper

Computing the Extensions of Autoepistemic and Default Logics with a Truth Maintenance System

• Ulrich Junker

IJCAI Conference 1989 Conference Paper

A Correct Non-Monotonic ATMS

• Ulrich Junker