Application Of Constrain Programming In Stable Matching

The problem of stable matching problem was raised in 1962 by Nobel laureates Alvin Roth and Lloyd Shapley.The matching problem is to match a group of objects with another group of objects and is subject to preference lists and capacity constraints during the matching process.Preference list is the preference of an object for other objects.The preference list of the object may be complete(preference sorting for all objects),or it may be incomplete(preference sorting only for some objects).The capacity indicates that the object can match at most the number of other objects.Stability is one of the important criteria for evaluating the match.When a match satisfies the stability condition,it is considered that the match is a stable match,otherwise it is an unstable match.Stable Marriage(SM),Hospitals/Residents(HR),and Stable Roommates(SR)are known as the three classical stable matching problems.The main research content of this paper is based on the constrained modeling and solving of stable marriage problem and stable roommate problem of complete preference sequence and non-complete preference sequence..Constraint Satisfaction Problems(CSPs)is an important research direction in the field of artificial intelligence.Related technologies are widely used in the fields of configuration,scheduling,and combination problem solving.We can define a stable marriage problem or a stable roommate problem as the constraint satisfaction problem,and convert the solution to the stable matching problem to solve the constraint satisfaction problem.At present,there are many mature solvers that solve the constraint satisfaction problem,such as Ilog Solver,Gecode,Choco,Mistral and so on.The Choco solver is a java library for solving constraint satisfaction problems and optimization problems.It provides a relatively complete set of modeling languages that can be used to model and solve problems simply and quickly.Because of its ease of use and extension,Choco solvers are widely used in teaching and research.The main work of this article is as follows:(1)This paper mainly studies the problem of stable matching.First,it introduces the problem of stable marriage;then,it introduces several common variants of stable marital problems,and gives general solutions to solve such problems;Finally,it introduces hospital/doctor problems and the algorithm for solving them.(2)Analyze and research Choco solvers and constraint programs.Firstly,the structure of Choco solver and the main used jar package are introduced.Secondly,how to use Choco solver for simple modeling and solving is introduced.Once again,the constraint satisfaction problem and constraint program are introduced.Finally,the constraints are described.The mechanism of communication.(3)Mainly to improve the constraint model to solve the problem of stable matching.Firstly,the characteristics of the CP model are described.Second,the disadvantages of the CP constraint model are analyzed.Third,the original model is not preprocessed for the original preference sequence,and there is still a large amount of redundant data in the preference sequence after implementing the arc compatible algorithm.Disadvantages proposed corresponding improved algorithm;Finally,the improved model and the original model were compared experimentally and the conclusion was given.Experiments show that our algorithm has obvious improvement.