Solving Various Weighted Matching Problems with Constraints.
This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint ( WeightedMatching), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CP is shown not to be competitive with specialized polynomial algorithms for pure matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the Traveling Salesman Problems [5], which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a  WeightedMatching constraint. This is an extension to the weighted case of the work of Rgin [19], which we show to bring significant improvements on a timetabling example.
Introduction
Constraint Logic Programming (CLP) and more generally Constraint-based
Programming (CP), has become an interesting approach for solving combinatorial
optimization problems [VH 89]. For instance, on problems such as jobshop
scheduling it has shown to be as efficient as more traditional approaches based on
Operations Research (OR) [CL 94] while delivering more flexibility (i.e. it is easy to
adapt the algorithm to a slightly customized problem with additional constraints). Our
goal is to investigate the advantages and drawbacks of constraint programming
compared to classical combinatorial optimization on the maximum weight matching
problem in a bipartite graph and see how these techniques may be combined.
Bipartite matching is interesting and important for three reasons. First, it is a well-understood
problem, for which many polynomial algorithms ranging from simple to
really elaborate (e.g., [GT 89]) are available. Therefore, the performance of the
constraint satisfaction algorithm can be assessed against a rigorous gauge. Second,
many real-life problems are either matching or "extended" matching with one or a few
additional constraints. It is, therefore, a perfect domain to see where the boundary
between flexibility and efficiency should lay. Moreover, many such matching
problems are optimization problems with weights, and it may be more indicated to
use weighted matching algorithms than to use generic optimization methods with non-weighted
techniques. Third, matching is often a part of more complex problems and
the efficient propagation of matching constraints is a basic building block of a modern
constraint satisfaction system. By looking carefully into matching algorithms, we
derive ideas that will be of use to designers of constraint solvers.
The paper is organized as follows. Section 2 describes a "naive" approach to
matching and a few improvements that can be implemented easily. We then move on
to more complex heuristics and cutting rules and show how they can be used to
handle larger problems. Section 3 compares the previous results with two well-known
algorithms, the Hungarian (weighted) method and the Busaker & Gowen flow
algorithm. We show that the constraint satisfaction approach does not really compare
with these specialized algorithms when the problem is to find an optimal matching.
On the other hand, it is a plausible approach for finding a set of "very good" solutions.
This leads to Section 4, where we look at two extended matching problems: in the
first case, we allow the substitution of a new cost matrix for a few (k) edges
(machine-task allocation problem with renewal of k machines); in the second case, we
study the resolution of two simultaneous matching problem (e.g., in a machine-task
allocation problem, maximize production within a bounded energy consumption). For
these two variations of the problem, the original algorithms are adapted and
compared. Last, we apply in Section 5 the various techniques that were presented in
this paper to a time-tabling problem. We show that we can use weighted matching as
a global constraint, which captures hard and soft constraints at the same time,
enabling a more efficient resolution.
2. Constraint based programming
Formally, the matching problem can be described as follows : Let G=(V,E) be a
bipartite graph, the vertex set V can be parted in two shores such that all
edges link V 1 to V 2 . A matching is a set of edges M - E such that no two of them are
adjacent. A perfect matching is a matching covering all vertices. We consider the case
which a perfect matching corresponds to an assignment
(such matchings frequently arise in production planning, for the
assignment of jobs to machines or tasks to technicians). Moreover, we consider the
case of a weighted graph and define the weight of a matching as the sum of the
weights of its edges. The purpose is then to find, when it exists, a perfect matching of
maximal weight (or of minimal weight if all weight w ij are replaced by A- w ij ), for
some large constant A).
2.1. Naive CLP
A natural way to see this problem as a constraint program is to think of the vertices
in V 1 as variables and to those in V 2 as values. A vertex in V 1 is linked to the set of
values in V 2 which form its domain. A matching corresponds to an assignment for the
variables such that different variables are always assigned different values. The
problem consists in finding an assignment of maximal weight. This constraint
(AllDifferent) [R-94] is offered as a built-in in most CLP languages. Propagation is
often performed by arc-consistency [Ma77], [MM 88]. when a value is assigned to a
variable, it is taken out of the domains of the other variables. When a contradiction
occurs (because a domain becomes empty), the system backtracks to the previous
variable assigned and tries the next possible assignment. For optimization, the
algorithm is a classical branch and bound scheme : a variable is selected and all
possible values are recursively tried. Once a solution M of weight W has been found,
the constraint weight > W is added to the system to help pruning subtrees of the search
space using simple upper bounds for weight.
At any time during the search, two upper approximations of the maximal matching
are maintained : the sum s + for all variables of their best possible assignment (for
each variable v, we define the value best(v) as the maximal value weight(v,x) for all
possible values x) and reciprocally the sum s - for all values of their best possible
inverted assignment.
Instead of computing these sums explicitly for each node in the search tree, they are
maintained incrementally. Each time a value x is removed from the domain of a
variablev, if weight(x,v)=best(x) then best(x) is re-computed and the difference
between the old and the new value is subtracted from s + . Similar updates are
performed on best(v) and s - if weight(x,v)=best(v). Whenever one of the bounds s
or s - becomes strictly smaller than the goal, one can predict that the upcoming
solutions will have a smaller weight than the best one found so far, so this branch of
the tree can be cut off.
This propagation algorithm is widespread among the implementations of the
alldifferent constraint. In a CLP system, the selection of the node on which to branch
is usually done with the first-fail principle : one selects a variable with the smallest
domain. Assignments are usually tried in decreasing order of weight to drive the
search towards matchings with heavy weights (best first principle, greedy heuristic).
As shown in table 1, this naive algorithm solves problems up to 2x20 nodes within
seconds but requires unreasonable amounts of time for larger problems. Although it
may not be the case for all implementations of the alldifferent constraint, taking both
upper bounds is important. The program which just considers s + as
upper bound is 10 times slower on 10x10 instances and cannot solve 20x20 problems
within reasonable times. This fact gives us a hint of the progress that a symmetrical
view of the problem can bring to a constraint approach.
The next two sections (2.2 and 2.3) describe improvements that can be made to the
propagation scheme and the heuristics (first fail, best first) in order to improve
performance. 1 All the experiments reported in this paper have been done with the
CLAIRE programming language 2 .
1 For programmers using a blackbox constraint system with no access to the propagation and
search engine (as many CLP systems), these changes could only be encoded within the solver:
this allows to state the problem with the single command alldifferent, but the changes can only
be written by an expert of the constraint system. For programmers using an open constraint
system with access to the solver and the propagation engine, the program is a little longer but
any user can program these changes.
2 available at http://www.dmi.ens.fr/~laburthe/claire.html
2.2. Adding symmetry and regret
Many improvements can be made on this algorithm to make it scale up for larger
problems. The first idea suggested by the importance of the symmetrical upper
bounds is to have a fully symmetrical description of the problem. The model that
considers vertices of V 1 as variables and vertices of V 2 as values is an arbitrary
breech to the symmetry of the problem (although perfectly valid). A way around this
is to add the redundant model where V 2 is seen as the set of variables and V 1 as the
set of values. Branching both on vertices from V 1 and V 2 implies some overhead (an
inverse of the domain relation must be maintained), but it avoids missing evident
decisions (for instance, when a value is in only one domain, it needs to be assigned to
that variable). Hence, the matching is done from both sides at the same time. This is
very similar to the use of symmetric redundant models for the n-queens problem [Jo
95], as would be expected since the n-queens is a customized matching problem
(without weights).
Moreover, the first-fail heuristic for the selection of the vertex on which to branch
is not a panacea : The notion of regret gives a more acute description of the crucial
vertices. The regret is usually defined as the difference between the optimal choice
and the second best. In our case, if v is a vertex from V 1 and x is a value such that
best(v)=weight(v,x), we define regret(x) as the difference between best(v) and the
maximum of weight(v,x') for all values x'-x. Focusing on regret is justified by the fact
that problem solutions do not change if a constant is added to all edges incident to one
vertex (thus, only relative values matter, as opposed to absolute ones).
The regret is actually the change that will be made to the upper bound if the best
assignment for this vertex is discarded. Selecting the vertex with the largest
regret as a branching point is an entropic choice in the sense that we try to maximize
the impact of this decision. As described in [CL 94], entropic heuristics are a powerful
tool for proofs of optimality since they limit the size of the tree by forcing much
propagation to happen at each node. To avoid a real slow down of the algorithm at
each node, the regret and the best assignment for each node are memorized and
updated incrementally.
Another idea would be to somehow re-break the symmetry. At any time, two upper
bounds for the matching, s are available. As soon as one of them becomes
less than the goal, the branch can be cut. Selecting vertices in V 1 with large regret
decreases conversely. In cases when one of the bounds is
clearly better than the other, it could seem worthwhile to encourage this dissymmetry
in the choice of the branching node. We implemented this by giving a bonus (or
penalty, depending of the situation) during the selection of the branching vertex,
proportional to s to the vertices in V 1 . This heuristic is denoted as "balance" in
table 1.
The table below illustrates the effect of these techniques on randomly generated
instances for 2- 20 and 2 - each vertex being typically connected to 5 to 8
edges, with weight a random number between 1 and 100. The entries of the table
show the number of backtracks (b.) in the search process (1kb.=1000b.) and the
running times (on a Pentium Pro 200) for finding an optimal solution and giving the
proof of optimality. The naive approach (arc consistency and first fail) behaves
poorly, the addition of regret and symmetry brings a gain of a factor 10. The idea of
the balance does not really pay off.
Naive Propagation
1.2 s.
52 kb.
500 s.
5 kb.
9 kb.
198 kb.
b.
800 b.
3,5 kb.
800 b.
1.2 s.
9.5 s.
2,7 Mb.
Basic
900 b.
3,5 kb.
900 b.
43 kb.
2.5 s.
1,1 Mb.

Table

programs
2.3 Finer tuning of the algorithm
One of the aspects of the algorithm that can be sharpened is propagation. In
addition to upper bound evaluation and domain reduction due to edge selection, we
can also do some domain reduction because of the upper bound. As a matter of fact,
we can dynamically remove all illegal edges. An edge uv is illegal as soon as (best(u)
- weight(u,v)) is greater than the available slack (goal - s
goal is the objective weight (goal is subsequently decreased to
time an admissible solution M is found). We call this technique
dynamic cut and report its behavior in table 2. The interest of dynamic cut is two-
folds. On the one hand we detect some failures a little earlier (a rather small benefit).
On the other hand, we maintain smaller and more relevant domains, which may
improve the efficiency of the first-fail principle. Removing meaningless values
produces more rapidly the domains with very small cardinals (1 to 3) that first-fail
tells us to examine. If we want to re-introduce some of the first-fail behavior into our
choice heuristic based on regret, we can use a simple trick (used in [CGL93]): select
the vertex that will minimize the lexicographic pair
where par is a fixed parameter. The effect is to select vertices by largest regret
while there are still domains with cardinal more than par and to select them by first
fail when all domains are smaller than par. This strategy yields some improvements,
but only for small values of par (3).
The search tree, as described now has many branches per node. Actually, it may be
a waste of time to wonder what edge should be selected for a vertex, once we know
that it will not be the best one, since these edges may well look alike and be
numerous. The search tree can be constructed differently with a single alternative at
each node : either the best edge is the selected one, or it is not. The tree becomes
narrower (binary), maybe deeper, but in practice, it prevents the algorithm from
wasting time in irrelevant choices. This new branching scheme is reported in table 2
as binary branching.
The other tuning that can be done concerns the upper bound that is used for cutting
branches of the search tree. Our formula that sums all best choices
estimation of the best assignment. Indeed, if v -V 1 is the favorite choice of p vertices
in V 2 , we know that we will have to take into account the regret for atleast p-1 of
them (because they cannot all be matched to their common favorite vertex).
Therefore, it is possible to tighten the bound by subtracting from s + a conservative
estimate of the regrets that will occur (this is an application of the lookahead principle
because we try to forecast the evolution of the bounds). For each vertex v -V 1 , we
consider the previous set of vertices x from V 2 such that best(x). To this
set of p vertices, we associate the sum of all regrets but the highest one, that we call
look(v). s + . can be replaced by
This strategy which estimates the difference between the simple bound and the
actual choice is called lookahead in table 2. Note that the estimation s corresponds
to a relaxation of the matching problem. This could suggest to use Lagrangean
relaxation by affecting weights to nodes. In fact, this lookahead strategy uses similar
ideas by affecting weights to nodes that are related to several others ones in the
preference graph (these nodes which prevent the solution of the relaxed problem to be
a matching). Moreover, the Hungarian method which associates weights to nodes can
also be seen as related to Lagrangean relaxation.
basic
1.2 s.
9.5 s.
2,7 Mb.
dynamic cuts 24 kb.
1,5 Mb.
2.2 Mb.
new branching
1.2 s.
95 kb.
6.5 s.
lookahead 4,5 kb.
1.2 s.
6 s.

Table

A few remarks can be made from these results. First, the lookahead heuristic works
well, although its benefits (obvious from the numbers of backtracks) only pay off
when the size of the problem is large enough. On the other hand, both the dynamic cut
and binary branching schemes produce unstable results and it is difficult to measure
any significant improvement.
These techniques (propagation, branching, bouding, heuristics) have been
succesfully applied to the Traveling Salesman Problem (TSP) which can be
represented as a weighted matching problems (trying to match each node with its
direct successor in the cycle) coupled with a subtour elimination constraint. As
described in [CL97], these improvements enable constraint programs to solve 30-city
tours instead of 15-city tours (more complex techniques are also given for larger
problems).
3. Traditional algorithmic approaches
Matchings have been widely studied by the Operations Research community for
years ([CoL 86], [Ge 94]). The two methods presented here do not pretend to be the
best ones available today. We made a compromise by limiting ourselves to algorithms
which were simple enough to be understood and implemented in a reasonable amount
of time, not out of proportion with the implementation times of constraint-based
programs
. The algorithm of Busaker and Gowen (described in [GM 79], [VL 90])
embeds the matching problem into a flow problem by adding a source linked to all
vertices in V 1 and a sink linked to all vertices in V 2 . In this case, the capacities on all
edges are set to 1. It is an adaptation of the well-known Ford&Fulkerson maximum
flow algorithm to the case of a network with weighted edges. It starts with a null flow
and augments it by saturating it along augmenting paths until no augmenting path can
be found, meaning that the flow is maximal. This polynomial algorithm runs in
is the number of edges and N the number of nodes. However,
unlike the Ford&Fulkerson it is not incremental in the sense that it cannot complete
any partial flow into a minimal cost maximal flow (it requires the partial flow to be of
maximal stream for its cost).
. The Hungarian method is an algorithm of the class of primal-dual algorithms
often associated to problems stated as linear programs [PS 82]. The primal program
consists in finding a maximal matching of minimal weight. The dual program consists
in finding positive weights p u associated to vertices u such that for all edges uv,
and such that the sum of the p u is maximal. The algorithm
constructs incrementally the weights p u , starting with all p u equal to 0, and
constructing the graph G p formed by the edges uv verifying p u . The
algorithm alternatively works in the dual model (updating the p u in order to add new
edges to the graph G p ) and the primal model (finding augmenting paths in G p ). In
the end, the matching in G p is a minimal weight maximal matching in G. This
polynomial algorithm runs in O(N 3 ). Its major interest compared to the flow algorithm
is its incrementality. When one wants to remove an edge uv from the graph and
recompute the optimal solution, one just sets weight uv to a large positive constant and
remove uv from G p . It takes then only one iteration to complete the optimal
matching.
3.1. Comparison with CLP
For finding an optimal solution to a pure matching program, CP is not competitive
with these OR techniques. CP solves reasonably well problems with up to 2 - 40 or
nodes, whereas the Hungarian method scales up to problems well over 2 - 100
nodes (on our examples, solved in 70 or 80 000 backtracks and approximately
200 s. by our best constraint programs, the flow algorithm takes 1 s. and the
Hungarian method takes 0,3 s. However, if one no longer considers the problem of
finding one optimal solution, but all optimal solutions (or rather all solutions within a
given distance of the optimum), then CLP becomes a plausible competitor. Table 3
reports this experiment: four programs are compared:
. The first one is just a straightforward adaptation of our previous constraint
program basic. Instead of stopping at the first solution, we explore the whole tree.
. The second is a similar branch and bound exploration where the flow
algorithm is used to evaluate the optimal matching at each node instead of using an
upper bound estimate. The flow algorithm is actually only triggered when one of the
edges of the current "optimal" matching is removed from this dynamic graph.
. The third program is similar with a different branching scheme. For each edge
of the original optimal solution we explore two branches : either the edge is part of the
matching or it is removed from the dynamic graph.
. The fourth program is a branch and bound algorithm similar to the third one,
except that the Hungarian method is used instead of the flow algorithm. We here take
advantage of the incrementality of the Hungarian method (its ability to recompute the
optimal matching in a single iteration when an edge is discarded at a node of the
search tree).
For this exploration, the bottleneck is the amount of computation performed at each
node of the search tree. The incremental Hungarian method is the best algorithm since
it explores very small search trees (all explored branches lead to an admissible
solution), however, the constraint algorithm is a fair competitor because it performs
much less work per node.
1%
4 sol.
2%
9 sol.
5%sol.
0,5%.
3 sol.
1%
8 sol.
2,5%
sol.
Basic 1249 b.
b.
8000 b.
14 kb.
1.1 s.
38 kb.
2s.
140kb.
Flow algorithm 137 b.
9 s.
224 b.
2000 b.
100 s.
100 b.
26 s.
172 b.
215 b.
48 s.
1,5kb.
200 s.
Flow algorithm
with new branching
57 b.
136 b.
b.
34 b.
b.
22 s.
195 b.
Hungarian
matching
b.
58 b.
b.
b.
b.
b.
b.

Table

finding all solutions
Hence for the problem of finding all near-optimal perfect matchings, the constraint
program behaves better than our basic Operations Research program (the adaptation
of the flow algorithm) and not as well as our smarter O.R. program (incremental
Hungarian method). The big advantage of the constraint program is it simplicity: it is
indeed much easier to implement than both of the O.R. algorithms (naive and smart).
It seems therefore to be good candidate for real-life matching problems involving a
few additional constraints (and which thus require more exploration of the space of
solutions than the pure problem).
4. Complex matching
In this section, we address the case of two real-life variations of the matching
problem. Ad-hoc algorithms could also probably be specially designed for these
variations of the problem. However, from a methodological point of view, we decided
to consider only adaptations of the original solutions that could be implemented in a
reasonable amount of times (since the constraints programs are adapted in a matter of
minutes).
4.1 Replacing k machines
Suppose that in a plant, the manager has the funds to replace k machines among the
n, by newer ones. We want to find an optimal assignment (maximum
bringing maximal production) of tasks to machines, given that newer machines are
more efficient than older ones. This means that the matching problem is extended
with the additional choice of those k vertices in V 1 for which we prefer to use a
different weight matrix (say weight' instead of weight). For the sake of comparison,
we implemented three solutions for this problem, one using constraint propagation
and two O.R. solutions, a basic adaptation of the flow algorithm and a smart
adaptation of the Hungarian method:
. The first one is a straightforward adaptation of our constraint-based program
basic. The principle is to postpone the choice of the k "new" vertices as much as
possible, but to take them into account with a modified upper bound estimate. Instead
of taking the sum of the best choices for all nodes, we add to this sum s
the sum of the k heaviest edges in the "difference graph" (defined by the gain in the
production function between new and old machines, i.e. considering weight'(uv) -
weight(uv) as the weight of the edge uv). Like the bounds s
can be maintained incrementally.
. The second program is based on the flow algorithm. It goes through a search
tree where the nodes at depth i correspond to the choice of the i th machine to replace.
All branches are explored. Whenever a decision of replacement is made, the
production function is updated (i.e., the second weight function is used for the i th
machine). At each node, the upper bound (computed for pruning) is the sum of the
optimal solution for a matching in the original graph (where i of the k decisions have
been made) and of the optimal solution for a matching of cardinal k-i in the difference
graph.
. The third program is based on the Hungarian method. The algorithm goes
through the same search tree as the program looking for all near optimal solutions (cf
section 3.3) : at each node a vertex v from V 1 selected and each branch
matches one of the vertices x of by removing all edges vx' for x' -
x. The first branch explored corresponds to the current assignment of v in the solution
given by the Hungarian method. The upper bound is the sum of the best possible
matching (given by the Hungarian method) with an estimate of a sub-matching of size
k in the "difference graph" (same estimate as for the constraint algorithm)
Constraints 266b
0,1s
433b
0.1s.
735b
0.1s.
19kb
2.1 s.
26kb
9.9 s.
4,4Mb
700 s.
Flow 5 s.
Hungarian
Matching
20b.
22b.
31b.
30b.
30b.
34b.
40b.
71b.
107b.

Table

replacing k machines

Figure

4 shows these three strategies on a few problems. The constraint-based
approach performs better than the approach based on the flow algorithm but not as
well as the algorithm using the Hungarian method. The constraint approach is much
faster than this smart O.R. algorithm for n=10, a little faster for n=20, somewhat
slower for n=30 and much slower for n=40 (which is anyway the upper limit for the
constraint-based approaches on pure matching problems). Its main advantage is its
simplicity (it took a few simple lines of code to modify the upper bound in the
original constraint algorithm) compared to both O.R. algorithms. This makes the
constraint approach a good solution for small and mid-sized problems (even for
values of k up to 10), while the solution based on the incremental Hungarian method
is well adapted to large problems.
4.2. Bi-matching
This second problem addresses the case of the combination of two matching
problems (with two distinct weight matrices), where one problem is used for
satisfiability and the other one for optimization (in a task-to-machine assignment, this
amounts to maximizing production while keeping the energy consumption below a
certain level). The difficulty varies according to the role played by the passive
matching problem : if the value chosen for the maximal energy consumption is low or
high, the energy matching is dominating the problem or is marginal. On the other
hand, intermediate values make the problem much harder, because the shape of the
solution space is equally affected by both matching problems. This implies that the
distribution of feasible solutions in the search tree is no longer concentrated in one or
a few areas, but is more dispersed. From a linear programming perspective, a bi-
matching problem is made of three components: the matching constraints (shared by
the two matching problems), the energy consumption constraint and the cost function
that represent the optimization on production. A classical approach in such a situation
is to use Lagrangean relaxation to push the energy constraint into the cost function.
Here again, we implemented several solutions that find the maximal production for
a matching which consumption is less than a given constant
. The first one is also a straightforward adaptation of our basic constraint
program. The search is guided by the optimization on the production. The
consumption constraint is only used for pruning: Two lower bounds of the
consumption are estimated by the sum of the edges of least consumption
for each vertex set. Moreover, instead of considering the regret for the production
function, we consider the sum of the regrets for both the production and the energy
function. Therefore, this program is obtained by a simple replication of a few lines
from the original basic program, where energy is substituted to production.
. The second algorithm is a branch and bound algorithm using twice the
(incremental) Hungarian method. Two Hungarian matchings are constructed: one of
maximal production and one of minimal consumption. Branching is based on the
Hungarian matching of maximal solutions. Both these matchings are used to prune: a
branch can be cut off when the minimal consumption is strictly greater than E or
when the maximal production is less than the best one found so far.
. The third one and fourth are based on Lagrangean relaxation with Busaker's
flow algorithm and the Hungarian method. The general principle of this method is to
put some constraints in the objective function with a certain coefficient, and to vary
the value of this coefficient [Re 93], assuming that the relaxed problem (i.e., without
the constraint that was pushed into the cost function) is simpler to solve. Here, If we
"push" the energy constraint into the cost function, we obtain a simple matching
problem that we solve with the flow algorithm. The objective function becomes the
total weight of the matching with the following weight function on the edges:
weight l (u,
Let us call f(l) the value of the maximum matching for weight l By construction,
f(l) (for l - 0) is an upper bound for the original problem since the energy
consumption has to be smaller than E. Now, if we compute the value F which is the
minimal value for f(l) when l varies (l - 0), F is also an upper bound (that can be
found through a dichotomic search). This provides us with an upper bound of high
quality, and also, while varying the value of l, a possible lower bound (if one of the
l yields an admissible energy). These bounds are computed at each node of the search
tree, and branching is made on the edges of the matching of the optimal flow, as was
indicated in the third approach in the previous section. The third program is a
straightforward implementation of the Lagrangean relaxation with the flow algorithm,
the fourth one is an implementation of the Lagrangean relaxation with the Hungarian
method, that tries to be as incremental as possible (trying to keep part of the dual
solution for similar values of l)
(inc. Hung. Match.)
2.4kb
2.6kb
7.1 s.
3.2 kb
140kb
500 s.
900 s
14kb.
Lagragean Relaxation
with the flow algorithm
20b.
31b.
102b.
22b.
107b.
31b.
72 s.
197b.
87b.
Lagragean Relaxation
with the Hung. Match.
14b.
5.1 s.
64b.
80b.
28b.
86b.
50 s.
28b.
180b.
296b.
Constraints (Basic) 1kb.
28kb.
1.2 s.
30kb.
1.3 s.
2kb.
900kb
43 s.

Table

bi-matching

Table

5 compares all four algorithms on two problems where the cost and weight
functions are randomly generated with values ranging from 1 to 100. There is a
balance between optimization on the cost and feasibility on energy : they both can cut
the search tree. If E is small (close to the value of a minimal energy consumption
matching), the energy is responsible for all the pruning and the program behaves like
a simple matching one. Symmetrically, if E is large, the problem is almost
unconstrained and looks like a simple maximal production matching program. The
hardest situation is when energy and cost are both responsible for pruning the search
tree. This situation corresponds to E@ 550 and E @ 900 in our examples. Lagrangean
relaxation pays off for large problems, when no criterion dominates the other.
However, it seems that for real life problems a criterion most often dominates the
other. From this point of view, the constraint approach is much more efficient.
Here again, the constraint program performs better than the simple O.R.
algorithm (with the two incremental Hungarian matchings). But it also performs better
(except for the balanced situation for n=30) than the complex LR program. In fact, the
Hungarian method is only mildly incremental for the Lagrangean relaxation scheme.
The dual solution cannot be easily repaired after a change of weight function.
5. Application
In the previous section we have shown the strenghts of the constraint-propagation
approach compared with more specialized algorithms. We shall now see that these
techniques should be combined and not opposed. We consider a time-tabling problem
which consists of filling a weekly schedule with a set of lessons (of duration 1 to 4
hours). Each lesson is given a set of possible start times and a set of preferred start
times. The schedule is made of 10 half-days of 4 hours and lessons should not be
interrupted. This section illustrates how weighted matching techniques can be applied
to such a problem and provide significant improvement. We notice that if all lessons
were of duration 1, this problem would indeed be a matching problem. This suggests
a straightforward relaxation where we consider lessons to be interruptible. Second,
preferences can be encoded using weights so that the minimum weight matching
corresponds to the assignment using as many preferred start times as possible.
In the rest of the paper, we consider m lessons l 1 . l m , and a schedule with n time
slots of length 1 hour 4). For each lesson, we are given two lists of time
slots (integers between 1 and n) that represent respectively the set of possible and
preferrred start times. The goal is to find a start time for each lesson so that
. no two lessons overlap. This is the ususal disjunctive scheduling constraint: for all
pairs of lessons l,l' either start(l') - start(l)
. each lesson fits into a half day. So within a half day (says the i th half-day, covering
the time units {4i+1, 4i+2, 4i+3, 4i+4}), lessons of duration 4 can only start at the
first unit (4i+1), lessons of size 3 can only start at units 4i+1 and 4i+2 , etc.
. the number of defaults, defined by the number of lessons which are assigned a
start time outside the set of preferred times, is minimal
This problem is very dependent on the range of input data. The problem can be
seen as the combination of a satisfiablility problem (filling the schedule) and an
optimization problem (an assignment problem). When the lessons are large, if there
are enough of them, the problem may look like a bin-packing, where the preference
optimization is almost irrelevant. On the other hand, with smaller lessons, the packing
is much easier and the optimisation problem dominates. Similarly, the difficulty of the
preferences (i.e., the tightness of the preference sets) will augment the importance of
the optimization component of the problem. We have picked three problems that are
representative of different situations: Problem 1 uses rather short lessons (such as in a
high-school schedule) with complex preferences (the optimum is 6 defaults). Problem
2 is similar (from a lesson size point of view) but has simpler preferences (the
optimum is 1). The last problem uses larger lessons to explore how the algorithm
would react to a problem where satisfiability is an issue.
In order to exploit the matching relaxation, we decompose each lesson of duration k
into k units of 1 hour. The total number U of units is, therefore, the sum of the
durations of the lessons. The matching that we need to build associates its start time (a
time slot) to each unit. For a unit u associated to a lesson l, and a time slot i, we give a
weight to each edge (u,i) as follows:
cannot happen at i because it would imply an illegal start
time for the lesson l,
if u can happen at i but this implies a start time outside the
preferred set,
happens at i when the lesson l starts at one of its
preferred time.
We can now define MinWeightAllDifferent({start(u 1 ), ., start(u U )}, w) as the
minimum weight matching for this graph. Recall that this value can be computed
efficiently with the Hungarian matching, and that it can also be maintained
incrementally throughout the search procedure (section 3. described how to
recompute this value when a few edges have been removed in the graph). Since the
lesson l has k units, it is straightforward to check that an optimal solution of our time-tabling
problem will correspond to a minimum weight matching. For each schedule
with D defaults, the value of the matching is 1000 * U - 12 * D. Thus, if we search for
a solution with less than D defautlts, we can use the redundent constraint :
To solve the three problems, we have used a branch-and-bound algorithm that
minimizes the number of defaults. Branching is done on the starting time of a lesson,
trying all perefered values first. The lesson on which to branch is picked using the
first-fail heuristics. Each start time decision is propagated as follows:
. We discard values from other lessons that could cause an overlap with the lesson
that has been assigned.
. The start time of the units composing the lessons are set accordingly.
. When the number of default reaches the upper bound, all edges that are not
preferred are removed.
. We use a redundent constraint to detect when it becomes impossible to place large
lessons. For each value d of duration that is strictly larger than a half-day (for
example 3 hours), we compute the set of lessons lessons(d) with this duration and
the union of all possible half days for these lessons possible(d). we then check that
possible(d) - lessons(d). Finally, we check that possible({4,3,2}) -
2.
Problem 1
(24 lessons 39h)
Problem 2
(26 lessons 40h)
Problem 3
(14 lessons 39h)
1. simple propagation 189 kb. 1541 s. 286 kb. 1040 s. 43 kb. 246 s.
2. matching cut 31 kb. 177 s. 269 kb. 1008 s. 27 kb. 160 s.
3. Regin's filter 31 kb. 197 s. 269 kb. 1243 s. 27 kb. 160 s.
4. weighted matching cut 3511 b. 29 s. 234 b. 2.6 s. 17 kb. 120 s.
5. global consistency 1206 b.
shaving - 382 b. 96 s. 183 b. 11 s. 5888 b. 314 s.

Table

Applying various weighted matching techniques to a time-tabling problem

Table

6 gives the result obtained with the following approaches :
1. The first method only performs constraint propagation.
2. The second method checks that the underlying matching problems (for the units)
is still feasible (i.e., there exists a perfect matching).
3. The third method removes all edges that do not belong to at least one perfect
matching using Regin's algorithm [R-94].
4. The fourth method uses our new global constraint MinWeightAllDifferent (1)
which is propagated as explained earlier using the incremental Hungarian method.
5. The fifth method uses a look-ahead consistency check trying for each un-assigned
lesson l to discard all prefererred (respectively non-preferred) edges. - Trying -
here means to detect if the removal of the values would create a contradiction
through the propagation of the constraints. If a contradiction is detected, we
deduce that the lesson l must start at a preferred (resp. non-preferred) time.
6. The sixth method applies a global consistency technique which consists of trying
each possible start time and removing those who produce a contradiction. This is
similar to the shaving technique that is used for jobshop scheduling [CL96].
A few conclusions can be drawn from these experiments.
. First, our global constraint MinWeightAllDifferent brings a serious improvement
over standard propagation (local consistency). For problem 2, the number of
backtracks is divided by a factor of 1000. Moreover, the overhead for keeping the
value of the minimal weight matching up to date with the incremental Hungarian
method is very reasonable, compared to the the cost of simple matching propagation
and bounding for defaults. Indeed, with the addition of the MinWeightAllDifferent the
average time per backtrack over the three instances goes from 4,1 ms. to 7,3 ms.
Therefore, the gain in search tree sizes turns into a real speedup.
. Second, the propagation of the unweighted matching constraint (the difference
constraint), which can be done very efficiently with the filtering algorithm proposed
in [R- 94], has a marginal impact on the resolution of the problem compared to the
propagation of the weighted matching constraint.
. Third, it seems a good idea to check global consistency by performing a limited
breadth-first exploration of the search tree (limited to depth one). This seems to work
better for branching decisions based on satisfaction of lessons (method 5) rather than
for actual assignements of time slots to lessons (method 6). This is due to the fact that
the complexity of method 5 is smaller than that of method 6. Moreover, these global
consistency techniques work best for time-tables with large blocks (lessons with
duration 3 and 4), rather than on problems with small lessons, where the matching
relaxation is more accurate.
6. Conclusion
A first conclusion might be that constraint propagation is not a competitive
technique for pure weighted matching problems. Specialized algorithms are simple
enough and should be used appropriately. On the other hand, constraint propagation is
a more plausible approach to augmented matching problems. Depending on the
complexity of additional constraints and the size of the problem, the performances
obtained (easily) with a CP approach range from reasonable to excellent, compared to
more specialized approaches. In the few cases where this is not good enough, the best
approach is to incorporate some of the weighted matching techniques into a constraint
based branch and bound search.
The first contribution of this paper is a set of generic techniques that improve the
performance of constraint-based branch-and-bound algorithms for such problems,
namely a binary branching scheme based on regret, the use of the implicit symmetry
and the look-ahead bounding functions. These techniques may be applied to any
augmented matching problem and were actually applied with success to the Traveling
Salesman Problem [CL97].
Our second contribution is to show that indeed a weighted matching can be
considered as a global constraint (MinWeightAlldifferent), since we know how to
propagate it efficiently using the incremental version of the Hungarian algorithm. This
is a very useful global constraint, as we have shown with our time-tabling example. A
constraint solver that offers this feature will be able to solve problems with hard and
soft constraints at the same time, taking advantage of the weights, whereas a system
that relies on simple matching only will implement soft constraints as a second layer,
in a much less efficient way. We must also notice that this feature allows us to
combine the best of both worlds for the two augmented problems that we studied in
Part 4: we keep the simplicity and flexibility of the constraint-based approach, while
ensuring the robustness of the underlying matching algorithm.

Acknowledgments

We would like to thank an anonymous referee for his helpful comments and
suggestions on an earlier version of this paper.



--R

A Deductive and Object-Oriented Approach to a Complex Scheduling Problem
Improved CLP Scheduling with Tasks Intervals.
Cumulative Scheduling with Task Intervals.
Solving small TSPs with Constraints.
Introduction to Algorithms.
Matching. in Handbook in Operations Research and Management Science (Networks)

Faster Scaling algorithms for network problems.
Concurrence et coop-ration de mod-les multiples
Consistency in networks of relations.
Running efficiently arc consistency
Combinatorial Optimization.
A Filtering Algorithm for Constraints of Difference in CSPs
Modern Heuristic techniques for combinatorial problems.
Constraint satisfaction in Logic Programming.
Graph Algorithms.
--TR
weighted matching;resource allocation;global constraint;hungarian method