The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently de...The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.展开更多
Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerf...Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.展开更多
Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for...Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraintsatisfaction problem (DFCSP). Fuzzy constrains are thus used to naturally represent each agent''sdesires involving imprecision and human conceptualization, particularly when lexical imprecision andsubjective matters are concerned. On the other hand, based on fuzzy constraint-basedproblem-solving, our approach enables an agent not only to systematically relax fuzzy constraints togenerate a proposal, but also to employ fuzzy similarity to select the alternative that is subjectto its acceptability by the opponents. This task of problem-solving is to reach an agreement thatbenefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the dealmore quickly since their search focuses only on the feasible solution space. An application tomultilateral negotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework.展开更多
Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous v...Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi value constraint.展开更多
Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques hav...Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques have been proposed. To generate effective test data, we propose a test-data generation technique guided by static defect detection in this paper. Using static defect detection analysis, our approach first identifies a set of suspicious statements which are likely to contain faults, then generates test data to cover these suspicious statements by converting the problem of test-data generation to the constraint satisfaction problem. We performed a case study to validate the effectiveness of our approach, and made a simple comparison with another test-data generation on-line tool, JUnit Factory. The results show that, compared with JUnit Factory, our approach generates fewer test data that are competitive on fault detection.展开更多
Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm ...Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound (BB) is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.展开更多
Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering...Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics: a variable's dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.展开更多
In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposi...In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity.展开更多
基金This work was supported by Lebanese National Council for Scientific Research.
文摘The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.
基金supported by Guangdong Major Project of Basic and Applied Basic Research No.2020B0301030008Science and Technology Program of Guangzhou No.2019050001+2 种基金the Chinese Academy of Sciences Grant QYZDJ-SSWSYS018the National Natural Science Foundation of China(Grant No.12171479)supported by the National Natural Science Foundation of China(Grant Nos.11301339 and 11491240108)。
文摘Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.
文摘Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraintsatisfaction problem (DFCSP). Fuzzy constrains are thus used to naturally represent each agent''sdesires involving imprecision and human conceptualization, particularly when lexical imprecision andsubjective matters are concerned. On the other hand, based on fuzzy constraint-basedproblem-solving, our approach enables an agent not only to systematically relax fuzzy constraints togenerate a proposal, but also to employ fuzzy similarity to select the alternative that is subjectto its acceptability by the opponents. This task of problem-solving is to reach an agreement thatbenefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the dealmore quickly since their search focuses only on the feasible solution space. An application tomultilateral negotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework.
文摘Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi value constraint.
基金sponsored by the National High-Tech Research and Development 863 Program of China under Grant No.2007AA010301the National Natural Science Foundation of China under Grant Nos. 60803012 and 90718016China Postdoctoral Science Foundation funded project under Grant No. 20080440254
文摘Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques have been proposed. To generate effective test data, we propose a test-data generation technique guided by static defect detection in this paper. Using static defect detection analysis, our approach first identifies a set of suspicious statements which are likely to contain faults, then generates test data to cover these suspicious statements by converting the problem of test-data generation to the constraint satisfaction problem. We performed a case study to validate the effectiveness of our approach, and made a simple comparison with another test-data generation on-line tool, JUnit Factory. The results show that, compared with JUnit Factory, our approach generates fewer test data that are competitive on fault detection.
基金supported by the Hi-Tech Research and Development Program of China(2012AA011201)the National Natural Science Foundation of China(61202080)+1 种基金the Major Program of the National Natural Science Foundation of China(91318301)the Open Funding of State Key Laboratory of Computer Architecture(CARCH201201)
文摘Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound (BB) is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.
基金supported in part by the National Natural Science Foundation of China under Grant No. 61070039
文摘Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics: a variable's dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.
文摘In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity.