Applications of Matching Theory in Constraint Programming

School:

University of Hannover

Heribert Vollmer

Abstract:

One of the most important and most studied areas in constraint programming is global constraints. Global constraints are classes of constraints defined by a relation between a non-fixed number of variables. This thesis deals with matching theory and its application in constraint programming. Based on the existing results of matching and decomposition theory, a universal method will be devised for solving various global constraints.

All constraints should have the property that their solution is representable as a matching problem in a particular graph. The basic idea is to model the solution to the global constraint as a maximum, perfect or complete matching. The edges belonging to no matching (forbidden edges) can be removed from the auxiliary graph because the corresponding values do not belong to a solution. The partition of edges can be computed by means of the so-called alternating breadth-first search and alternating depth-first search.

First, the bipartite matching will be discussed and some constraints representable by a matching in a bipartite graph will be considered. The mandatory and forbidden edges can be found by means of the Dulmage-Mendelsohn Canonical Decomposition. In this chapter we describe a generic propagation routine for the following constraints and their soft versions: alldifferent, correspondence, inverse, same, used_by, gcc, and symmetric_gcc.

The next chapter examines constraints solvable by the matching for general graphs. The partition of edges can be determined by means of the Gallai-Edmonds Structure Theorem. A constraint modeled as a maximum matching problem is the well-known constraint symmetric_alldifferent and its variants, such as symmetric_alldifferent_except_0, symmetric_alldifferent_loop and soft_symmetric_alldifferent_var, and 2-cycle, as well the proper_forest constraint. By means of the Lovasz-Plummer Decomposition the constraints tour and undirected_path can be partially solved.

The next chapter introduces a directed matching. This matching can be found by means of the bipartite graph so the method proposed for the bipartite matching can be easily applied. The propagation rules described in this chapter can have an application to some graph partitioning constraints such as circuit, cycle, derangement, soft_derangement_var, tree, binary_tree, path and map. These constraints are mostly intractable and therefore the domains can be only partially reduced.

In the last chapter of the thesis the weighted matching is disputed. This matching can have an application to solve optimization constraints representable as a weighted matching problem. There are two kinds of weighted matchings: a vertex-weighted matching and an edge-weighted matching. By the first matching the constraints such as wpa, nvalue or swdv can be solved. By the second matching the constraints cost_alldifferent, soft_inverse_var, cost_gcc, cost_symmetric_gcc, cost_symmetric_alldifferent, as well as cost_tour and cost_path can be modeled. Some of the constraints represent NP- complete problems so only incomplete filtering is possible.

Keywords: matching theory, decomposition theory, extreme sets, dominators, constraint programming, global constraints, filtering algorithms, computational complexity radoslaw_cymer_-_applications_of_matching_theory_in_constraint_programming.pdf