The Experts below are selected from a list of 5499 Experts worldwide ranked by ideXlab platform

Ali Ridha Mahjoub - One of the best experts on this subject based on the ideXlab platform.

  • a branch and cut algorithm for the k edge Connected Subgraph problem
    Networks, 2010
    Co-Authors: F. Bendali, Ali Ridha Mahjoub, Ibrahima Diarrassouba, Didi M Biha, J. Mailfert
    Abstract:

    In this article, we consider the k-edge Connected Subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and 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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

  • on the steiner 2 edge Connected Subgraph polytope
    Rairo-operations Research, 2008
    Co-Authors: Ali Ridha Mahjoub, Pierre Pesneau
    Abstract:

    In this paper, we study the Steiner 2-edge Connected Subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge Connected Subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge Connected Subgraph problem in that class of graphs.

  • critical extreme points of the 2 edge Connected Subgraph polytope
    2006
    Co-Authors: Jean Fonlupt, Ali Ridha Mahjoub
    Abstract:

    In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge Connected spanning Subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if X is a non-integer minimal extreme point of P(G), then G and X can be reduced, by means of some reduction operations, to a graph G' and an extreme point X of P(G') where G' and X'satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge Connected graphs, the graphs for which the polytope P(G) is integral.

  • the k edge Connected Subgraph problem i polytopes and critical extreme points
    Linear Algebra and its Applications, 2004
    Co-Authors: Didi M Biha, Ali Ridha Mahjoub
    Abstract:

    Abstract In this paper we consider the linear relaxation of the k -edge Connected Subgraph polytope, P ( G , k ), given by the trivial and the so-called cut inequalities. We introduce an ordering on the fractional extreme points of P ( G , k ) and describe some structural properties of the minimal extreme points with respect to that ordering. Using this we give sufficient conditions for P ( G , k ) to be integral.

  • steiner k edge Connected Subgraph polyhedra
    Journal of Combinatorial Optimization, 2000
    Co-Authors: Didi M Biha, Ali Ridha Mahjoub
    Abstract:

    In this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Baiou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505–514, 1997 for the case k = 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are allowed.

Carla P Gomes - One of the best experts on this subject based on the ideXlab platform.

  • wildlife corridors as a Connected Subgraph problem
    Journal of Environmental Economics and Management, 2012
    Co-Authors: Jon M Conrad, Carla P Gomes, Willemjan Van Hoeve, Ashish Sabharwal, Jordan F Suter
    Abstract:

    Wildlife corridors connect areas of biological significance to mitigate the negative ecological impacts of habitat fragmentation. In this article we formalize the optimal corridor design as a Connected Subgraph problem, which maximizes the amount of suitable habitat in a fully Connected parcel network linking core habitat areas, subject to a constraint on the funds available for land acquisition. To solve this challenging computational problem, we propose a hybrid approach that combines graph algorithms with Mixed Integer Programming-based optimization. We apply this technique to the design of corridors for grizzly bears in the U.S. Northern Rockies, illustrating the underlying computational complexities by varying the granularity of the parcels available for acquisition. The approach that is introduced is general and can be applied to other species or other similar problems, such as those occurring in social networks.

  • solving Connected Subgraph problems in wildlife conservation
    Integration of AI and OR Techniques in Constraint Programming, 2010
    Co-Authors: Bistra Dilkina, Carla P Gomes
    Abstract:

    We investigate mathematical formulations and solution techniques for a variant of the Connected Subgraph Problem. Given a Connected graph with costs and profits associated with the nodes, the goal is to find a Connected Subgraph that contains a subset of distinguished vertices. In this work we focus on the budget-constrained version, where we maximize the total profit of the nodes in the Subgraph subject to a budget constraint on the total cost. We propose several mixed-integer formulations for enforcing the Subgraph connectivity requirement, which plays a key role in the combinatorial structure of the problem. We show that a new formulation based on subtour elimination constraints is more effective at capturing the combinatorial structure of the problem, providing significant advantages over the previously considered encoding which was based on a single commodity flow. We test our formulations on synthetic instances as well as on real-world instances of an important problem in environmental conservation concerning the design of wildlife corridors. Our encoding results in a much tighter LP relaxation, and more importantly, it results in finding better integer feasible solutions as well as much better upper bounds on the objective (often proving optimality or within less than 1% of optimality), both when considering the synthetic instances as well as the real-world wildlife corridor instances.

  • CPAIOR - Solving Connected Subgraph problems in wildlife conservation
    Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2010
    Co-Authors: Bistra Dilkina, Carla P Gomes
    Abstract:

    We investigate mathematical formulations and solution techniques for a variant of the Connected Subgraph Problem. Given a Connected graph with costs and profits associated with the nodes, the goal is to find a Connected Subgraph that contains a subset of distinguished vertices. In this work we focus on the budget-constrained version, where we maximize the total profit of the nodes in the Subgraph subject to a budget constraint on the total cost. We propose several mixed-integer formulations for enforcing the Subgraph connectivity requirement, which plays a key role in the combinatorial structure of the problem. We show that a new formulation based on subtour elimination constraints is more effective at capturing the combinatorial structure of the problem, providing significant advantages over the previously considered encoding which was based on a single commodity flow. We test our formulations on synthetic instances as well as on real-world instances of an important problem in environmental conservation concerning the design of wildlife corridors. Our encoding results in a much tighter LP relaxation, and more importantly, it results in finding better integer feasible solutions as well as much better upper bounds on the objective (often proving optimality or within less than 1% of optimality), both when considering the synthetic instances as well as the real-world wildlife corridor instances.

Stephen J Maher - One of the best experts on this subject based on the ideXlab platform.

  • reduction techniques for the prize collecting steiner tree problem and the maximum weight Connected Subgraph problem
    Networks, 2019
    Co-Authors: Stephen J Maher, Daniel Rehfeldt, Thorsten Koch
    Abstract:

    The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this article we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize‐collecting Steiner tree problem, the rooted prize‐collecting Steiner tree problem and the maximum‐weight Connected Subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90% of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state‐of‐the‐art Steiner problem solver SCIP‐Jack.

  • the unrooted set covering Connected Subgraph problem differentiating between hiv envelope sequences
    European Journal of Operational Research, 2016
    Co-Authors: Stephen J Maher, John M Murray
    Abstract:

    This paper presents a novel application of operations research techniques to the analysis of HIV Env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of Env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest Connected Subgraph of the constructed covariance network that exhibits a set covering property. The integer program developed for this analysis, labelled the unrooted set covering Connected Subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders’ decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders’ decomposition solution approach and the effectiveness of these techniques and heuristic approaches for solving the USCCSP.

Valentin Pollet - One of the best experts on this subject based on the ideXlab platform.

  • the balanced Connected Subgraph problem complexity results in bounded degree and bounded diameter graphs
    Conference on Combinatorial Optimization and Applications, 2019
    Co-Authors: Benoit Darties, Rodolphe Giroudeau, Jeanclaude Konig, Valentin Pollet
    Abstract:

    We present new complexity results for the Balanced Connected Subgraph (BCS) problem. Given a graph whose vertices are colored either blue or red, find the largest Connected Subgraph containing as many red vertices as blue vertices. We establish the NP-completeness of the decision variant of this problem in bounded-diameter and bounded-degree graphs: bipartite graphs of diameter four, graphs of diameter three and bipartite cubic graphs. BCS being polynomially solvable in graphs of diameter two and maximum degree two, our results close some of the existing gaps in the complexity landscape.

  • COCOA - The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs
    Combinatorial Optimization and Applications, 2019
    Co-Authors: Benoit Darties, Rodolphe Giroudeau, Jeanclaude Konig, Valentin Pollet
    Abstract:

    We present new complexity results for the Balanced Connected Subgraph (BCS) problem. Given a graph whose vertices are colored either blue or red, find the largest Connected Subgraph containing as many red vertices as blue vertices. We establish the NP-completeness of the decision variant of this problem in bounded-diameter and bounded-degree graphs: bipartite graphs of diameter four, graphs of diameter three and bipartite cubic graphs. BCS being polynomially solvable in graphs of diameter two and maximum degree two, our results close some of the existing gaps in the complexity landscape.

Thorsten Koch - One of the best experts on this subject based on the ideXlab platform.