China
Africa
Explore chapters and articles related to this topic
Constraint-Based Resource Allocation for Air Cargo Transfer Planning
Published in Don Potter, Manton Matthews, Moonis Ali, Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2020
In general, any scheduling and resource allocation problems can be formulated as a constraint-satisfaction problem (CSP) which involves the assignment of values to variables subjected to a set of constraints. CSP can be defined as consisting of a finite set of n variables v1, v2,…, vn, a set of domains d1, d2, …, dn, and a set of constraint relations c1, c2, …, cm. Each di defines a finite set of values (or solutions) that variable vi may be assigned. A constraint Cj specifies the consistent or inconsistent choices among variables and is defined as a subset of the Cartesian product: cj ⊆ d1xd2x … x dn. The goal of a CSP algorithm is to find one tuple from d1 x d2x … x dn such that n assignments of values to variables satisfy all constraints simultaneously.
Introduction to Artificial Intelligence and Soft Computing
Published in Konar Amit, Artificial Intelligence and Soft Computing, 2018
Constraint Satisfaction: This method is concerned with finding the solution of a problem by satisfying a set of constraints. A number of constraint satisfaction techniques are prevalent in AI. In this section, we illustrate the concept by one typical method, called hierarchical approach for constraint satisfaction (HACS) [47]. Given the problem and a set of constraints, the HACS decomposes the problem into sub-problems; and the constraints that are applicable to each decomposed problem are identified and propagated down through the decomposed problem. The process of re-decomposing the sub-problem into smaller problems and propagation of the constraints through the descendants of the reasoning space are continued until all the constraints are satisfied. The following example illustrates the principle of HACS with respect to a problem of extracting roots from a set of inequality constraints.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
In constraint satisfaction problems, variables can assume different types including: Boolean, integer, symbolic, set elements, and subsets of sets. Similarly, a variety of constraints are possible, including: mathematical: C=s+p (completion time = start time + processing time)disjunctive: tasks J and K must be done at different timesrelational: at most five jobs to be allocated at machine R50explicit: only jobs A, B, and E can be processed on machine Y50
The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm
Published in International Journal of Production Research, 2020
Mateus Martin, Pedro H.D.B. Hokama, Reinaldo Morabito, Pedro Munari
The BSP can be formally stated as model (30), which is a linear constraint satisfaction problem. This model is feasible if, and only if, the solution is of guillotine-type. By abuse of notation, we assume that the variables and constraints (11) to (16) in model (30) are defined only for indices in , and . Following the nomenclature presented in the comprehensive survey on Benders decomposition by Rahmaniani et al. (2017), we implement a Branch-and-Benders-cut method, as the BPM is solved inside a single search tree. The combinatorial cuts, if any, are added as lazy constraints after checking whether an integer solution is of guillotine-type using the BSP – the reader is referred to the mentioned survey for a complete discussion on the topic. Hereafter, we call the present Benders decomposition by B&BC, which is summarised in Algorithm 1. Notice that when a time limit is considered as stop criterion, the approach is heuristic.
Zonotopic fault detection observer design for Takagi–Sugeno fuzzy systems
Published in International Journal of Systems Science, 2018
Jitao Li, Zhenhua Wang, Yi Shen, Ye Wang
Combining (14) and (25), we have that when fault-free case 0 holds. When fault occurs, the centre of zonotope will deviate, and condition 0 will not be guaranteed. Thus, we develop the following fault detection logic As mentioned in Wang, Zhou, et al. (2017), to implement this logic, the residual zonotope can be characterised in a halfspace representation. Therefore, the zonotopic set contains a sequence of linear constraints, which can be formulated as , where Σ and ϱ denote a matrix and a vector from the halfspace representation of the residual zonotope. Therefore, this logic involves solving a constraint satisfaction problem. If the problem is feasible, then the origin of the coordinate is included in the residual zonotope. Otherwise, it is not included.
Improving harmony search algorithms by using tonal variation: the case of Sudoku and MKP
Published in Connection Science, 2018
Nicolás Rojas-Morales, María-Cristina Riff Rojas
In this work we propose an approach inspired in the tonal variation during jazz music improvisation. Section 4 presents our approach as a general strategy for Harmony Search algorithms. We evaluate our strategy in two combinatorial problems: Sudoku and Multidimensional Knapsack Problem (MKP). We selected these two well-known problems to evaluate our approach in different scenarios, a Constraint Satisfaction Problem and a Constraint Satisfaction Optimisation Problem. Moreover, these problems are NP-hard and have been severally studied. For each problem, we selected an existing base HS algorithm for including our technique: an HS algorithm for solving Sudoku (Geem, 2007) and, the Adaptive Binary Harmony Search (Wang et al., 2013) for the MKP. Section 5 presents the application and evaluation of our approach in solving Sudoku puzzles. Then, the details of the application for the MKP are presented in Section 6. It is important to remark our goal in this work is to improve the search process of an existing HS algorithm, that it has shown to be efficient for solving MKP or Sudoku puzzles, not to define the best algorithm for those problems. Finally, Section 7 gives the conclusions of our work and ideas for future work.