Search

International audience; Synchronizing heterogeneous processes remains a difficult issue in Scheduling area. Related ILP models are in trouble, because of large gaps induced by rational relaxation. We choose here to deal with it while emulating the interactions which take place between the various players of such heterogeneous processes, and propose a pipe-line decomposition of a dynamic programming process designed in order to schedule energy production and energy consumption

Synchronizing heterogeneous processes remains a difficult issue in Scheduling area. Related ILP models are in trouble. So we propose here a pipe-line collaboration of a dynamic programming process for energy production and consumption scheduling.

The emergence of H2 energy produced through photolysis makes appear a new generation of local energy players, which are at the same time producers and consumers. This raises the question of synchronizing H2 production, which deeply depends on the time, and its consumption through some transportation activity. We deal here with this issue, in the context of an experimental H2 production platform, through dynamic programming augmented with ad hoc filtering devices.

Given a connected undirected graph $$G=(V, E)$$ , a subset W of nodes of G is a weakly connected independent set if W is an independent set and the partial graph $$(V, \delta (W))$$ is connected, where $$\delta (W)$$ is the set of edges with only one endnode in W. This article proposes several distinct results about the weakly connected independent sets of a graph obtained by corona or join operations: the complete description of the wcis polytope for a corona or a join of two graphs of which we know the wcis polytopes or the maximal independent set polytopes, and the consequences of these graph operations on the minimum weight weakly connected independent set problem (MWWCISP). A class of graphs is also inductively defined from the connected bipartite graphs, the cycles and the strongly chordal graphs, for which the MWWCISP is polynomially solvable. This work is a direct continuation of the article (Bendali et al. in Discrete Optim 22:87–110, 2016) where a similar theorem about complete description of the wcis polytope has been given for 1-sum operation.

Let G=(V,E) be a connected graph. An independent set WV is said to be weakly connected if the spanning subgraph GW=(V,(W)) is connected where (W) is the set of edges with exactly one end in W. We present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristic separation procedures. Finally, we develop a Branch-and-Cut algorithm and test it on two classes of graphs.

Modeling topologies in Wireless Sensor Networks principally uses domination theory in graphs. Indeed, many dominating structures have been proposed as virtual backbones for wireless networks. In this paper, we study a dominating set that we call Weakly Connected Independent Set (wcis ). Given an undirected connected graph G = (V,E ), we say that an independent set S in G is weakly connected if the spanning subgraph (V, [ S,V \ S ]) is connected, where [ S,V \ S ] is the set of edges having exactly one end in S . The minimum weakly independent connected set problem consists in determining a wcis of minimum size in G . First, we discuss some complexity and approximation results for that problem. Then we propose an implicit enumeration algorithm which computes a minimum wcis in a graph with n vertices with a running time O ∗ (1.4655n ) and polynomial space. Processing results are given that show that our enumeration program solves the mwcis problem for graphs whose number of vertices is less than 120.

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût. Nous proposons une heuristique pour ce problème auxiliaire et discutons divers cas particuliers. We present here a Flow/Multicommodity Flow model for Transportation and Production Planning problems. We deal with this model through Lagrangean Relaxation and Hierarchical Decomposition techniques, which involve the resolution of a specific flow with least integral cost problem. We propose and test several heuristic schemes for this specific problem and conclude by discussing some particular situations.

In this paper, we study a composition (decomposition) technique for the triangle-free subgraph polytope in graphs which are decomposable by means of 3-sums satisfying some property. If a graph G decomposes into two graphs G1 and G2, we show that the triangle-free subgraph polytope of G can be described from two linear systems related to G1 and G2. This gives a way to characterize this polytope on graphs that can be recursively decomposed. This also gives a procedure to derive new facets for this polytope. We also show that, if the systems associated with G1 and G2 are TDI, then the system characterizing the polytope for G is TDI. This generalizes previous results in R. Euler and A.R. Mahjoub (Journal of Comb. Theory series B, vol. 53, no. 2, pp. 235–259, 1991) and A.R. Mahjoub (Discrete Applied Math., vol. 62, pp. 209–219, 1995).

Given a graph G which decomposes into two graphs G1 and G2 by means of a 3-sum, we derive a linear system of inequalities that defines the triangle free subgraph polytope from two systems related to G1 and G2. This yields a method to characterize this polytope for graphs that decompose this way. A procedure is given to describe new facets for this polytope. We also show that this system is TDI if the systems for the pieces are also TDI. Some applications of these results will be discussed.

International audience; Wireless Sensor Networks (WSN) have been studied in several contexts. There are many challenges involving WSN design such as the energy resources optimization, the robustness and the network coverage. We address here the problem of energy-efficient topology design. A well-designed dynamic topology and efficient routing algorithms may allow a large reduction on the energy consumption, which is one of the main concerns of WSN nodes. In this work, we propose to model the problem of clustering a WSN topology as a variation of the independent dominating set optimization problem. Then, we describe two heuristics to generate a WSN topology and two ways to evaluate the energy consumption. Computational results are presented for instances with up to 500 nodes.

Wireless sensor networks have been studied in several contexts because of their large number of applications. There are many challenges involving such networks as the energy resources optimization, the robustness and the network coverage. We address here the problem of energy efficient topology design. A well-designed dynamic topology and an efficient routing algorithm allow to reduce energy consumption, which is the main constraint of wireless sensor node. In this work, we propose to model the problem as a variation of the independent set optimization problem, for the clustering the wireless sensor nodes. We also propose a local search procedure to improve the whole network topology and a specific evaluation procedure.

In this paper we describe a Branch-and-Cut algorithm for the k-edge connected subgraph problem. This problem has applications in the design of survivable telecommunication networks. We introduce a new family of valid inequalities for the associated polytope. We give sufficient conditions for these inequalities to be facet defining and devise separation heuristics to separate them. We present further classes of valid inequalities and also discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we develop a Branch-and-Cut algorithm and present some computational results.

In this paper, we consider the independent dominating set polytope. We give a complete linear description of that polytope when the graph is reduced to a cycle. This description uses a general class of valid inequalities introduced in [T.M. Contenza, Some results on the dominating set polytope, Ph.D. Dissertation, University of Kentucky, 2000]. We devise a polynomial time separation algorithm for these inequalities. As a consequence, we obtain a polynomial time cutting plane algorithm for the minimum (maximum) independent dominating set problem on a cycle. We also introduce a lifting operation called twin operation, and discuss some polyhedral consequences. In particular, we show that the above results can be extended to a more general class of graphs.

Nous modelisons ici plusieurs problemes de Transport et de Gestion de Flux a l'aide d'un flot entier et d'un multiflot fractionnaire couples par une contrainte de capacite. Pour le probleme ainsi obtenu, nous proposons differents schemas de resolution par relaxation et decomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entiere superieure doit minimiser un certain cout, et qui requierent la mise en œuvre d'un processus d'agregation. Nous en deduisons diverses heuristiques que nous testons.

A cooperative game is defined as a set of players and a cost function. The distribution of the whole cost between the players can be done using the core concept, that is the set of all undominated cost allocations which prevent players from grouping. In this paper we study a game whose cost function comes from the optimal solution of a linear integer covering problem. We give necessary and sufficient conditions for the core to be nonempty and characterize its allocations using linear programming duality. We also discuss a special allocation, called the nucleolus. We characterize that allocation and show that it can be computed in polynomial time using a column generation method.