Alan M. Frisch

IJCAI Conference 2023 Conference Paper

Conjure: Automatic Generation of Constraint Models from Problem Specifications (Extended Abstract)

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest given the expertise and time required to develop an effective model of a particular problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a diverse space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. We show how modelling symmetries may be broken automatically as they enter a model during refinement, removing the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

AIJ Journal 2022 Journal Article

Conjure: Automatic Generation of Constraint Models from Problem Specifications

• Özgür Akgün
• Alan M. Frisch
• Ian P. Gent
• Christopher Jefferson
• Ian Miguel
• Peter Nightingale

When solving a combinatorial problem, the formulation or model of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest because of the expertise and time required to produce an effective model of a given problem. We describe a method to automatically produce constraint models from a problem specification written in the abstract constraint specification language Essence. Our approach is to incrementally refine the specification into a concrete model by applying a chosen refinement rule at each step. Any non-trivial specification may be refined in multiple ways, creating a space of models to choose from. The handling of symmetries is a particularly important aspect of automated modelling. Many combinatorial optimisation problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: modelling symmetries. We show how modelling symmetries may be broken automatically as they enter a model during refinement, obviating the need for an expensive symmetry detection step following model formulation. Our approach is implemented in a system called Conjure. We compare the models produced by Conjure to constraint models from the literature that are known to be effective. Our empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of 42 benchmark problems found in the literature.

AIJ Journal 2009 Journal Article

Filtering algorithms for the multiset ordering constraint

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.

IJCAI Conference 2007 Conference Paper

• Alan M. Frisch
• Matthew Grum
• Chris Jefferson
• Bernadette Mart
• iacute; nez Hern
• aacute; ndez
• Ian Miguel

ESSENCE is a new formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. ESSENCE provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. ESSENCE also allows these combinatorial objects to be nested to arbitrary depth, thus providing, for example, sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be directly specified by using a decision variable whose type is precisely that combinatorial object.

AIJ Journal 2006 Journal Article

Propagation algorithms for lexicographic ordering constraints

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O ( n ) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.

IJCAI Conference 2005 Conference Paper

The Rules of Constraint Modelling

• Alan M. Frisch
• Chris Jefferson
• Bernadette Martínez-Hernández
• Ian

Many and diverse combinatorial problems have been solved successfully using finite-domain constraint programming. However, to apply constraint programming to a particular domain, the problem must first be modelled as a constraint satisfaction or optimisation problem. Since constraints provide a rich language, typically many alternative models exist. Formulating a good model therefore requires a great deal of expertise. This paper describes CONJURE, a system that refines a specification of a problem in the abstract constraint specification language ESSENCE into a set of alternative constraint models. Refinement is compositional: alternative constraint models are generated by composing refinements of the components of the specification. Experimental results demonstrate that CONJURE is able to generate a variety of models for practical problems from their ESSENCE specifications.

ECAI Conference 2004 Conference Paper

Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern

• Alan M. Frisch
• Christopher Jefferson
• Ian Miguel

SAT Conference 2003 Conference Paper

The Interaction Between Inference and Branching Heuristics

• Lyndon Drake
• Alan M. Frisch

Abstract We present a preprocessing algorithm for SAT, based on the HypBinRes inference rule, and show that it does not improve the performance of a DPLL-based SAT solver with conflict recording. We also present evidence that the ineffectiveness of the preprocessing algorithm is the result of interaction with the branching heuristic used by the solver.

AIJ Journal 1994 Journal Article

Anytime deduction for probabilistic logic

• Alan M. Frisch
• Peter Haddawy

This paper proposes and investigates an approach to deduction in probabilistic logic, using as its medium a language that generalizes the propositional version of Nilsson's probabilistic logic by incorporating conditional probabilities. Unlike many other approaches to deduction in probabilistic logic, this approach is based on inference rules and therefore can produce proofs to explain how conclusions are drawn. We show how these rules can be incorporated into an anytime deduction procedure that proceeds by computing increasingly narrow probability intervals that contain the tightest entailed probability interval. Since the procedure can be stopped at any time to yield partial information concerning the probability range of any entailed sentence, one can make a tradeoff between precision and computation time. The deduction method presented here contrasts with other methods whose ability to perform logical reasoning is either limited or requires finding all truth assignments consistent with the given sentences.

AIJ Journal 1991 Journal Article

The substitutional framework for sorted deduction: Fundamental results on hybrid reasoning

• Alan M. Frisch

Researchers in artificial intelligence have recently been taking great interest in hybrid representations, among them sorted logics—logics that link a traditional logical representation to a taxonomic (or sort) representation such as those prevalent in semantic networks. This paper introduces a general framework—the substitutional framework—for integrating logical deduction and sortal deduction to form a deductive system for sorted logic. This paper also presents results that provide the theoretical under-pinnings of the framework. A distinguishing characteristic of a deductive system that is structured according to the substitutional framework is that the sort subsystem is invoked only when the logic subsystem performs unification, and thus sort information is used only in determining what substitutions to make for variables. Unlike every other known approach to sorted deduction, the substitutional framework provides for a systematic transformation of unsorted deductive systems into sorted ones.

AAAI Conference 1990 Conference Paper

Generalization with Taxonomic Information

• Alan M. Frisch

This paper studies sorted generalization-the generalization, with respect to an arbitrary taxonomic theory, of atomic formulas containing sorted variables. It develops an algorithm for the task, discusses the algorithm and task complexity, and presents semantic properties of sorted generalization. Based on its semantic properties, we show how sorted generalization is applicable to such problems as abduction, induction, knowledge base vivification, and analogical reasoning. Significant distinctions between this work and related work with taxonomic information arise from the generality of the taxonomic theories we allow, which may be any first-order taxonomic theories, and the semantic completeness properties of sorted generalization.

UAI Conference 1988 Conference Paper

Modal logics of higher-order probability

• Peter Haddawy
• Alan M. Frisch

IJCAI Conference 1987 Conference Paper

Inference without Chaining

• Alan M. Frisch

IJCAI Conference 1985 Conference Paper

Using Model Theory to Specify Al Programs

• Alan M. Frisch