Explore chapters and articles related to this topic
Mixed Integer Optimization
Published in Timothy R. Anderson, Optimization Modeling Using R, 2023
Another approach to integer programming is full enumeration which means listing out all possible solutions and then determining if that solution is feasible and if so, what the objective function value is. Alas, this can result in a combinatorial explosion. For example, if a problem has 1000 non-negative integer variables each of which can range from zero to nine, full enumeration would require listing 101000 possible solutions. This is far larger than the number of grains of sand on Earth ( 1019) or the number of stars in the universe ( 1019). In fact, this is much larger than the number of atoms in the universe ( 1080). Needless to say explicit enumeration for large problems is not an option.
Bayesian networks with imprecise datasets: Application to oscillating water column
Published in Stein Haugen, Anne Barros, Coen van Gulijk, Trond Kongsvik, Jan Erik Vinnem, Safety and Reliability – Safe Societies in a Changing World, 2018
H.D. Estrada-Lugo, E. Patelli, M. de Angelis, Daniel D. Raj
The implementation of imprecise data in Bayesian networks is a very necessary tool in engineering. However, the methods currently available are computationally expensive. Most importantly, when systems with a large number of variables are studied, the algorithms may suffer combinatorial explosion. Adaptive line sampling will be further studied to deal with bounded failure probabilities. In addition to that, random set theory (combined with Subset Simulation to improve calculation speed) appears as a good option to the limitations of the current tool, since the latter method is specially useful for small probability cases and good performance in both low- and high-dimensional spaces as well as in nonlinear limit functions.
Higher-Order Models in Computer Vision
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
Pushmeet Kohli, Carsten Rother
As mentioned before, any higher-order function can be converted to a pairwise one by introducing additional auxiliary random variables [5, 24]. This enables the use of conventional inference algorithms such as belief propagation, tree-reweighted message passing, and graph cuts for such models. However, this approach suffers from the problem of combinatorial explosion. Specifically, a naive transformation can result in an exponential number of auxiliary variables (in the size of the corresponding clique) even for higher-order potentials with special structure [38, 37, 26].
GAASP: Genetic Algorithm-Based Atomistic Sampling Protocol for High-Entropy Materials
Published in Materials and Manufacturing Processes, 2023
There has been a significant interest in the area of high-entropy and medium-entropy materials due to their interesting properties, such as high strength and toughness at liquid helium[1], as well as liquid nitrogen temperature,[2] high corrosion resistance,[3] strength retention at high temperature,[4] high catalytic activity,[5] etc. Medium- and high-entropy materials containing three or more elements, respectively, exhibit these exciting properties but also present a unique challenge in designing such materials with high computational complexity. The compositional complexity in such materials leads to a combinatorial explosion, and a traditional hit-and-trial approach for designing such material might not be a feasible approach. Such a problem becomes further challenging with the advent of non-concentrated compositionally complex alloys, where certain elements may be added in a dilute amount to concentrated complex alloys. Dragoe et al. presented a simple calculation to demonstrate the combinatorial explosion through a scenario, in which if five elements are chosen from a palette of 26 elements with 1% increment, one can have 2,822,599,802,880 combinations, while if six elements are chosen with similar increments in the composition, the possibilities increase to a value of 902,943,619,878,430.[6]
Modelling and feedback control for a class of Petri Nets with shared resources subject to strict time constraints using Max-plus algebra
Published in International Journal of Systems Science, 2021
Sofiane Aberkane, Redouane Kara, Saïd Amari
Integration of information and communication technologies in the different fields of engineering leads to more complexity, in particular the real-time aspect of these systems. This aspect is presented by specifications (constraints) which can be presented in various forms (prohibited states, time intervals, validity period, etc.). In timed discrete event systems, operations are processed within a specific time frame, and sometimes they have to complete before a predetermined date, violating this time constraint will lead to failures and sometimes severe consequences. In many applications it is important to explicitly consider time. For example, one seeks to evaluate the production per unit of time of a workshop, or the average time taken to transmit information over a network. Time is often taken into account through the duration of the tasks that are carried out, for example the machining time of a workpiece in a workshop, the execution time of a job in a workshop, the execution time of a processor, the time taken to transmit a message along a communication line. The durations are sometimes physical constraints, which are necessarily satisfied. In the literature, several approaches have been proposed for the control of DESs under different constraints and specifications. Many authors have discussed the construction of controllers to ensure that critical time requirements for system behaviour are met. The contribution in Brandin and Wonham (1994) for control of automata is augmented with timing features by use of Ostroff's semantics for timed transition models. They extended the framework of Ramadge and Wonham's theory (Ramadge & Wonham, 1987) and defined the concept of controllability for timed discrete event systems. These approaches are interesting and relevant, but the problem of combinatorial explosion limits their field of application. To overcome this problem, often encountered when we are dealing with automata models, methods based on the use of timed event graphs and dioid algebra are proposed in Amari et al. (2012), Atto et al. (2011), Houssin et al. (2012), Tebani et al. (2017) and Maia et al. (2011).
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
As the output of MCSNN reveals that can be solved, the conceptual design solutions are generated by clustering the embedding of principle structure nodes. According to the edge connections between principle structure nodes and design constraints nodes, the similar principle structures are merged into a group and listed in Table 5. For example, permanent magnet AC synchronous motor (s13) and reluctance type AC synchronous motor (s14) are merged into a group because they have the same edge connections in the adjacent matrix M. Moreover, the group number ‘G0' indicates the principle structures that violate on-factor correspondence constraints and cannot be used to generate conceptual design solutions. Since the embedding of principle structure nodes is sparse, the PCA is applied firstly to reduce the embedding into 8 dimensions. Subsequently, the k-means algorithm is utilised to cluster the principle structure nodes into different categories. In order to ensure that all the behaviours can be achieved in each category, k = 2 is determined and the clustering result during the iteration of message passing is shown in Figure 8. Although the clustering results in the early iteration times (i.e. iteration time 50) are well separated, they cannot be regarded as design solutions. This is because the output of MCSNN in this iteration time shows that cannot be solved. Therefore, the combination of principle structures in each cluster cannot satisfy all design constraints. With the increasing times of message passing, MCSNN learns more information from design space. After adequate message passing times (600 in this study), design space is sufficiently searched by MCSNN, then feasible design solutions can be founded by the k-means algorithm. The clustering result is that: and . The merged principle structure group in is relevant to the same behaviour, e.g. is relevant to the behaviour ‘meshing effect'. Designers can choose any one of them to achieve this behaviour. According to each cluster, Boolean variable ‘1' is assigned to the principle structures in this cluster while Boolean variable ‘0' is assigned to the other groups. The proposition logic is used to verify the assignment of Boolean variables. If , the conceptual design solution can be generated by combining principle structures assigned with the Boolean variable ‘1'. Therefore, design space can be significantly narrowed down, and the combinatorial explosion is avoided to a great extent. The conceptual design solutions for the traction system are shown in Table 6.