China
Africa
Explore chapters and articles related to this topic
A Constraint Programming Solution for the Military Unit Path Finding Problem
Published in Jitendra R. Raol, Ajith K. Gopal, Mobile Intelligent Autonomous Systems, 2016
Louise Leenen, Alexander Terlunen, Herman le Roux
The modelling of problems in terms of constraints has the advantage of a natural, declarative formulation. When a problem is defined as a Constraint Satisfaction Problem (CSP), it is a representation of what must be satisfied, without specifying how it should be satisfied. A CSP consists of a set of variables, a set of domains for the variables, and a set of constraints. Each constraint is defined over a subset of the set of variables. A constraint is a logical relation involving one or more variables, where each variable has a domain of possible values. A constraint thus restricts the possible values that variables can have. Constraints can specify partial information about variables, are declarative and may be non-linear. A solution to a CSP specifies values for all the variables such that all the constraints are satisfied. There are many general-purpose techniques that can be used to solve CSPs, for example, integer programming, local search, and neural network techniques, but there is a special-purpose technique that is widely used: tree search in conjunction with backtracking and consistency checking. Constraint Programming (CP) is a term that refers to the computational systems used to solve CSPs. CP emerged from a number of disciplines such as artificial intelligence, computational logic, programming languages and operations research. CP has proven to be effective at solving combinatorial and over-constrained problems, that is, sets of constraints that cannot be satisfied. There are several texts that provide an introduction to CP and CSPs [22,23].
Unification of Artificial Intelligence with Optimization
Published in Jay Liebowitz, The Handbook of Applied Expert Systems, 2019
Constraint and Rule Satisfaction Problem (CRSP) is a hybrid representation and reasoning method encompassing both Constraint Satisfaction Problems (CSP) and rule-based systems. CSP is a kind of problem in Artificial Intelligence that requires the assignment of values to variables that are subject to a set of compatibility constraints (Kumar, 1992; Macworth, 1986). Much research has improved the applicability of CSP methodology to practical field problems (Bowen and Bahler, 1991; Davis and Rosenfield, 1981; Detcher and Pearl, 1988; Montanari and Rossi, 1991). To enhance the representational power of CSP, the integration of constraints and rules in a unified framework is attempted (Lee and Kwon, 1995).
A cerebellar operant conditioning-inspired constraint satisfaction approach for product design concept generation
Published in International Journal of Production Research, 2023
Mingdong Li, Shanhe Lou, Yicong Gao, Hao Zheng, Bingtao Hu, Jianrong Tan
The constraint satisfaction methods proposed to solve CSP can be divided into three categories: backtracking-based methods, heuristic algorithms, and machine learning-based approaches. Regarding backtracking-based methods, Yang and Dong (2013) proposed a backtracking search method to solve CSP in product configuration with cardinality-based rules. Pascal and Panescu (2019) adopted asynchronous backtracking and weak commitment search to solve a distributed CSP on rescheduling in manufacturing systems. Mechqrane et al. (2020) developed an agile asynchronous backtracking method to solve the decision-making tasks in physically distributed agents without a static total ordering of them. Shi et al. (2021) proposed a depth-first search method for generating an AND/OR graph with minimal nodes. Song et al. (2022) proposed a deep reinforcement learning-based approach to automatically determine better variable ordering, which significantly improved the efficiency of backtracking search. However, with the increasing complexity or frequent changes in design space, the computational workload will increase significantly in backtracking-based methods.
Problem Specific Variable Selection Rules for Constraint Programming: A Type II Mixed Model Assembly Line Balancing Problem Case
Published in Applied Artificial Intelligence, 2020
Hacı Mehmet Alakaş, Bilal Toklu
Constraint programming (CP) is widely used for solving constraint satisfaction and optimization problems. Researchers have successfully achieved the solution of various problems with CP such as scheduling (Sel et al. 2015; Serra, Nishioka, and Marcellino 2012), manufacturing (Banaszak, Zaremba, and Muszyński 2009; Soto et al. 2012), supply chains (Lee and Lee 2013; Rodrigues and Leandro 2007), rostering (He and Qu 2012; Qu and He 2009), vehicle rooting (Ozfirat and Ozkarahan 2010) and allocation (Bui, Pham, and Deville 2013). Mainly, related problems in CP are modeled and solved as constraint satisfaction problems (CSP). The CSP consists of an n-tuple of variables which are related to their domain di and m-tuple of constraints. The CSP has a solution when all variables take value in their domains. The values must satisfy all constraints. Backtracking, branch, and bound algorithm or local searches are generally used to explore and obtain the CSP problem’s solution. Two main phases are processed to explore the solution. First one is an enumeration strategy which composed of variable and value selections. The second one is the propagation which is used to filter the variable domains by eliminating the inconsistent values.
Job shop scheduling with the option of jobs outsourcing
Published in International Journal of Production Research, 2019
Hamid Safarzadeh, Farhad Kianfar
Constraint Programming (CP) is an alternative approach to solve the combinatorial optimisation problems, which originates in computer science and artificial intelligence community. It was initially developed to solve constraint satisfaction problems (CSP), i.e. the constrained problems aiming to find a feasible solution. However, later on CP was utilised to solve the optimisation problems too (Gass and Fu 2013). This approach has been applied successfully in different areas such as production planning, scheduling, timetabling, supply chain management, production configuration, molecular biology, robotics, etc. (Benhamou, Jussien, and O’Sullivan 2007). The major solution strategy in CP, called constraint propagation, is based on analysing the existing constraints to infer new ones, reducing the domains of the decision variables based on the new constraints, and communicating the reduced domains to the constraints. This procedure continues iteratively with the aim of restricting the solution space and solving the problem (Lustig and Puget 2001). CP likewise MILP, and in contrast to the metaheuristic algorithms and most of the heuristic algorithms, is capable of proving solution optimality. However, CP may be more efficient than MILP when the problem is constraint intensified, since it gains the constraints effectively in solving the problem.