International audience

Boolean Networks (BNs) are widely used as a modeling formalism in several domains, notably systems biology and computer science. A fundamental problem in BN analysis is the enumeration of trap spaces, which are hypercubes in the state space that cannot be escaped once entered. Several methods have been proposed for enumerating trap spaces, however they often suffer from scalability and efficiency issues, particularly for large and complex models. To our knowledge, the most efficient and recent methods for the trap space enumeration all rely on Answer Set Programming (ASP), which has been widely applied to the analysis of BNs. Motivated by these considerations, our work proposes a new method for enumerating trap spaces in BNs using ASP. We evaluate the method on a mix of 250+ real-world and 400+ randomly generated BNs, showing that it enables analysis of models beyond the capabilities of existing tools (namely pyboolnet, mpbn, trappist, and trapmvn).

Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research is to enumerate all fixed points, which has been proven crucial in the analysis and control of biological systems. Indeed, in that field, BNs originated from the pioneering work of R. Thomas on gene regulation and from the start were characterized by their asymptotic behavior: complex attractors and fixed points. The former being notably more difficult to compute exactly, and specific to certain biological systems, the computation of stable states (fixed points) has been the standard way to analyze those BNs for years. However, with the increase in model size and complexity of Boolean update functions, the existing methods for this problem show their limitations. To our knowledge, the most efficient state-of-the-art methods for the fixed point enumeration problem rely on Answer Set Programming (ASP). Motivated by these facts, in this work we propose two new efficient ASP-based methods to solve this problem. We evaluate them on both real-world and pseudo-random models, showing that they vastly outperform four state-of-the-art methods as well as can handle very large and complex models.

MOTIVATION: Boolean networks are simple but efficient mathematical formalism for modelling complex biological systems. However, having only two levels of activation is sometimes not enough to fully capture the dynamics of real-world biological systems. Hence, the need for multi-valued networks (MVNs), a generalization of Boolean networks. Despite the importance of MVNs for modelling biological systems, only limited progress has been made on developing theories, analysis methods, and tools that can support them. In particular, the recent use of trap spaces in Boolean networks made a great impact on the field of systems biology, but there has been no similar concept defined and studied for MVNs to date. RESULTS: In this work, we generalize the concept of trap spaces in Boolean networks to that in MVNs. We then develop the theory and the analysis methods for trap spaces in MVNs. In particular, we implement all proposed methods in a Python package called trapmvn. Not only showing the applicability of our approach via a realistic case study, we also evaluate the time efficiency of the method on a large collection of real-world models. The experimental results confirm the time efficiency, which we believe enables more accurate analysis on larger and more complex multi-valued models. AVAILABILITY AND IMPLEMENTATION: Source code and data are freely available at https://github.com/giang-trinh/trap-mvn.

Abstract Radio network planning is a core problem in cellular networks. It includes coverage, capacity and parameter planning. This paper investigates the Antenna Positioning Problem (APP) which is a main task in cellular networks planning. The aim is to find a trade‐off between maximizing coverage and minimizing costs. APP is the task of selecting a subset of potential locations where installing the base stations to cover the entire area. In theory, the APP is NP‐hard. To solve it in practice, we propose a new meta‐heuristic called Evolutionary Iterated Local Search that merges the local search method and some evolutionary operations of crossover and mutation. The proposed method is implemented and evaluated on realistic, synthetic and random instances of the problem of different sizes. The numerical results and the comparison with the state‐of‐the‐art show that the proposed method succeeds in finding good results for the considered problem.

Summary To classify high‐dimensional data, feature selection plays a key role to eliminate irrelevant attributes and enhance the classification accuracy and efficiency. Since feature selection is an NP‐Hard problem, many heuristics and metaheuristics have been used to tackle in practice this problem. In this article, we propose a novel approach that consists in a probabilistic selection hyper‐heuristic called the synergy Thompson sampling hyper‐heuristic. The Thompson sampling selection strategy is a probabilistic reinforcement learning mechanism to assess the behavior of the low‐level heuristics, and to predict which one will be more efficient at each point during the search process. The proposed hyper‐heuristic is combined with a 1 nearest neighbor classifier from the Weka framework. It aims to find the best subset of features that maximizes the classification accuracy rate. Experimental results show a good performance in favor of the proposed method when comparing with other existing approaches.

Reasoning about gene networks is essential from various perspectives, such as predicting side effects of drugs or explaining unusual cellular behavior. Because of the massive size of these gene networks, a biologist can only work on a small part of the network. Thus, there is an essential requirement for logical representations and automated reasoning on such networks to help biologists to understand genetic interactions. However, the knowledge about gene networks is always incomplete and sometimes not accurate. Hence, knowledge has to be continuously revised and extended. In this work, we propose an approach based on non-monotonic logic programming, and the framework of Answer Set Programming(ASP), to represent and handle gene networks. We show how to model reasoning, predict events, and explain observations in gene networks. Finally, we show how our approach is applied to represent and resolve the DNA double-strand breaks, which is one of the most severe genomic lesions.

In biology, Boolean networks are conventionally used to represent and simulate gene regulatory networks. The attractors are the subject of special attention in analyzing the dynamics of a Boolean network. They correspond to stable states and stable cycles, which play a crucial role in biological systems. In this work, we study a new representation of the dynamics of Boolean networks that are based on a new semantics used in answer set programming (ASP). Our work is based on the enu- meration of all the attractors of asynchronous Boolean networks having interaction graphs which are circuits. We show that the used semantics allows to design a new approach for computing exhaustively both the stable cycles and the stable states of such networks. The enumeration of all the attractors and the distinction between both types of attractors is a significant step to better understand some critical aspects of biology. We applied and evaluated the proposed approach on randomly generated Boolean networks and the obtained results highlight the benefits of this approach, and match with some conjectured results in biology.

This work concerns the consideration of human resource constraints in the single machine scheduling problem of both production and flexible periodic maintenance activities. We assume that a maintenance activity requires the intervention of a human resource to be treated. These human resources are characterized by a competence level and availabilities considered as strong constraints allowing or not the maintenance activities' planning. To solve this NP-hard scheduling problem, we propose a guided local search metaheuristic that embeds a post-optimization process in order to minimize both production and maintenance delays. We implemented and experimented the proposed method on two series of benchmarks. The first one focuses on small size instances. The results show that the quality of the solutions obtained by the proposed method compared to an exact one is good, and even it reaches the optimal solution in some cases. In the second one, we applied the method on large instances to show its advantages and efficiency.

In this work, we introduce a new method for searching stable models of logical programs. This method is based on a relatively new semantics that has not been exploited yet. This semantics captures and extends that one of the stable models (Gelfond et al., 1988) and offers a new alternative to implement ASP solvers. The proposed method performs a DPLL enumerative process that is adapted to Answer Set Programming (ASP) framework according to the used semantics. This method has the advantage to use a Horn clause representation having the same size as the input logic program has constant spatial complexity. It avoids the workload induced by the loop management from which suffer most of the ASP solvers based on the Clark completion. Moreover, the enumeration is done on a restricted set of literals called the strong back-door (STB) of the considered logic program. This reduces the algorithm time complexity which is in theory a function of the size of the STB set. We also introduced new inference rules that the method uses to prune its search tree and hence reduces its size in practice. We implemented the proposed method and applied it to enumerate the stable models of some combinatorial problems. The method is compared to other known systems and the obtained results show that our approach is a good alternative for designing ASP solvers.

In this paper, we study a new scheduling problem that considers both production and flexible preventive maintenance on a single machine where the human resource constraints (the availability and the competence) are taken into account. The objective function involves both the tardiness and the earliness resulting from production and maintenance tasks. We propose a mathematical formulation of the studied problem that is expressed in the constraint programming (CP) paradigm as a set of linear constraints. This CP modeling had been implemented in ILOG OPL language and the exact method Cplex is applied on it to compute the optimal solutions of relatively small instances of the problem. Further, a heuristic algorithm is provided to deal with lager instances of the problem. Computational experiments demonstrate that the proposed heuristic performs well and is able to find good solutions to instances up to 700 jobs in a reasonable CPU time.

The problem of positioning antennas in cellular networks is a known problem in the field of telecommunications. It consists of selecting from a set of candidate sites, the best locations to install the base stations in order to maximize the network coverage while minimizing the number of the used stations. In theory, the problem is NP-hard. To solve it in practice, we propose in this work the adaptation of two metaheuristics based on the local search that are the Iterated Local Search (ILS) and the Breakout Local Search (BLS) and provide a new algorithm inspired from both the ILS and the BLS algorithms. The latter is based on a local search process and a perturbation in the exploration of the search space. It is distinguished by its mechanism of reinitialization of the search and by its way of generating a new starting solution. To validate our approach, we have implemented, tested and compared these algorithms to several other methods on a real instance of the problem. The experimental results obtained show that the proposed approach improves the performance of these methods in most of the cases.

This research focuses on the problem of scheduling jobs on a single machine that requires flexible maintenance under human resource constraints. A fuzzy genetic algorithm that integrates production, maintenance, human resource availability and competence constraints is developed. This algorithm uses fuzzy logic to deal with uncertainties. Experiments show that the consideration of human resource constraints and uncertainties in the integrated and proactive scheduling allows proposing more realistic and applicable solutions.

Many research works had been done in order to define a semantics for logic programs. Most of these semantics are iterated fixed point semantics. The main idea is the canonical model approach which is a declarative semantics for logic programs that can be defined by selecting for each program one of its canonical models. The notion of canonical models of a logic program is what it is called the stable models. The stable models of a logic program are the minimal Her brand models of its "reduct" programs. The work that we describe in this paper is theoretical, we introduce a new semantics for logic programs that is different from the known fixed point semantics. In our approach, logic programs are expressed as CNF formulas (sets of clauses) of a propositional logic for which we define a notion of extension. We prove in this semantics, that each consistent CNF formula admits at least an extension and for each given stable model of a logic program there exists an extension of its corresponding CNF formula which logically entails it. On the other hand, we show that some of the extensions do not entail any stable model, in this case, we define a simple condition called a discrimination condition which allows to recognize such extensions. These extensions could be very important, but are not captured by the stable models semantics. Our approach, extends the stable model semantics in this sense. Following the new semantics, we give a full characterization of the stable models of a logic program by means of the extensions of its CNF encoding verifying the simple discrimination condition, and provide a procedure which can be used to compute such extensions from which we deduce the stable models and eventually the extra-stable models of the given logic program.

The satisfiability problem (SAT) is shown to be the first decision NP-complete problem. It is central in complexity theory. A CNF formula usually contains an interesting number of symmetries. That is, the formula remains invariant under some variable permutations. Such permutations are the symmetries of the formula, their elimination can lead to make a short proof for a satisfiability proof procedure. On other hand, many improvements had been done in SAT solving, Conflict-Driven Clause Learning (CDCL) SAT solvers are now able to solve great size and industrial SAT instances efficiently. The main theoretical key behind these modern solvers is, they use lazy data structures, a restart policy and perform clause learning at each fail end point in the search tree. Although symmetry and clause learning are shown to be powerful principles for SAT solving, but their combination, as far as we now, is not investigated. In this paper, we will show how symmetry can be used to improve clause learning in CDCL SAT solvers. We implemented the symmetry clause learning approach on the MiniSat solver and experimented it on several SAT instances. We compared both MiniSat with and without symmetry and the results obtained are very promising and show that clause learning by symmetry is profitable for CDCL SAT solvers.

Most of the local search methods for the satisfiability problem deal with a complete and inconsistent truth assignment of the problem variables, and try to repair it by switching the truth value of some variables until reaching a model. We propose a new local search algorithm which works on partial truth assignments, but always consistent, instead of complete and inconsistent ones. This method attempts to extend a current partial assignment as a complete method would do. However, instead of backtracking when a conflict arises, it frees at least one variable involved in each falsified clause to restore consistency. Thus, the explored neighborhood is always consistent whereas it is not the case for classical local search algorithms. Experimental results show the competitiveness of our method towards other local search methods.

Information often comes from different sources and merging these sources usually leads to the apparition of inconsistencies. Fusion is the operation consists in restoring the consistency of the merged information by changing a minimum of the initial information. In this paper, we are interested in linear constraints prioritized fusion in the framework of simple temporal problems (STPs). Priority expresses a preference relation between linear constraints and can represent either confidence or quality degrees of the constraints, or the reliability of their sources. We propose a local fusion method which we experiment on random prioritized STP instances.

Finite model and counter model generation is a potential alternative in automated theorem proving. In this paper, we introduce a system called FMSET which generates finite structures representing models of equational theories. FMSET performs a satisf