International audience

ABSTRACT The survivable variant of the Ring Star Problem aims at building a network such that when a hub fails, the Ring Star structure is preserved thanks to backup arcs and edges. In this article, we propose a resilient variant of the Ring Star Problem named 1‐R‐RSP in which the failure of a node in a given subset of so‐called uncertain nodes triggers two corrective operations to repair a ring star structure. The first operation repairs the ring, and the second operation reconnects the star. For a given real positive input parameter , which represents the total duration of breakdowns during the considered time horizon, the objective is to minimize the classical costs of the Ring Star Problem plus the costs incurred by the corrective operations when the hub associated with the largest fixing cost fails during units of time. We model this problem as an integer linear program (ILP), which is also addressed with a Branch‐and‐bins‐cut algorithm. We then perform a sensitivity analysis to help the decision maker understand the impact of the parameter .

Abstract The Ring Star Problem consists in selecting a subset of nodes called hubs including the depot and linking them with a cycle, the remaining nodes being connected to exactly one hub, at minimum cost. We study a survivable variant of the Ring Star Problem where at most one node in a given subset of so‐called uncertain nodes can fail if selected as a hub. We model this problem as an Integer Linear Program (ILP), that is also addressed with a Branch‐and‐Benders‐cut decomposition. The Benders subproblem is turned into a linear program with the addition of new inequalities that are shown to be facet‐defining, and several enhancements to both the ILP and Branch‐and‐Benders‐cut algorithm are also presented. Both approaches are compared on the basis of extensive numerical experiments that bring the following conclusions. First, the survivable variant is shown to be much harder than the original Ring Star Problem, and the extra cost induced by survivability is significant. Second, the ILP formulation tends to produce tighter lower bounds but memory issues are frequent for large instances. Finally, the Branch‐and‐Benders‐cut algorithm returns feasible solutions that are often of better quality than those produced by ILP, and is less frequently subjected to memory issues on the considered set of instances.

International audience

This article studies the effect of partial coverage to extend the lifetime of wireless sensor networks and introduces a hybrid exact solution strategy that efficiently maximizes network lifetime. We consider a set of sensors used to provide coverage of discrete targets and transfer the information to the sink node via multi‐hop wireless communication. An active sensor has one of the two roles: it is a source when it senses and transfers data; it is a relay if it only transfers data. Network lifetime is extended through the use of covers representing sensors role allocation and network topology. A hybrid column generation is used to identify the optimal operation schedules and roles allocation that maximize network lifetime. A constraint programming strategy is provided to identify profitable network configurations leading to extend network lifetime and to prove optimality of the solutions found. Moreover, an evolutionary algorithm is proposed to boost up the solution process and accelerate convergence. Extensive computational results demonstrate the effectiveness of the proposed approach. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(1), 34–53 2016

This paper presents an algebraic approach to functional verification of gate-level, integer arithmetic circuits. It is based on extracting a unique bit-level polynomial function computed by the circuit directly from its gate-level implementation. The method can be used to verify the arithmetic function computed by the circuit against its known specification, or to extract an arithmetic function implemented by the circuit. Experiments were performed on arithmetic circuits synthesized and mapped onto standard cells using ABC system. The results demonstrate scalability of the method to large arithmetic circuits, such as multipliers, multiply-accumulate, and other elements of arithmetic datapaths with up to 512-bit operands and over 2 million gates. The results show that our approach wins over the state-of-the-art SAT/satisfiability modulo theory solvers by several orders of magnitude of CPU time. The procedure has linear runtime and memory complexity, measured by the number of logic gates.

The paper presents an algebraic approach to functional verification of gate-level, integer arithmetic circuits. It is based on extracting a unique bit-level polynomial function computed by the circuit directly from its gate-level implementation. The method can be used to verify the arithmetic function computed by the circuit against its known specification, or to extract the arithmetic function implemented by the circuit. Experiments were performed on arithmetic circuits synthesized and mapped onto standard cells using ABC system. The results demonstrate scalability of the method to large arithmetic circuits, such as multipliers, multiply-accumulate, and other elements of arithmetic datapaths with up to 512-bit operands and over 2 Million gates. The procedure has linear runtime and memory complexity, measured by the number of logic gates.

Abstract This article addresses three problems that arise in coverage scheduling for wireless sensor networks subject to bandwidth constraints. The first problem focuses on minimizing the total breach under a lifetime constraint, where a breach occurs when some targets are not covered by active sensors. The second problem aims at maximizing the network lifetime under a breach constraint. Finally, the problem of computing the possible trade‐offs between breach and lifetime offered by the sensor network is also addressed. An exact approach based on a column generation algorithm is proposed for solving these problems, and a heuristic is also derived from it and briefly presented. The use of a genetic algorithm within the column generation scheme appears to significantly decrease computation time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

The purpose of this paper is the implementation of control loop for extended reconfigurable systems. In the context of “first time right” approach, it's necessary to propose design method which takes into account reconfigurable feature of the system as well as its sociotechnical aspect. After a state of the art of industrial uses we define a design approach based on tools from model driven engineering. This method considers a job oriented model for input and allows the simultaneous implementation of the control code and of the man machine interfaces.

This paper presents an innovative way to build flexible benchmarks based on micro-architecture independent characteristics. The proposed approach enables the testing and stressing of processors in order to reflect the real nature of applications and give meaningful information to the designers. The use of a limited number of basic blocks hand-coded in assembly, wisely chosen and arranged, enables to copy the behaviour of proprietary applications. An integer linear programming approach is used to find the number of basic blocks and their iterations. An enumerative method is used to build the basic blocks base. Our approach is used to generate synthetic test benches representative of the MediaBench applications suite. Real measurements conducted on an Intel processor show interesting and promising results, which will be discussed in details in this paper.

This paper proposes a methodology for automatic control generation of conveying systems. Its purpose is to automate the development of discrete control programs in order to reduce costs. It is based on components to model controlled conveying systems. A component is a reusable element that includes several views including partial models. It is formalized referring to the notion of operations. Four views are delineated in this paper: operating part view, constraints view, topological view and control view. The control model of the workshop is built on these views. The procedure uses these partial models and refers to model transformation to provide an easy way to obtain source code compatible with the IEC 61131-3 standard. Tools allowing to implement the methodology are also presented, along with some applications.

This paper deals with the reconfiguration of flexible manufacturing systems. It presents a methodology that addresses the whole reaction loop toward failures. The major key point is the component notion that provides an easy way to get several models used in the monitoring supervision and control modules. A component is a reusable element that is composed of several views including partial models. It is formalized referring to the notion of operations and described using UML standard. Three views are delineated in this paper: monitoring view, supervision view and control view. Workshop models are built from these three views. The computation and the interactions of these models enable to get a relevant reaction for the reconfiguration process. Works concerning the detection, identification of down operations, the decision of a new configuration and the updating of control are presented.