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.

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.

In constraint solving, a critical bottleneck is the formulation of aneffective constraint model of an input problem. The Conjure system describedin this paper, a substantial step forward over prototype versions of Conjurepreviously reported, makes a valuable contribution to the automation ofconstraint modelling by automatically producing constraint models from theirspecifications in the abstract constraint specification language Essence. Aset of rules is used to refine an abstract specification into a concreteconstraint model. We demonstrate that this set of rules is readily extensibleto increase the space of possible constraint models Conjure can produce. Ourempirical results confirm that Conjure can reproduce successfully the kernelsof the constraint models of 32 benchmark problems found in the literature.

The primary goal of this paper is to illustrate how smaller deductive search spaces can be obtained by extending a logical language with restricted quantification and tailoring an inference system to this extension. The illustration examines the search spaces for a bottom‐up parse of a sentence with a series of four strongly equivalent grammars. The grammars are stated in logical languages of increasing expressiveness, each restatement resulting in a more concise grammar and a smaller search space. A secondary goal is to point out an area where further research could yield results useful to the design of efficient parsers, particularly for grammatical formalisms that rely heavily on feature systems.

Ever since Wood's "What's in a Link" paper, there has been a growing concern for formalization in the study of knowledge representation. Several arguments have been made that frame representation languages and semantic-network languages are syntactic variants of the first-order predicate calculus (FOPC). The typical argument proceeds by showing how any given frame or network representation can be mapped to a logically isomorphic FOPC representation. For the past two years we have been studying the formalization of knowledge retrievers as well as the representation languages that they operate on. This paper presents a representation language in the notation of FOPC whose form facilitates the design of a semantic-network-like retriever.