Constraint Relaxation Techniques to Aid the
Reuse of Knowledge Bases and Problem Solvers

Tomas Nordlander1, Ken Brown2, and Derek Sleeman1
1Department of Computing Science, University of Aberdeen, Scotland, UK
{tnordlan, sleeman}@csd.abdn.ac.uk
2Cork Constraint Computation Centre, Department of Computer Science,
University College Cork, Ireland
k.brown@cs.ucc.ie

Abstract: Effective re-use of knowledge bases requires the identification
of plausible combinations of both problem solvers and knowledge bases,
which can be an expensive task. Can we identify impossible combinations
quickly? The capabilities of combinations can be represented using
constraints, and we propose using constraint relaxation to help eliminate
impossible combinations. If a relaxed constraint representation of a
combination is inconsistent then we know that the original combination is
inconsistent as well. We examine different relaxation strategies based on
constraint graph properties, and we show that removing constraints of low
tightness is an efficient strategy which is also simple to implement.
1. Introduction
The MUSKRAT (Multistrategy Knowledge Refinement and Acquisition Toolbox)
framework aims to unify problem solving, knowledge acquisition and knowledge-base
refinement in a single computational framework [1]. Given a set of Knowledge Bases
(KBs) and Problem Solvers (PSs), the MUSKRAT-Advisor [2] investigates whether the
available KBs will fulfil the requirements of the selected PS for a given problem. The
Advisor informs the user if the available KBs are sufficient. Our research addresses the
problem of checking whether combinations of existing KBs could be reused with the
selected PS. We propose to represent the KBs and PSs as Constraint Satisfaction Problems
(CSPs), which can be combined to produce composite CSPs. If a combined CSP is
solvable, then the original combination of KBs with the selected PS could be used to solve
the given problem; if the resultant CSP is inconsistent, then the combination cannot be
used. Identifying a suitable combination thus requires examining a series of CSPs, and
rejecting insolvable ones until we find one with a solution. Proving CSPs insolvable can be
a lengthy process; we would like to find a way to do this quickly. The method we propose
here is to relax a CSP, and if we can prove that the relaxed version is insolvable then we
know that the original CSP does not have a solution either. However, if the relaxed CSP
has a solution, then the original CSP represents a plausible combination. To test this
proposal, we investigate different relaxation strategies for binary CSPs and test them on
randomly generated problems. We suggest that removing constraints with low tightness is
an effective method for identifying insolvable combinations. Thus this paper reports a
contribution to the challenging problem of Knowledge Reuse as it presents an aid based on
Constraint Programming to enable a quick identification of inconsistent combinations.
1/13

---

2. Background

This work is supported by the Advanced Knowledge Technologies (AKT)
Interdisciplinary Research Collaboration, which focuses on six challenges to ease
substantial bottlenecks in the engineering and management of knowledge; reuse of
knowledge is one of those challenges [3]. Current work in reuse has resulted in
systems where a number of components have been reused, including ontologies,
problem-solving methods (PSMs), and knowledge bases (KBs) [3]. The use of cases
in Case Based Reasoning is a related activity [4].
2.1 Reusing Knowledge Based Systems
One of the main goals of the Knowledge Based System (KBS) community is to
build new systems out of existing Problem Solvers (say Problem Solving Methods)
and existing Knowledge Bases. At an early stage the Knowledge Engineering sub-
area identified a range of Problem Solving Methods, which they argued covered the
whole range of problem solving and included methods for Classification and
Diagnosis through to Planning (so-called synthesis tasks) [5]. An early but powerful
example of reuse of a PSM was the use of the EMYCIN shell with a variety of
domain-specific knowledge bases [6]. More recently, systems like PROTÉGÉ have
provided an option to write KBs in a standardised format like OKBC [7]. This then
takes the goal of building new Knowledge-Based Systems (KBSs) one step further.
A possible approach is to take the required KB and PSM and to produce manually,
initially, a series of mappings, which will make the 2 components “comparable” [7],
and thus to develop a new KBS from pre-existing components.
We have chosen to work with the domain of scheduling, mainly because the
constraint community has been successful in addressing real world problems in this
area. Also, we argue that the nature of scheduling problems are very close to CSPs,
hence it would be relatively easy to transform PSs and KBs in this domain. We will
now consider an example of a mobile phone manufacturer to understand our notion
of KB and PS reuse. The manufacturer has two factories, three suppliers and two
delivery companies to transport phones to wholesalers around the world (Figure 1).






Supplier
Supplier
Factory
Delivery
Constraints
One of 60 Plausible
France
Mexico
Canada
Europe


Relaxation Rules
Combinations





Supplier
Factory
Delivery
Background
Constraints
China
Germany
America
Knowledge
Relaxation Rules

KBs



Factory
Background
Canada
Knowledge
PSs


Design Selector
Constraint
Supplier

Constraint
Satisfier
China
Satisfier
Present all
Scheduler

Present all
possible
Optimal
Optimal
Optimal
Schedule selected

possible
Delivery
solutions
solution

Price
Quality
Functionality
solutions
America


Figure 1. Combining KBs with selected PS

Along with the domain-specific KBs, the system also consists of background
knowledge (e.g., ISO 9001, Safety Standards), and constraint relaxation rules to
2/13

---

identify those constraints, which the system is allowed to relax (e.g. accept a screen
with a maximum of 64 colours instead of 4096). This toy example has 5 PSs and 7
KBs (for each of the factories, suppliers, and delivery companies) to combine as
well as the obligatory KBs about background knowledge and constraint relaxation
rules (See Figure 1). To solve a task one needs to have: 1 Problem Solvers (out of
5), 1 supplier (out of 3), 1 factory (out of 2), 1 delivery company (out of 2),
background knowledge and constraint relaxation. Since the number of possible
combination is 60 (5*3*2*2*1*1=60), we would like to eliminate some of the
insolvable combinations quickly, leaving a couple of plausible combinations, which
need to be evaluated thoroughly. Let us assume that the manufacturer would like, if
possible, to reuse knowledge to answer questions such as: Can we manufacture,
within the guidelines of ISO 9001 and European safety standards (CE), a mobile
phone with a 4096 colour screen, not heavier then 100g and have it delivered to the
American market within 6 months?

Constraint Relaxation rules

Soft constraints = 4096 colour, CE,…

Hard constraints = ISO 9001, 100 gram, American market, Time,…

Factory Canada:
Background Knowledge:

Product is ISO 9001

Human Resources = 20,…,40 days

If Factory = ISO 9001
Machine Resources = 25,…,45 days


Supplier = ISO 9001

Total Weight ≥ 100 gram

Factory Canada = ISO 9001
Product is CE
…

If Factory = CE


Requirements for the
Supplier China:
Constraint Satisfier:

Colour screen = 4096,512,128,0 colours
ISO 9001 =Yes
Supplier China ≠ ISO 9001
CE = Yes
Colour screen = 4096 colour

Delivery America:
Weight
≤ 100 gram
Delivery market = American

Supplier China - Factory Canada = 30,31,…,45 days
Time ≤ 180 days?
Factory Canada - American market = 20,21,…,30 days


Figure 2. One of 60 Plausible Combinations


Figure 2 illustrates one candidate combination, as well as the requirements for the
selected problem solver. With the knowledge and problem solving requirements in
Figure 2 we can demonstrate that the combination is inconsistent, as one of the
requirements given to the PS, viz., ISO 9001 certified, our background knowledge
states that to make a phone certified, both the manufacture and the part supplier
need to be ISO 9001 certified. Figure 2 shows that only the factory is certified hence
the combination is inconsistent.
White & Sleeman [1] discussed the creation of Meta Problem Solvers, which check
if combinations of KBs with a PS, represented as a CSP, are plausible. However,
this approach was unable to verify if any discarded combination contained a
solution. As noted earlier, we propose to use constraint programming as our PSM
and to represent combination of KBs and PSs as CSPs. We will show that some of
our strategies can not only identify insolvable combinations quickly, but also verify
that their related CSPs do not have any solutions.
3/13

---

2.2 CSP
Constraint Satisfaction techniques attempt to find solutions to constrained
combinatorial decision problems [8, 9] , and there are a number of efficient toolkits
and languages available (e.g. [10, 11]). The definition of a constraint satisfaction
problem (CSP) is:

a set of variables X={ X 1,..., X n},
for each variable Xi, a finite set Di of possible values (its domain), and
a set of constraints C<j> ⊆ Dj1 × Dj2 × …× Djt, restricting the values that
subsets of the variables can take simultaneously.

A solution to a CSP is an assignment of a value from its domain to every variable, in
such a way that all constraints are satisfied. The main CSP solution technique
interleaves consistency enforcement [12], in which infeasible values are removed
from the problem, with various enhancements of backtracking search. The same
approach also serves to identify insolvable problems.
The approach of relaxing CSPs has received considerable attention [13-15], but has
focused on changing the CSP to introduce solutions. Relaxing problems is also a
common technique in mathematical programming, e.g. to obtain better bounds in
optimisation [16]. There has been extensive research on randomly generated CSPs
[13, 17], which show a phase transition between solvable and insolvable problems,
with the hardest problems being at the transition point. Problem classes in these
CSPs can be described by a tuple <n,m,c,t>, where n is the number of variables and
m is the number of values in each domain, c is the number of constraints, and t is the
number of forbidden tuples in each constraint (a measure of problem tightness).
Much of this research concentrates on binary CSPs, in which each constraint is
defined over a pair of variables. Any CSP with finite domains can be modelled by a
CSP with only binary constraints [8, 18].
3. Empirical
Studies
The aim of relaxing CSPs is to produce new CSPs, which are easier to prove
inconsistent. It is not obvious that relaxing an insoluble CSP will produce an easier
problem. In fact, phase transition research (e.g. [19]) seems to indicate the opposite
when the original CSP is inconsistent – as constraints become more loose, or the
connectivity of the problems become more sparse, the time to prove inconsistency
for random problems increases. If our approach is to work, we need to identify
suitable relaxation strategies, which avoid the increase in solution time. In this
section, we describe a series of experiments designed to test whether our approach is
practical and to identify suitable relaxation strategies. For this paper, we limit the
experiments to randomly generated binary CSPs, with a view to extending the
results to real world problems. First we will describe the software, and then present
the experiments. For the experiments, we generate a set of random problems, prove
them inconsistent by search, and then apply various relaxation strategies and
measure the reduction in search effort. The experiments are divided into three
groups according to the distribution of the random problems.
4/13

---

3.1 CSP-Suite

The CSP-Suite [20] used in these experiments is written in SICStus Prolog [11] and
consists of Generating, Relaxing, and Solving modules (Figure 3).





Generating
Relaxing
Solving
Results






CSPs
Relaxed CSPs


Figure 3. The CSP-Suite

The Generating module creates random binary CSPs. Our random CSPs are slightly
different from most reported in the literature. We want to find local properties of a
problem which indicate how to relax it, so rather than have every constraint in a
problem with the same tightness, we instead allow the tightness to vary. This also
produces random CSPs which are closer to real world problems. The tightness of
individual constraints in our problems will be uniformly, normally, or exponentially
distributed. Thus, for different tightness distributions we use different ways to
describe the tightness tuple. The uniform problem classes have 5-tuples
<n,m,c,[tµ,r]>, where tµ is the average number of forbidden tuples, with the number
for each constraint selected uniformly at random from the range [tµ-r, tµ+r]. The
normal problem classes introduce standard deviation (sd) in our tightness tuple;
<n,m,c,[tµ,sd,r]>. The standard deviation parameter controls the width of the bell
curve. The exponential distribution requires a somewhat different notation:
<n,m,c,[tm,stp,r]>, where tm (tightness middle) shows the middle of the distribution
range, which is not the same as average distribution. The parameter stp has an effect
on the steepness of the exponential probability curve. Even though only a positive
exponential distribution has been tested in this paper (many low tightness
constraints that decay exponentially to few high tightness constraints), it is also
possible to generate a negative exponential tightness distribution. First we create a
skeleton graph by successively adding nodes, then we randomly add constraints
until we reach “c”, then take each constraint in turn, decide how many tuples it
should forbid, and then randomly remove that number of tuples.
The Relaxing module generates relaxed CSPs from original CSPs by removing a
specified number of constraints according to nine different strategies. Random
Removal simply chooses the constraints randomly. Greedy Search considers each
constraint in turn, removing it, solving the relaxed CSP, and replacing the constraint. It
then selects the constraint whose removal gave the best performance improvement,
removes it, and repeats the whole process on the resulting CSP. Greedy Ordering uses
5/13

---

the first iteration of Greedy Search to generate an ordering list for all constraints
then removes constraints in the order suggested. Node Degree selects constraints
in ascending or descending order of the degree of their associated variables in the
constraint graph. Isolate Node selects high or low degree nodes and removes a
series of constraints incident on those nodes (i.e. it tries to remove variables from
the problem). Tightness removes constraints in ascending or descending order of
their tightness. Note that the two Greedy strategies would not be applicable in our
eventual framework, since they must solve many CSPs each time. They are useful
here as reference points showing what might be achievable. We also used the
results of the Greedy search to analyse the properties of the most profitable
removed constraints, and from that developed some of the other strategies.
The Solving module simply solves the CSPs using the finite domain library [21],
and records search effort each time. Since the library does not report constraint
checks, we use the resumption statistic instead. We have confirmed that
resumptions correlate well with CPU time [22].
3.2 CSPs with Uniformly Distributed Tightness
First, we consider problems with a uniform distribution of tightness. In Figure 4, for
the problem class <20,10,133, [65, 15]>, we show the resumption profit achieved
(i.e. how much easier it is to solve the relaxed CSP compared to the original) by
each strategy, removing up to 60 constraints each time. The problem class is in the
over-constrained region, and in all cases we considered, remained over-constrained
even after removing the constraints. The graph shows that removing low-tightness
constraints is the most profitable of the applicable strategies, for this problem class.
We assume that although such constraints are easy to satisfy, they are likely to be
redundant when showing there is no solution, since they rule out so few
combinations, and thus they introduce many extra branches into the search tree for
no benefit.









Figure 4. Relaxation Strategies when removing up to 60 constraints
6/13

---

We then concentrate on the Low Tightness strategy, and Figure 5 illustrates its
effect on 4 different problem classes. Whilst the graph shows a negative result
for the <20,10,133,[45,15]> curve, the others are positive. In the best case we
can create relaxed CSPs that are up to 45% easier to solve than the original
CSPs, still without introducing a solution. The graphs suggest that the Low
Tightness Removal strategy works better on CSPs with high tightness and wide
distribution.











Figure 5. Low Tightness Removal Strategy when removing 60 constraints


As discussed at the start of section 3, strategy (1), randomly removing
constraints from a randomly generated inconsistent CSP, is likely to make it
harder to prove inconsistency. Does the same effect happen for Low Tightness
Removal? I.e., is there a point at which removing constraints is no longer
profitable? In Figure 6 we plot the search effort against the number of
constraints in problems obtained by relaxing an original problem using Low
Tightness Removal, and we include Random Removal for comparison. We start
with a particular problem class on the right-hand side of the curve, remove
constraints according to each strategy, and solve the new problem after each
removal. In three cases, we avoid any significant hardness peak with the Low
Tightness strategy, and for the fourth a peak appears only after removing
approximately 40 constraints. That peak is further to the left than for Random
Removal, and the peak normally coincides with the solubility transition. Figure 7
shows the transition curves, and we can see that in four cases, the transition
point for Low Tightness Removal appears later (further left) than for Random
Removal. This gives us some confidence that we can use our relaxation strategy
reliably without introducing new solutions.
7/13

---

Figure 6. Search effort for Random Removal vs. Low Tightness Removal












Figure 7. Transition phase for Random Removal vs. Low Tightness Removal


3.3 CSPs with Normally and Exponentially Distributed Tightness
We now repeat the experiments on problems with normally distributed tightness
(Figures 8 to 11) and with exponentially distributed tightness (Figures 12 to 15).
Although the graphs suggest that the results of the low tightness strategy are
slightly better for CSPs with a uniformly distributed tightness that have a high
average and a wide distribution range, it is evident from figures 8 &12 that low
tightness is still the best strategy for all distributions.
There are only two differences in the results for these distributions when
compared to Uniform. Firstly, as seen in figure 10, there are only two cases
instead of three where we can avoid any significant hardness peak when relaxing
using the Low Tightness strategy. Secondly, when we compare the Random
curves (Figure 10 & 14) we notice that the hardness peak is not only a bit wider
but also slightly higher than the uniform distribution graphs in section 3.2. Still,
8/13

---

for all cases, the transition point for low tightness is later than for random (see
Figures 11 & 15), which leaves us with some confidence that we can use our
relaxation strategy reliably without introducing new solutions even when the
tightness is exponentially distributed.
Note that the reason that we use a different standard deviation (sd) for problem
classes with a different range is to obtain an equal bell-shaped distribution form
for all our problem classes (Figure 9-11). Additionally, in order to achieve a
similar exponential decay for the problem classes with different range values we
use a different steepness (stp) (Figure 13-15).












Figure 8. Relaxation Strategies when removing up to 60 constraints













Figure 9. Low Tightness Removal Strategy when removing 60 constraints


9/13

---

Figure 10. Search effort for Random Removal vs. Low Tightness Removal
Figure 11. Transition phase for Random Removal vs. Low Tightness Removal
Figure 12. Relaxation Strategies when removing up to 60 constraints
Figure 13. Low Tightness Removal Strategy when removing 60 constraints
10/13

---

Document Outline

• Introduction
• Background
  • Reusing Knowledge Based Systems
  • CSP
• Empirical Studies
  • CSP-Suite
  • CSPs with Uniformly Distributed Tightness
  • CSPs with Normally and Exponentially Distributed Tightness
• Future Work
• Summary
• Acknowledgements
• References

---