Unmanned aerial vehicles (UAVs) have become increasingly popular in various fields, including precision agriculture, search and rescue, and remote sensing. However, exploring unknown environments remains a significant challenge. This study aims to address this challenge using on-policy reinforcement learning (RL) with proximal policy optimization (PPO) to explore the two-dimensional area of interest with multiple UAVs (multi-rotor and fixed-wing). The UAVs will avoid collision with obstacles and each other and will do the exploration in a distributed manner. The proposed solution includes actor-critic networks that use deep convolutional neural networks (CNN) and long-short-term memory (LSTM) to identify UAVs and areas that have already been covered. Compared to other RL techniques, such as the policy gradient (PG) and the actor-critic asynchronous advantage (A3C), the simulation results demonstrate the superiority of the proposed PPO approach. In addition, the results show that combining LSTM with CNN in critic can improve exploration. Since the proposed exploration has to work in unknown environments, where environments not encountered during training, and we evaluate generalization to such unseen environments. The results showed that the proposed setup can complete the coverage when we have new maps that differ from the trained maps. Finally, we show how tuning hyperparameters may affect overall performance. While the proposed framework is designed for generic UAV types, the main formulation and training are implemented for multi-rotor UAVs; fixed-wing behavior is analyzed separately due to their turning constraints and is not included in the main RL training loop.

Solving combinatorial optimization problems involves satisfying hard constraints while optimizing one or more objectives. Although exact methods always return the optimal solution(s), they are usually associated with an exponential time complexity. Alternatively, approximate methods optimize the computations by trading the solution(s)’ quality in exchange for improved execution time. In this paper, we tackle the Nurse Scheduling Problem (NSP). Solving the NSP involves assigning weekly shifts to nurses in a way that satisfies workload coverage constraints while optimizing both nurses’ preferences and hospital costs. In this context, we introduce implicit and explicit approaches to solve the NSP. In the implicit approach, we employ machine learning methods through historical data (assuming that they are optimal) to learn patterns and simulate new scheduling solutions given the constraints and objectives incorporated in the data. To measure the effectiveness of our implicit approach in capturing the underlying constraints and objectives, we use the Frobenius norm, a metric that calculates the mean error between historical data and the obtained solutions. To make up for the lack of visibility of constraints and objectives in the implicit approach, we propose two alternative explicit methods. In the first one, we model the NSP from ground constraints and objectives using the Constraint Satisfaction Problem (CSP) formalism. The latter is consequently solved using Stochastic Local Search and Branch and Bound augmented with variable/value ordering heuristics and constraint propagation. The second explicit method uses a data-driven approach to acquire constraints and objectives in the form of a CSP.

A common problem that faces many is the tension between doing what aligns with our values and doing what is fiscally best. A system leveraging Multi-Objective Evolutionary Computation, specifically MOEA/D, was proposed to produce highly performant portfolios tailored to an individual’s ESG preferences given a custom survey. The survey, written using the greater context of other risk and ESG relevant surveys, was conducted and used to construct a weighting to normalize a given investor’s own survey responses and allow a single portfolio from the collection of the best portfolios to be matched to that investor. Two potential architectures were considered to build the proposed system: Architecture 1, where the optimization is run for each investor that takes the survey, and Architecture 2 where a multi-objective optimization is run less frequently and the investor is given a portfolio from the Pareto front. This subset consists of all the non-dominated portfolios. The user may have a different experiences, including quality or time waiting, depending on the architecture chosen. The result of the experiment was that both architectures produced high quality portfolios that performed comparably. However, the best portfolio from Architecture 2 was better in most regards than any portfolio from Architecture 1. All Architecture 1 portfolios were more significantly tailored to each of the individuals preferences. For Architecture 2, a limited number of high performing portfolios was generated: as a result, more investors would potentially be recommended the same few portfolios, especially in comparison to Architecture 1.

Internet of Things (IoT) applications have become an integral part of our daily lives. However, due to the rising number of cybercrimes, ensuring cyberspace security has become essential. The security and privacy of IoT applications are fundamental as they are used in critical sectors, like healthcare, transportation systems, and energy production. As a result, many studies are focusing on the security and privacy of the IoT revolution. The need for assessing IoT security risks is increasing. This paper presents a survey and taxonomy of risk management, analysis, and evaluation methods applied to systems involving IoT devices. In particular, the paper reviews and categorizes existing IoT risk management and assessment frameworks, and the different assessments techniques, risk perspectives, and methodologies. The paper concludes with a deep analysis of these frameworks, solutions, and guidelines, and discusses future research directions.

Investments in unmanned aerial vehicles (UAVs) have recently surged in precision agriculture. However, multi-UAV missions can face limitations due to weather conditions, highlighting the need for effective spray coverage. A novel system tailored for spraying in windy conditions to tackle this challenge is proposed. Instead of directly controlling sprayed drops, the location of spraying UAVs based on real-time wind data is adjusted. Our proposed methodology consists of three stages: Firstly, on-policy reinforcement learning (RL) with Proximal Policy Optimization (PPO) is utilized to optimize path planning. In the second stage, another PPO iteration to correct wind drift is employed, leveraging the latest wind data to enhance spray mission efficiency. Lastly, a novel algorithm is introduced to improve efficiency in narrow areas by substituting unmanned aerial vehicles with unmanned ground vehicles. To evaluate the efficiency of the proposed aerial spraying system, we conducted a simulation and reported the corresponding results. • A novel wind effect corrector using RL for precision agriculture spraying efficiency • A hybrid RL model leveraging discrete and continuous outputs to tackle spray drift efficiently • An innovative planning feature combining UGV and UAV strengths to address the wind factor

As Internet of Things (IoT) technology rapidly evolves, the widespread use and diversity of IoT devices present new challenges for device identification (often called finger-printing). Nevertheless, traditional methods for identifying IoT devices face several problems. This paper presents an identification solution capable of detecting the IoT device identities by analyzing the network traffic they generate and machine learning approaches. The solution we propose is tested on three well-known IoT traffic datasets, and showed higher prediction performance in identifying IoT device types. It is also compared against existing solutions and showed far better results, in terms of both prediction accuracy and temporal complexity.

We propose a new hybrid approach, that we call History-driven Particle Swarm Optimization-Simulated Annealing (HdPSO-SA), to improve metaheuristics performance through collaboration and history-driven methods. Collaboration is per-formed using a Self-Adaptive Binary Space Partitioning tree (SA-BSP tree) to partition search space and guide the hybrid frame-work to the most promising sub-region of a given continuous problem to solve. The hybrid framework consists of three phases. In the first phase, the SA - BSP tree is applied in PSO to record essential information, create the landscape of fitness values, and partition the search space during exploration. The second phase consists of a smart controller to learn the SA-BSP maturity condition to balance exploration and exploitation through HdPSO and SA, respectively. The proposed smart controller determines the appropriate step (iteration) for switching from HdPSO to SA. In the third phase, the search space will be limited to only the most promising sub-region. Then, the information of the best solution (fitness value and position) will be given to SA to exploit the limited search space. The proposed HdPSO-SA is compared to several metaheuristics on ten well-known uni-modal and multimodal continuous optimization benchmarks. The results demonstrate the superiority of HdPSO-SA in returning a good quality solution while reducing the execution time.

The Multi-Depot Vehicle Routing Problem (MD-VRP) is a known routing problem whose goal is to minimize the total cost while visiting a set of routes from their respective depots. We consider a particular application of the MDVRP, called the Electricity Technician Dispatch Problem (ETDP), in which we look for optimal tours for technicians to provide services to their customers. To overcome the inherent exponential time cost of this NP-hard problem, we propose a hybrid method structured in two stages. In the first phase, we rely on a clustering algorithm to identify the appropriate set of customers for each technician based on availability, demand, and proximity of the customer's location to each technician's depot. We then consider several approximate and exact methods to get the optimal route for each set of customers. To evaluate the performance of our hybrid solving method, we conducted experiments on a set of problem instances. The results show the effectiveness of our method when Stochastic Local Search (SLS) is used as a search technique.

Risk Assessment for IoT is important for analyzing the risks associated with deploying and using IoT technologies. A risk assessment framework helps organizations identify, assess, and manage the risks of IoT, which can range from data privacy and confidentiality to system integrity, availability, and performance. The significance of risk assessment in medical sectors, particularly in emergency rooms, is more imperative due to the criticality of the service. This paper presents an IoT risk assessment framework for the healthcare environment, in which we have improved upon existing methodologies. The proposed framework dynamically calculates the risk score for different device profiles, considering their population and other parameters, such as network protocols, device heterogeneity, device security updates, device physical security status, device history status, layer history status, and device criticality. We validate our proposed framework by simulating an emergency room environment, considering a variety of devices and parameters. The results show that our framework provides more insight into the overall risk assessment, as it takes into account the number of IoT devices and their relation to a threshold we introduce, which can be tuned by the security expert.

Data clustering has many applications in machine learning, data mining and image processing. K-means is the most popular clustering algorithm due to its efficiency and simplicity of implementation. However, K-means has limitations, such as large feature spaces, which may affect its effectiveness. To improve K-means accuracy, we adopt the Biogeography-Based Optimization (BBO) evolutionary technique to select the most relevant features of datasets. We conducted several experiments to compare our approach with other methods, such as PCA and Particle Swarm Optimization (PSO). The results demonstrate the effectiveness of BBO for feature selection.

A Qualitative Constraint Network (QCN) is a constraint graph representing problems under qualitative temporal or spatial relations. More formally, a QCN includes a set of entities and a list of qualitative constraints defining the possible scenarios between these entities. Qualitative constraints are expressed as disjunctions of binary relations capturing the (incomplete) knowledge between the involved entities. QCNs effectively represent various real-world applications, including scheduling and planning, configuration, and Geographic Information Systems (GIS). It is, however, challenging to elicit, from the user, the QCN representing a given problem. To overcome this difficulty in practice, we propose a new algorithm for learning, through membership queries, a QCN from a non-expert. Membership queries are asked to elicit temporal or spatial relationships between pairs of temporal or spatial entities. To improve the time performance of our learning algorithm, constraint propagation and ordering heuristics are enforced. The goal is to reduce the number of membership queries needed to reach the target QCN. We conducted several experiments on randomly generated temporal and spatial QCN instances to assess the practical effect of constraint propagation and ordering heuristics. The results of the experiments are encouraging and promising.

Most online platforms, applications, and Websites use a massive amount of heterogeneous evolving data. These data must be structured and normalized before integration to improve the search and increase the relevance of results. An ontology can address this critical task by efficiently managing data and providing structured formats through techniques such as the Web Ontology Language (OWL). However, building an ontology can be costly, primarily if conducted manually. In this context, we propose a new methodology for automatically building and learning a multilingual ontology using Arabic as the base language via a corpus collected from Wikipedia. Our proposed methodology relies on Finite-state transducers (FSTs). FSTs are regrouped into a cascade to reduce errors and minimize ambiguity. The produced ontology is extended to English and French and independent language images via a translator we developed using APIs. The rationale for starting with the Arabic corpus to extract terms is that entity linking is more convenient from Arabic to other languages. In addition, many Wikipedia articles in English and French (for instance) do not have associated Arabic articles, but the opposite is true. In addition, dealing with Arabic terms permits us to enrich the Arabic module of the free linguistic platform we use in dictionaries and graphs. To assess the efficiency of our proposed methodology, we conducted performance metrics. The reported results are encouraging and promising.

There are many different recommender systems available in this technological era, each with its own set of features and distinct selling points. We propose a new interactive system for eliciting and learning users’ qualitative preferences. These preferences are modeled as a conditional preference network (CP-net). The CP-net is a known graphical model representing qualitative and conditional preferences in a compact form. Users’ preferences are first captured through a learning method based on membership queries. These preferences are then compiled into a list of conditional preference statements. The CP-net is finally generated from this list. We are also incorporating a collaborative technique so that when a CP-net of a given user is generated, the latter will receive suggestions based on similarities with other users. The suggested solution is interactive, user-friendly, and its performance measurements were tested with actual users. E-commerce, combinatorial optimization, multi-agent planning and agreement, will all benefit from the system’s ability to elicit preferences and make decisions.

Unmanned aerial vehicles (UAVs) have been very successful in many civilian and commercial applications, including disaster relief, search and rescue, precision farming, archaeology, cargo transport, and surveillance. In most of these applications, mapping is a required phase that needs to be performed as an initial step. While mapping has attracted much attention in the last decades, much of the works rely on single drones. In this context, we propose a multiple UAV system for efficient mapping, minimizing mission time and cost. The system includes offline and online planning, and a good balance between both to reduce on-board processing. Offline planning includes area decomposition, take-off location finding, and path planning. Online planning will then be used to react to any unforeseen event that might occur during the plan execution. These incidents include a sudden change in weather conditions, communication loss or drone malfunction, and the presence of a nearby flying obstacle. Each of the main offline and online planning tasks are formalized as a Multi-Objective optimization (MOO) problem where requirements need to be met while objectives have to be optimized. In this regard, we consider several evolutionary techniques to tackle these MOO problems. To assess the performance of these techniques, we conducted several experiments and reported the related results. One finding is that MOEA/D outperforms NSGA2, while the latter requires less processing time.

This work presents a deep averaged reinforcement-learning approach to learn improvement heuristics for route planning. The proposed method is tested on the Traveling Salesman Problem (TSP). While learning improvement heuristics using machine learning models are prosperous, these methods suffer from low generalization and forgetfulness of the agents during the training process. We have applied the stochastic weight averaging method during the training phase to solve these issues, which smothers the training convergence and prevents the forgetting of optimized learned policies, and consequently provides better results. The agent can learn the optimized policy while holding a moving average of the previously learned policies during the training epochs. In order to assess the performance of our proposed approach, we conducted comparative experiments considering other known methods from the literature. The results demonstrate our proposed method’s superiority in training trends and optimization.

SAT problems are fundamental in representing and solving combinatorial applications. Over the past years, many sophisticated SAT solvers have been proposed. Due to the topic’s relevance, a SAT competition is scheduled yearly to promote solving hard SAT instances. There is no unique solver to tackle all SAT problems efficiently. Indeed, some solvers work best for some SAT instances but perform poorly for others. This limitation has been addressed, in the literature, by identifying a pool of solvers that complement each other for efficiently tackling a given set of SAT instances. This pool of solvers is called a portfolio. Several studies have been conducted to find the optimal portfolio maximizing the number of solved SAT instances, minimizing the overall running time, or a trade-off between both. In this context, we present a new approach that first finds the suitable portfolio meeting each of these objectives. Then, the approach predicts the best solver for any new SAT instance. Our approach is based on Greedy search techniques, clustering, and deep learning. More precisely, we investigate two different scenarios. In the first one, our goal is to find the best portfolio capable of solving the largest number of instances within a given time limit. Both the Greedy-based method and clustering are used in this case. The second scenario aims to find the optimal portfolio to minimize the penalized average running time. The latter objective captures a good trade-off between the objective in the first scenario and the overall average running time. In addition to Greedy search and clustering, we consider a variant of the Beam-search technique to address this scenario. To assess the performance of our approach regarding the two scenarios, we conduct multiple experiments on the SAT2021 competition datasets that include SAT instances together with participants’ solvers’ results for each instance. The outcomes from the conducted experiments are encouraging and promising.

We propose an Ontology-Based Information Extraction (OBIE) system to automate the extraction of the criteria and values applied in Land-Use Suitability Analysis (LUSA) from bylaw and regulation documents related to the geographic area of interest. The results obtained by our proposed LUSA OBIE system (land-use suitability criteria and their values) are presented as an ontology populated with instances of the extracted criteria and property values. This latter output ontology is incorporated into a Multi-Criteria Decision-Making (MCDM) model applied for constructing suitability maps for different kinds of land uses. The resulting maps may be the final desired product or can be incorporated into the cellular automata urban modeling and simulation for predicting future urban growth. A case study has been conducted where the output from LUSA OBIE is applied to help produce a suitability map for the City of Regina, Saskatchewan, to assist in the identification of suitable areas for residential development. A set of Saskatchewan bylaw and regulation documents were downloaded and input to the LUSA OBIE system. We accessed the extracted information using both the populated LUSA ontology and the set of annotated documents. In this regard, the LUSA OBIE system was effective in producing a final suitability map.

Mobile devices are used by numerous applications that continuously need computing power to grow. Due to limited resources for complex computing, offloading, a service offered for mobile devices, is commonly used in cloud computing. In Mobile Cloud Computing (MCC), offloading decides where to execute the tasks to efficiently maximize the benefits. Hence, we represent offloading as a Task Scheduling Problem (TSP). This latter is a Multi-Objective Optimization (MOO) problem where the goal is to find the best schedule for processing mobile source tasks, while minimizing both the average processor energy consumption and the average task processing time. Owing to the combinatorial nature of the problem, the TSP in MCC is known as NP-hard. To overcome this difficulty in practice, we adopt meta-heuristic search techniques as they offer a good trade-off between solution quality and scalability. More precisely, we introduce a new optimization approach, that we call Multi-objective Discrete Water Cycle Algorithm (MDWCA), to schedule tasks from mobile source nodes to processor resources in a hybrid MCC architecture, including public cloud, cloudlets, and mobile devices. To evaluate the performance of our proposed approach, we conducted several comparative experiments on many generated TSP instances in MCC. The simulation results show that MDWCA outperforms the state-of-the-art optimization algorithms for several quality metrics.

A Conditional Preference Network (CP-net) is a graphical model widely used to represent qualitative preferences in many real-world applications. Preference elicitation, representation, and reasoning plays an essential role in e-commerce and other applications relying on users’ preferences and desires. However, managing preferences often comes with dealing with hard and soft constraints. While hard constraints are requirements that can either be satisfied or violated, this two-level of satisfiability can be generalized to multiple levels through soft constraints. In this context, our main objective is to manage conditional and qualitative preferences together with hard and soft constraints, within a unique model. The constrained CP-net graphical model has been proposed to manage both conditional preferences and hard constraints. In order to include soft constraints, we extend the underlying constraint network of the constrained CP-net to a Weighted Constraint Satisfaction Problem (WCSP). A WCSP is a CSP where (soft) constraints can be violated or satisfied with associated costs. More precisely, a cost function is associated to each constraint. We call the Weighted Constrained CP-nets (WCCP-net) the new model we propose. Like for CP-nets and Constrained CP-nets, there are two queries to consider for WCCP-nets: outcome optimization and outcome comparison. The outcome optimization query in the case of a constrained CP-net consists in finding the set of feasible solutions that are not dominated by any other solutions. This set is called the Pareto optimal set. In the case of the WCCP-net, this task consists of finding those solutions, from the Pareto optimal set, that maximize the total cost function of the underlying WCSP. This is a NP-hard problem that we tackle using a variant of the branch and bound algorithm that has been proposed to solve the outcome optimization in the case of constrained CP-nets.

There are limited research contributions targeting sentiment analysis in feedback in Arabic gulf dialect, in particular, and the Arabic language in general. Furthermore, the inadequate and limited adoption of classification techniques and natural language processing is noticeable in the sentiment analysis projects addressing the Arabic language. Hence, this paper focuses on analyzing the sentiments in automobile and real estate domains through the application of the state-of-the-art word-embedding model “BERT” and a collection of deep learning models (GRU, LSTM, CNN, CNN-GRU and BiLSTM). The results of classification revealed that combining the BERT with deep learning models have shown efficiency in analyzing sentiments and yielded outstanding results.

A significant amount of water, energy and time are often wasted, before someone gets the desired water temperature in a bathroom or a kitchen. In this paper, we propose a novel electro-mechanical device for mixing the water intelligently, which is effective for saving water, energy and time. The problem that we intend to solve can be seen as a multiobjective optimization problem in which we require to optimize water's flow and temperature. To achieve this task, we consider both the single-objective and the multi-objective optimisation variants of the problem. NSGA II is then used to solve each of these variants. In order to assess the effectiveness of each approach, a case study has been conducted, where controllers are applied to control a dynamic number of users within a house. The results suggest that multi-objective optimization outperforms single-objective optimization, in terms of quality of the returned solutions.

Our study explores offensive and hate speech detection for the Arabic language, as previous studies are minimal. Based on two-class, three-class, and six-class Arabic-Twitter datasets, we develop single and ensemble CNN and BiLSTM classifiers that we train with non-contextual (Fasttext-SkipGram) and contextual (Multilingual Bert and AraBert) word-embedding models. For each hate/offensive classification task, we conduct a battery of experiments to evaluate the performance of single and ensemble classifiers on testing datasets. The average-based ensemble approach was found to be the best performing, as it returned F-scores of 91%, 84%, and 80% for two-class, three-class and six-class prediction tasks, respectively. We also perform an error analysis of the best ensemble model for each task.

The studies addressing the application of machine and deep learning models to analyze the sentiments of Arabic online reviews related to the real-estate and automobile fields are not mature. To fill this gap, this research has focused on classifying three types of sentiments in Arabic real-estate and automobile online reviews, which are negative, positive, and mixed sentiments. The research focused on analyzing the reviews written in both Gulf Cooperation Council (GCC) dialects and modern standard Arabic (MSA). The research also explained the natural language processing strategies that were adopted to prepare the text for classification. The research discussed the details of collecting and annotating the data, preprocessing procedures, and feature selection methods. Following this, the research highlighted the adopted strategies for balancing and splitting the datasets, and it showed the analysis of the classification results for both machine and deep learning models. Finally, the suggestions for future work were provided in this research.

Abstract User's choices involve habitual behavior and genuine decision. Habitual behavior is often expressed using preferences. In a multiattribute case, the Conditional Preference Network (CP‐net) is a graphical model to represent user's conditional ceteris paribus (all else being equal) preference statements. Indeed, the CP‐net induces a strict partial order over the outcomes. By contrast, we argue that genuine decisions are environmentally influenced and introduce the notion of “comfort” to represent this type of choices. In this article, we propose an extension of the CP‐net model that we call the CP‐net with Comfort (CPC‐net) to represent a user's comfort with preferences. Given that preference and comfort might be two conflicting objectives, we define the Pareto optimality of outcomes when achieving outcome optimization with respect to a given CPC‐net. Then, we propose a backtrack search algorithm to find the Pareto optimal outcomes. On the other hand, two outcomes can stand in one of six possible relations with respect to a CPC‐net. The exact relation can be obtained by performing dominance testing in the corresponding CP‐net and comparing the numeric comforts.

Constraint optimization consists of looking for an optimal solution maximizing a given objective function while meeting a set of constraints. In this study, we propose a new algorithm based on mushroom reproduction for solving constraint optimization problems. Our algorithm, that we call Mushroom Reproduction Optimization (MRO), is inspired by the natural reproduction and growth mechanisms of mushrooms. This process includes the discovery of rich areas with good living conditions allowing spores to grow and develop their own colonies. Given that constraint optimization problems often suffer from a high-time computation cost, we thoroughly assess MRO performance on well-known constrained engineering and real-world problems. The experimental results confirm the high performance of MRO, comparing to other known metaheursitcs, in dealing with complex optimization problems.

Many real-world problems such as scheduling, planning and resource allocation can be represented and solved as Constraint Satisfaction Problems (CSPs). The main challenge when tackling these applications is the fact that they occur in an evolving environment. That is, constraints might change over time and this can affect the feasibility of the solution found so far. These changes can be captured with the Dynamic CSP formalism that has been proposed and investigated in the literature. More formally, a Dynamic CSP corresponds to a series of static CSPs, each resulting from a change in the previous one as a result of the evolving world. This change corresponds to either a constraint addition or retraction. In this paper, the focus is on constraint addition (also called constraint restriction) and the goal is to search for the most similar solution satisfying the old constraints and the new ones. In this regard, we propose a new method based on the Firefly algorithm for solving this particular problem with minimal perturbation. To assess the efficiency of new technique, we conducted several experiments on randomly generated dynamic CSP instances. The results achieved clearly demonstrate the efficiency of our algorithm, over other known exact and approximation techniques used in the literature for solving these problems.

The Conditional Preference Network (CP-net) represents user's conditional ceteris paribus (all else being equal) preference statements in a graphical manner. In general, an acyclic CP-net induces a strict partial order over the outcomes. The task of comparing two outcomes (dominance testing) is generally PSPACE-complete, which is a limitation for this intuitive model, especially when representing and solving preference-based constrained optimization problems. In order to overcome this limitation in practice, we propose a divide and conquer algorithm that compares two outcomes according to dominance testing. The algorithm divides the original CP-net into sub CP-nets, and recursively calls itself for each of the sub CP-nets until it reaches to a termination criterion. In the termination criterion, the answer of the dominance query is returned. With a theoretical analysis of the time performance, we demonstrate that the proposed algorithm outperforms the existing methods.

Constraint Solving and Optimization is very relevant in many real world applications including scheduling, planning, configuration, resource allocation and timetabling. Solving a constraint optimization problem consists of finding an assignment of values to variables that optimizes some defined objective functions, subject to a set of constraints imposed on the problem variables. Due to their high dimensional and exponential search spaces, classical methods are unpractical to tackle these problems. An appropriate alternative is to rely on metaheuristics. My thesis is concerned with investigating the applicability of the evolutionary algorithms when dealing with constraint optimization problems. In this regard, we propose two new optimization algorithms namely Mushroom Reproduction Optimization algorithm (MRO) and Focus Group Optimization algorithm (FGO) for solving such problems.

In preference-based constrained optimization problems, helping users by providing the most preferable feasible outcome is crucial. The Lexicographic Preference Tree (LP- tree) and the Conditional Preference Network (CP-net) are two fundamental graphical models to represent and reason about user's qualitative preferences. In this paper, we extend the LP- tree with a set of hard feasibility constraints, and then we propose a recursive backtrack search algorithm that we call Search-LP to find the most preferable feasible outcome for the Constrained LP-tree. Search-LP instantiates the variables with respect to a hierarchical order defined by the LP-tree. Given that the LP-tree represents a total order over the outcomes, Search-LP simply returns the first feasible outcome. We prove that this returned outcome is also preferable to every other feasible outcome. The main advantage of Search-LP is that it does not require dominance testing (the task of comparing two outcomes using preferences) to find the optimal solution(s), while dominance testing is a very expensive operation in the case of Constrained CP-nets.

A Weighted Constraint Satisfaction Problem (WCSP) is a Constraint Satisfaction Problem in which preferences between solutions are considered, meaning that some solutions are more preferred than others and the optimal solution is the one with minimum weight. Such problems are usually dealt with classical complete methods like bucket elimination techniques. However, since these problems are NP-hard the complete methods will require exponential time in addition to a memory space cost. Therefore, approximation methods such as metaheuristics are a good alternative as they are capable of tackling hard to solve combinatorial problems in a very efficient running time. In this regard, we propose a new self-adaptive discrete Firefly algorithm for solving WCSPs. While, like any other approximation algorithm, our method does not guarantee the optimality of the solution returned, the experiments we conducted on randomly generated WCSP instances, demonstrate its ability in returning the optimal solution in a very efficient running time.

Constraint Satisfaction Problems (CSPs) provide an appropriate framework to formulate many real-world applications including scheduling, planning and resource allocation. However, the CSP description can change due to the evolving environment. The latter points to the fact that constraints might be subject to change over time and this can affect the feasibility of the solutions found so far. These changes can be captured with the Dynamic CSP (DCSP) formalism that has been proposed and investigated in the literature. More formally, a DCSP can be seen as a series of static CSPs, each resulting from a restriction or a relaxation of some constraints in the previous CSP constraint set. This paper focuses on constraint restriction (constraint addition) and the goal is to obtain the most similar solution to the previous one that satisfies the old and new constraints. In this regard, we propose a new method based on the Particle Swarm Optimization algorithm to solve these DCSPs with minimal perturbation. To evaluate the efficiency of the proposed method, we conducted extensive experiments on randomly generated DCSP instances generated by the model RB. The results achieved clearly demonstrate the efficiency of the proposed algorithm over other known exact and approximation techniques used in the literature for solving these problems.

Water temperature setting, in houses, leads to a high amount of waste in water and energy. Many circumstances including setting a proper water temperature, sudden drop or increase of temperature leads to the discomfort of the consumer and waste as well. This very large amount of waste can be reduced using cutting edge optimizers. This research proposes a new solution based on multiple objective optimizers (MOO) to set a proper flow rate and water temperature minimizing the used amount of energy by the taps. Note that, there is a large gap in this area when there are multiple users on different taps within a house. The proposed system works with a single or multiple taps. In this scenario, more precisely, the user enters the preferred water temperature as well as the flow rate for each tap. The proposed system then will optimize the used amount of energy and water waste. Meanwhile, the designed system will maintain the temperature with a dynamic number of users. Here, the controllers are part of the heating system to control the amount of used energy.

This paper introduces a new swarm intelligence algorithm called Mother Tree Optimization (MTO) for solving continuous optimization problems. MTO uses a set of cooperating agents that evolve based on the communication between Douglas fir trees mediated by the mycorrhizal fungi network that transfers nutrients between plants of the same or different species. In order to assess the performance of the MTO algorithm, we conducted extensive experiments on its variants, with and without climate change. In this regard, we run several statistical and graphical analyses on the resulting solutions when solving well-known test functions. In the statistical analysis, the average, standard deviation, and minimum number of function evaluations are calculated for various levels of solution quality. In the graphical analysis, qualified run-length distributions are used to show the probability of solving a suite of well-known test functions at different levels of solution quality. The results demonstrate that MTO with climate change is able to reach the global solution for all the problems considered. In addition, this MTO variant generally requires fewer function evaluations than Particle Swarm Optimization and Bacterial Foraging to reach a solution of a given quality.

We introduce a new nature-inspired optimization algorithm namely Mushroom Reproduction Optimization (MRO) inspired and motivated by the reproduction and growth mechanisms of mushrooms in nature. MRO follows the process of discovering rich areas (containing goabod living conditions) by spores to grow and develop their own colonies. We thoroughly assess MRO performance based on numerous unimodal and multimodal benchmark functions as well as engineering problem instances. Moreover, to further investigate on the performance of the proposed MRO algorithm, we conduct a useful statistical evaluation and comparison with well known meta-heuristic algorithms. The experimental results confirm the high performance of MRO in dealing with complex optimization problems by discovering solutions with better quality.

Constraint Satisfaction Problems are regarded as NP-Complete problems which solving them with systematic methods requires exponential time. Firefly algorithm is a nature inspired algorithm which has been successfully applied to different combinatorial problems. This paper presents a new Discrete Firefly Algorithm for Solving Constraint Satisfaction problems (CSPs) and investigates its applicability for dealing with such problems. Performance of the proposed method has been assessed through extensive experiments on CSP instances generated by Model RB which is a standard mean for generating CSPs with different tightness. Results of the experiments in comparison with other methods including classical methods and other metaheuristic methods clearly demonstrate the significant performance of proposed discrete firefly algorithm in dealing with CSPs.

Online auctions created a very attractive environment for dishonest moneymakers who can commit different types of fraud. Shill Bidding (SB) is the most predominant auction fraud and also the most difficult to detect because of its similarity to usual bidding behavior. Based on a newly produced SB dataset, in this study, we devise a fraud classification model that is able to efficiently differentiate between honest and malicious bidders. First, we label the SB data by combining a hierarchical clustering technique and a semi-automated labeling approach. To solve the imbalanced learning problem, we apply several advanced data sampling methods and compare their performance using the SVM model. As a result, we develop an optimal SB classifier that exhibits very satisfactory detection and low misclassification rates.

The Conditional Preference Network (CP-net) graphically represents user's qualitative and conditional preference statements under the ceteris paribus (all else being equal) interpretation. Given that the CP-net induces a partial order over the outcomes, the optimization for a constrained CP-net can have a set of Pareto optimal solutions. The existing algorithms for solving the constrained CP-net require dominance testing between the outcomes, which is a very expensive operation. In this paper, we propose an extension of the CP-net model by eliciting additional relative importance statements between variables in order to have a total order over the outcomes. As a result, the constrained optimization using the proposed model involves a single optimal solution, assuming the underlying CSP is consistent. In this regard, we provide an efficient algorithm to find this optimal solution without the need for dominance testing.

User's choices involve habitual behavior and genuine decisions. Habitual behavior is often represented using preferences. The Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus preference statements. We argue that genuine decisions are environmentally influenced and introduce the notion of "comfort" to represent this type of choices. In this paper, we propose an extension of the CP-net model, that we call the CP-net with Comfort (CPC-net), to represent user's comfort with preferences. A CPC-net has two optimal outcomes, one for preferences and another for comfort. We show that these two outcomes can be obtained in linear time on the number of variables for an acyclic CPC-net. We also evaluate outcome comparison queries with respect to CPC-nets.

The Conditional Preference Network (CP-net) is a graphical tool for representing and reasoning about user's conditional ceteris paribus preference statements. In case the user provides partial preferences, we get a partial CP-net. In this paper, we propose a novel algorithm, that we call Search-Partial-CP, to find the Pareto optimal outcomes with respect to an acyclic partial CP-net and a set of hard constraints. Search-Partial-CP is a backtrack search algorithm that utilizes the topological order of the related Directed Acyclic Graph (DAG) to order the variables, as well as the topological order of the partial preferences to order the values, during the instantiation process. Search-Partial-CP can significantly reduce the search space by pruning every infeasible or dominated outcome. We present and discuss the formal properties of Search-Partial-CP.

Temporal and spatial reasoning is a fundamental task in artificial intelligence and its related areas including scheduling, planning and Geographic Information Systems (GIS). In these applications, we often deal with incomplete and qualitative information. In this regard, the symbolic representation of time and space using Qualitative Constraint Networks (QCNs) is therefore substantial. We propose a new algorithm for learning a QCN from a non expert. The learning process includes different cases where querying the user is an essential task. Here, membership queries are asked in order to elicit temporal or spatial relationships between pairs of temporal or spatial entities. During this acquisition process, constraint propagation through Path Consistency (PC) is performed in order to reduce the number of membership queries needed to reach the target QCN. We use the learning theory machinery to prove some limits on learning path consistent QCNs from queries. The time performances of our algorithm have been experimentally evaluated using different scenarios.

A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Solving a CSP often requires searching for a solution in a large search space. Very often, much of the search efforts are wasted on the part of the search space that does not lead to a solution. Therefore, many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by guiding the search and reducing its size. Variable and value ordering techniques are among the most efficient ones as past experiments have shown that these heuristics can significantly improve the search performance and lead to the solution sooner. One such heuristic works by gathering information during search to guide subsequent decisions when selecting variables. More precisely, this heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. In this paper, we propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts, of each variable attached to this constraint, gathered during constraint propagation. We also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic performs well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly for some difficult problems.

This paper introduces Incremental Dynamic Search (IDS) Solver, a local search based solver, we propose, for solving general finite constraint satisfaction and combinatorial optimization problems. The goal of the IDS Solver is to offer a pluggable approach to Constraint-based models as well as a platform for composing a framework for parallel local search extension, whose functionality is determined by the modelled problem. The aim of the solver is to improve the efficiency, the robustness, and the usability of local-based search algorithms. The proposed solver along with its parallel extension are presented in this paper.

Exploration and exploitation are two strategies used to search the problem space in Evolutionary Algorithms (EAs). To significantly increase the performance of these optimization techniques in terms of the solution optimality is to strike the right balance between exploration and exploitation. Firefly is one of the most favored EAs. In this study, we introduce an entire fuzzy system to tune dynamically the firefly parameters in order to keep the exploration and exploitation in balance in each of the searching steps. A serious concern of EAs is to be stuck in local optimum solutions. The proposed fuzzy controller helps the firefly algorithm to converge to the optimal solution and escape from local optimums. To evaluate the efficiency of the fuzzy-based firefly algorithm, we conduct experiments on a set of high dimensional benchmark functions. The goal here is to compare the new firefly method with the standard firefly and well-known nature-inspired optimization algorithms. The results of the experiments show the superiority of the proposed Fuzzy firefly algorithm over the standard one.

A Probabilistic Conditional Preference network (PCP-net) provides a compact representation of preferences characterized with uncertainty. We propose to enrich the expressive power of the PCP-net by adding constraints between some of the variables. We call this new model, the Constrained PCP-net (CPCP-net). We study the key preference reasoning task with the proposed CPCP-net which consists in finding the most probable optimal outcome i.e. the most probable outcome that best represents the preferences while satisfying all the constraints. In this regard, a variant of the Branch and Bound algorithm has been proposed and experimentally evaluated on CPCP-net instances, randomly generated based on the RB-model. The results of these experiments show that the new proposed solving method is capable of returning the most probable optimal outcome in a reasonable time.

Multi-Attribute Reverse Auctions (MARAs) are considered an excellent way to buy and sell efficiently. However, eliciting the buyer's requirements and preferences as well as determining the winner, are both challenging tasks. In this paper, we propose a multi-round and semi-sealed MARA auction system, capable of determining the winner given a set of user's preferences and requirements. This system is capable of managing qualitative, quantitative and conditional preferences together with constraints. For that, we use the constrained Tradeoffs-enhanced Conditional Preference Networks (constrained TCP-nets) graphical model for representing constraints as well as qualitative and conditional preferences, and Multi-Attribute Utility Theory (MAUT) for dealing with quantitative preferences. Determining the winners of the auction will then be achieved using the backtrack search algorithm we use for solving constrained TCP-nets.

Despite some success of Genetic Algorithms (GAs) when tackling Constraint Satisfaction Problems (CSPs), they generally suffer from poor crossover operators. In order to overcome this limitation in practice, we propose a novel crossover specifically designed for solving CSPs including Temporal CSPs (TCSPs). Together with a variable ordering heuristic and an integration into a parallel architecture, this proposed crossover enables the solving of large and hard problem instances as demonstrated by the experimental tests conducted on randomly generated CSPs and TCSPs based on the model RB. We will indeed demonstrate, through these tests, that our proposed method is superior to the known GA-based techniques for CSPs. In addition, we will show that we are able to compete with the efficient MAC-based Abscon 109 solver for random problem instances as well as those instances taken from Lecoutre’s CSP library. Finally, we conducted additional tests on very large consistent and over constrained CSPs and TCSPs instances in order to show the ability of our method to deal with constraint problems in real time. This corresponds to solving the CSP or the TCSP by giving a solution with a quality (number of solved constraints) depending on the time allocated for computation.

We propose a Multi-Phase Hybrid Metaheuristics approach for solving the Exam Timetabling Problem (ETP). This approach is defined with three phases: pre-processing phase, construction phase and enhancement phase. The pre-processing phase relies on our variable ordering heuristic as well as a form of transitive closure for discovering implicit constraints. The construction phase uses a variant of the Tabu Search with conflicts dictionary. The enhancement phase includes Hill Climbing (HC), Simulated Annealing (SA) and our updated version of the extended “Great Deluge” algorithm. In order to evaluate the performance of the different phases of our proposed approach, we conducted several experiments on instances taken from ITC 2007 benchmarking datasets. The results are very promising and competitive with the well known ETP solvers.

A Constraint Satisfaction Problem (CSP) is a framework used for modeling and solving constrained problems. Tree-search algorithms like backtracking try to construct a solution to a CSP by selecting the variables of the problem one after another. The order in which these algorithm select the variables potentially have significant impact on the search performance. Various heuristics have been proposed for choosing good variable ordering. Many powerful variable ordering heuristics weigh the constraints first and then utilize the weights for selecting good order of the variables. Constraint weighting are basically employed to identify global bottlenecks in a CSP. In this paper, we propose a new approach for learning weights for the constraints using competitive coevolutionary Genetic Algorithm (GA). Weights learned by the coevolutionary GA later help to make better choices for the first few variables in a search. In the competitive coevolutionary GA, constraints and candidate solutions for a CSP evolve together through an inverse fitness interaction process. We have conducted experiments on several random, quasi-random and patterned instances to measure the efficiency of the proposed approach. The results and analysis show that the proposed approach is good at learning weights to distinguish the hard constraints for quasi-random instances and forced satisfiable random instances generated with the Model RB. For other type of instances, RNDI (RaNDom Information gathering) still seems to be the best approach as our experiments show.

Dealing with spatial knowledge requires the consistency of spatial information. This consistency is usually enforced by constraint satisfaction techniques including constraint propagation through arc and path consistency. While theses techniques often assume that spatial information are static, this is in general not the case in the real world. Our goal is to propose an approach to maintain the consistency of spatial knowledge in a dynamic environment. To our best knowledge no work in spatial reasoning has addressed this issue. In this paper we use a spatial ontology called Space Ontology to describe both objects and spatial relations namely topological and distance relations between these objects. Based on a dynamic path consistency algorithm, our proposed method maintains the consistency of spatial information after adding new instances of topological relations described by Space Ontology of a given environment. In order to evaluate the performance of our dynamic path consistency method, we conducted several tests on instantiations of Space Ontology in addition to randomly generated spatial constraint problems. The results of these tests demonstrate the efficiency of our method to deal with large size problems in a dynamic environment.

Graph coloring problems (GCPs) are constraint optimization problems with various applications including scheduling, time tabling, and frequency allocation. The GCP consists in finding the minimum number of colors for coloring the graph vertices such that adjacent vertices have distinct colors. We propose a parallel approach based on Hierarchical Parallel Genetic Algorithms (HPGAs) to solve the GCP. We also propose a new extension to PGA, that is Genetic Modification (GM) operator designed for solving constraint optimization problems by taking advantage of the properties between variables and their relations. Our proposed GM for solving the GCP is based on a novel Variable Ordering Algorithm (VOA). In order to evaluate the performance of our new approach, we have conducted several experiments on GCP instances taken from the well known DIMACS website. The results show that the proposed approach has a high performance in time and quality of the solution returned in solving graph coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.

A Constraint Satisfaction Problem (CSP) is a powerful framework for representing and solving constraint problems. When solving a CSP using a backtrack search method, one important factor that reduces the size of the search space drastically is the order in which variables and values are examined. Many heuristics for static and dynamic variable ordering have been proposed and the most popular and powerful are those that gather information about the failures during the constraint propagation phase, in the form of constraint weights. These later heuristics are called conflict driven heuristics. In this paper, we propose two of these heuristics respectively based on Hill Climbing (HC) and Ant Colony Optimization (ACO) for weighing constraints. In addition, we propose two new value ordering techniques, respectively based on HC and ACO, that rank the values based on their ability to satisfy the constraints attached to their corresponding variables. Several experiments were conducted on various types of problems including random, quasi random and patterned problems. The results show that the proposed variable ordering heuristics, are successful especially in the case of hard random problems. Also, when using the proposed value and variable ordering together, we can improve the performance particularly in the case of random problems.

Simulation of complex Lotos specifications is not always efficient due to the space explosion problem of their corresponding transition systems. To overcome this difficulty in practice, we present in this paper a novel approach which integrates constraint propagation techniques into the Lotos specifications. These solving techniques are used to reduce the size of the search space before and during the search for a solution to a given combinatorial problem under constraints. In order to do that, we first tackle the challenging task of describing combinatorial problems in Lotos using the Constraint Satisfaction Problem (CSP) framework. In this regard, we provide two generic Lotos templates for describing CSPs and temporal CSPs (CSPs involving temporal constraints). To evaluate the time performance of the framework we propose, we have conducted several experimental tests on instances of the N-Queens, the machine scheduling and randomly generated CSPs. The results of these experiments are promising and demonstrate the efficiency of Lotos simulation when CSP techniques are integrated.

The quadratic assignment problem (QAP) is a well known important combinatorial problem. Indeed, many real world applications such as backboard wiring, typewriter keyboard design and scheduling can be formulated as QAPs. Recently, tackling this problem has been addressed by ant colony optimization (ACO) Algorithms. To do so, ACOs, and more precisely min-max ant system (MMAS) Algorithms, are usually combined with two kinds of stochastic local search (SLS) methods: the 2-opt local search and the tabu local search. We talk then respectively about MMAS2optand MMAStabu. In this paper, we propose an improvement of these two methods according to the properties of ACO and QAP. In the case of MMAS2opt, a new random walk strategy is used to avoid a quick stagnation into local optima. Moreover, a forward-looking strategy is proposed to explore the neighborhood more thoroughly. In the case of MMAStabu, a random walk strategy is also employed to avoid getting stuck at local optima. In order to show the merits of our proposed techniques we have conducted experimental tests comparing respectively MMAS2optand MMAStabuwith and without the improvements. The results demonstrate that the improved local method, have better performance in terms of the quality of the solution returned than the original ones. Moreover, we also noticed that the improved methods outperform each other for different classes of problems.

In this paper we discuss the applicability of evolutionary algorithms enhanced by heuristics and adaptive fitness computation for solving the temporal constraint satisfaction problem (TCSP). This latter problem is an extension of the well known CSP, through our TemPro model, in order to handle numeric and symbolic temporal information. We test the evolutionary algorithms on randomly generated TCSPs and analyze and compare the performance of the algorithms tested, based on different measures. The results show that heuristics do not promise better performance for solving TCSPs. The basic genetic algorithm (GA) and microgenetic iterative descendant (MGID) are the most effective ones. We also noticed that MGID is more efficient than basic GA for easier problems.

We propose a probabilistic extension of Allen's interval algebra for managing uncertain temporal relations. Although previous work on various uncertain forms of quantitative and qualitative temporal networks have been proposed in the literature, little has been addressed to the most obvious type of uncertainty, namely the probabilistic one. More precisely, our model adapts the probabilistic constraint satisfaction problem (CSP) framework in order to handle uncertain symbolic temporal constraints. In a probabilistic CSP, each constraint C is given a probability of its existence in the real world. There is thus more than one CSP to solve as opposed to the traditional CSP where no such uncertainties exist. In a probabilistic temporal CSP, since we use the interval algebra where a constraint is a disjunction of Allen primitives, the probability is assigned to each of these Allen primitives rather than to the temporal constraint itself. This means that a probabilistic temporal CSP involves many possible temporal CSPs, each with a probability of its existence. Solving a probabilistic temporal CSP consists of finding a scenario that has the highest probability to be the solution for the real world. This is an optimization problem that we solve using a branch and bound algorithm we propose and involving constraint propagation. Experimental study conducted on randomly generated temporal problems demonstrates the efficiency in time of our solving method.

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique, whereas the approximation methods rely on stochastic local search (SLS) and genetic algorithms (GAs). A comprehensive empirical study, conducted on a wide range of randomly generated consistent SAT instances, demonstrates the efficiency in time of the approximation methods over the branch and bound algorithm. However, these approximation methods do not guarantee the completeness of the solution returned. We show that a method we propose that uses nonsystematic search in a limited form together with branch and bound has the best compromise, in practice, between time and the success ratio (percentage of instances completely solved).

The existing ant colony optimization (ACO) algorithms for the quadratic assignment problem (QAP) are often combined with two kinds of stochastic local search (SLS) methods: the 2-opt local search and the tabu local search. In this paper, these two SLS methods are respectively improved according to the properties of ACO and QAP. For the 2-opt local search, a new random walk strategy is used to avoid a quick stagnation into local optima. Moreover, a forward-looking strategy is proposed to explore the neighborhood more thoroughly. In the case of tabu local search, a random walk strategy is also employed to avoid getting stuck at local optima. Experimental evaluation of the ACO algorithms combined with the improved local search proposed in this paper are conducted on problems from the well known QAPLIB library. The results demonstrate that each ACO algorithm, combined with its respective improved local search, has a better performance, in terms of the quality of the solution returned, than the ACO algorithm with the original local search techniques. Moreover, we also noticed that the improved methods outperform each other for different classes of problems

Preferences in temporal problems are common but significant in many real world applications. In this paper, we extend our temporal reasoning framework, managing numeric and symbolic information, in order to handle preferences. Unlike the existing models managing single temporal preferences, ours supports four types of preferences, namely: numeric and symbolic temporal preferences, composite preferences and conditional preferences. This offers more expressive power in representing a wide variety of temporal constraint problems. The preferences are considered here as a set of soft constraints using a c-semiring structure with combination and projection operators. Solving temporal constraint problems with preferences consists of finding a solution satisfying all the temporal constraints while optimizing the preference values. This is handled by a variant of the branch and bound algorithm, we propose in this paper, and where constraint propagation is used to improve the time efficiency. Preliminary tests, we conducted on randomly generated temporal constraint problems with preferences, favor the forward checking principle as a constraint propagation strategy

Lotos is the ISO formal specification language for describing and verifying concurrent and distributed systems. The simulation or execution of complex Lotos specifications is, however, not always efficient due to the space explosion problem of their corresponding transition systems. To overcome this difficulty in practice, we propose in this paper the integration of constraint propagation techniques into the Lotos simulation. Indeed, constraint propagation techniques are very powerful for solving hard discrete combinatorial problems. Experimental tests, we have conducted on the simulation of several specified combinatorial problems, demonstrate the efficiency of integrating constraint propagation into Lotos simulation

A well known approach to managing the numeric and the symbolic aspects of time is to view them as constraint satisfaction problems (CSPs). Our aim is to extend the temporal CSP formalism in order to include activity constraints and composite variables. Indeed, in many real life applications the set of variables involved by the temporal constraint problem to solve is not known in advance. More precisely, while some temporal variables (called events) are available in the initial problem, others are added dynamically to the problem during the resolution process via activity constraints and composite variables. Activity constraints allow some variables to be activated (added to the problem) when activity conditions are true. Composite variables are defined on finite domains of events. We propose in this paper two methods based respectively on constraint propagation and stochastic local search (SLS) for solving temporal constraint problems with activity constraints and composite variables. We call these problems conditional and composite temporal constraint satisfaction problems (CCTCSPs). Experimental study we conducted on randomly generated CCTCSPs demonstrates the efficiency of our exact method based on constraint propagation in the case of middle constrained and over constrained problems while the SLS based method is the technique of choice for under constrained problems and also in case we want to trade search time for the quality of the solution returned (number of solved constraints)

One of the main challenges when designing constraint based systems in general and those involving temporal constraints in particular, is the ability to deal with conditional constraints and composite variables. Indeed, in this particular case the set of variables involved by the constraint problem to be solved is not known in advance. More precisely, while some variables (called initial variables) are available in the initial problem, others are added dynamically to the problem during the resolution process via activity constraints and composite variables. Activity constraints allow some variables to be activated (added to the problem) when activity conditions are true. Composite variables are variables whose values are the possible variables each composite variable can take. We propose a method based on constraint propagation for solving efficiently constraint problems involving numeric and symbolic temporal constraints, composite variables and activity constraints. We call these latter problems conditional and composite temporal constraint satisfaction problems (CCTCSPs). Experimental evaluation conducted on randomly generated CCTCSPs demonstrates the efficiency of our method to solve these problems especially when using the forward check strategy during the search.

Many applications such as planning, scheduling and natural language processing involve managing both symbolic and numeric aspects of time. We have developed a temporal model, TemPro, based on interval algebra, to express such applications in terms of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen (1983) to handle numeric information. To solve a temporal constraint problem represented by TemPro, we have developed a method using constraint propagation at the numeric and symbolic levels. In order to deal with real time applications or those applications where a complete solution cannot be obtained, we have modified the propagation techniques so that they will be able to solve temporal problems by giving a solution with a quality depending on the time allocated for computation.