China
Africa
Explore chapters and articles related to this topic
Heuristic and Metaheuristic Techniques for Optimization
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
Constraint programming assumes that the problem can be described as a set of variables and a set of constraints that restrict the feasible solutions for a problem. Each variable has a domain: a set of feasible values. The constraints can be logical relations (for example, only one of a set of variables can be true), mathematical constraints (e.g., x ≤ 5), integer, Boolean, real valued, and so on. Constraint programming defines the problem independent of the solution method. Disjunctive constraints: When the domain consists of discrete values, a disjunctive constraint states that only one of a set of conditions can be true. When the variables are real valued ranges, the constraint states that the ranges must not overlap.Conjunctive constraints: These are similar to disjunctive constraints, but in this case, there is a limit on the number of conditions that can be true.Temporal constraints: In scheduling applications, these constraints specify that one activity must precede another activity by at least some amount of time. For example, job B cannot start until job A has ended.
Constraint Programming
Published in Jay Liebowitz, The Handbook of Applied Expert Systems, 2019
A key innovation behind constraint programming is constraint propagation. Propagation is a generalization of data-driven computation. Consider the constraint x=y+l, where x and y are variables. In a constraint program, any assignment to the variable y (e.g., y = 5) causes an assignment to x (x = 6). Moreover, the very same constraint also works in the other direction: any assignment to x (e.g., x = 3) causes an assignment to y (y = 2).
Solving the integrated process planning and scheduling problem using an enhanced constraint programming-based approach
Published in International Journal of Production Research, 2022
Ganquan Shi, Zhouwang Yang, Yang Xu, Yuchen Quan
The Constraint Programming-based approach is usually expressed through variables, corresponding domains of these variables, and constraints, including objectives. The constraint optimization problem to minimize or maximize an objective function can actually be regarded as a constraint satisfaction problem (CSP) by comparing the values for all feasible solutions and displaying the best one. The solution procedure contains a constraint propagation phase and a search phase. The constraint propagation phase filters out the values that lead to infeasible solutions. Because variables interact with each other, constraint propagation will be triggered when a change of certain variables occurs until the domains of all variables stop changing. Subsequently, a backtracking search is performed to branch through and explore the solution space. When a feasible solution is found, the search excludes worse solutions by adding a new constraint to the objective function. Once the whole space has been explored or the estimated lower bound is reached, the optimality is affirmed.
Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility
Published in International Journal of Production Research, 2020
Oliver Polo-Mejía, Christian Artigues, Pierre Lopez, Virginie Basini
Constraint programming is a technique coming from logic programming and artificial intelligence to solve complex combinatorial problems using a declarative description. The idea is to separate the constraint declaration using a rich constraint language from the solution-finding process based on the so-called constraint propagation, an active use of constraints to reduce the search space (Baptiste, Le Pape, and Nuijten 2001; Young, Feydy, and Schutt 2017). Constraint programming has been successfully applied to solve RCPSP. In Kreter, Schutt, and Stuckey (2017), the authors proposed and tested six different CP models for the RCPSP with calendar constraint, and they showed that CP solutions are highly competitive with existing MILP formulations of the problem (average runtime required by CP models is lower). Young, Feydy, and Schutt (2017) used pure Constraint Programming to solve the MSPSP. In their work, the authors proposed and tested different configurations of CP models, together with different search and propagation techniques. Using the best of their configurations, the authors were able to close an important number of open instances of the literature, showing a better performance than the Branch-and-Price algorithm proposed by Montoya et al. (2014), thus proving the interest of using CP for solving the MSPSP.
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.