Search

Your search keyword '"Mahjoub, Ali Ridha"' showing total 128 results
Start Over Author "Mahjoub, Ali Ridha"

Refine your results

more »

more »

more »

more »
128 results on '"Mahjoub, Ali Ridha"'

2. Non-Robust Strong Knapsack Cuts for Capacitated Location-Routing and Related Problems

Author

Liguori, Pedro, Mahjoub, Ali Ridha, Marques, Guillaume, Sadykov, Ruslan, Uchoa, Eduardo, Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation (EDGE), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Universidade Federal Fluminense [Rio de Janeiro] (UFF), Inria Centre at the University of Bordeaux, and Plafrim

Subjects
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

The Capacitated Location-Routing Problem consists in, given a set of locations and a set of customers, determining in which locations one should install depots with limited capacity, and for each depot, design a number of routes to supply customer demands. We provide a formulation that includes depot variables, edge variables, assignment variables, and an exponential number of route variables, together with some new families of valid inequalities, leading to a branch-cut-and-price algorithm. The main original methodological contribution of the article is the Route Load Knapsack Cuts, a family of non-robust cuts, defined over the route variables, devised to strengthen the depot capacity constraints. We explore the monotonicity and the superadditivity properties of those cuts to adapt the labeling algorithm, used in the pricing, for handling the additional dual variables efficiently. Computational experiments show that several Capacitated Location-Routing previously unsolved instances from the literature can now be solved to optimality. Additional experiments with hard instances of the Vehicle Routing Problem with Capacitated Multiple Depots and with instances of the Vehicle Routing Problem with Time Windows and Shifts indicate that the newly proposed cuts are also effective for those problems.

Published
2022

6. Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem

Author

Diarrassouba, Ibrahima, Hadhbi, Youssouf, Mahjoub, Ali Ridha, Sciencesconf.org, CCSD, Laboratoire de Mathématiques Appliquées du Havre (LMAH), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and INSA Lyon

Subjects
breaking, separation, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Mathematics::History and Overview, primal heuristic, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], valid inequalities, and, branch, Computer Science::Computers and Society, polyhedron, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Physics::Popular Physics, spectrum assignment, routing, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], facet, Network design, cut, integer programming, symmetry
Abstract

International audience; Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem.

Published
2022

7. On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part II

Author

Diarrassouba, Ibrahima, Hadhbi, Youssouf, Mahjoub, Ali Ridha, Laboratoire de Mathématiques Appliquées du Havre (LMAH), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)

Subjects
valid inequality, separation, spectrum assignment, branch-and-cut, dimension, Optical networks, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], constrained-routing, facet, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], integer linear programming, polyhedron
Abstract

The constrained-routing and spectrum assignment (C-RSA) problem is a key issue when dimensioning and designing an optical network. Given an optical network G and a multiset of traffic demand K, it aims at determining for each traffic demand k ∈ K a path and an interval of contiguous slots while satisfying technological constraints and optimizing some linear objective function(s). In this paper, we introduce an integer linear programming formulation based on the so-called cut formulation for the C-RSA problem. We describe several valid inequalities for the associated polytope, and further give necessary and sufficient conditions under which these inequalities are facet defining. Based on these results, we develop a branch-and-cut algorithm to solve the problem.

Published
2021

8. Valid Inequalities and Branch-and-Cut-and-Price Algorithm for the Constrained-Routing and Spectrum Assignment Problem

Author

Diarrassouba, Ibrahima, Hadhbi, Youssouf, Mahjoub, Ali Ridha, Laboratoire de Mathématiques Appliquées du Havre (LMAH), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and HADHBI, Youssouf

Subjects
ILP, separation, column generation, interval graph, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], intersection graph, network design, constrained-routing, greedy-algorithm, branch-and-cut-and-price algorithm, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Spectrally flexible optical network, pre-processing, valid inequality, metaheuristics, conflict-graph, dynamic programming algorithm, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], branching rules, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], spectrum assignment, branch-and-price algorithm, perfect graph, heuristic, complexity, threshold graph, primal heuristic
Abstract

In this work, we focus on a complex variant of the so-called Routing and Spectrum Assignment problem (RSA), namely the Constrained-Routing and Spectrum Assignment (C-RSA). The C-RSA problem is a key issue when dimensioning and managing a new generation of optical networks, called spectrally flexible optical networks. It is well known to be NP-hard and can be stated as follows. Consider a spectrally flexible optical network as an undirected, loopless, and connected graph G, and an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K. The C-RSA consists of assigning for each traffic demand k ∈ K a path in G and an interval of contiguous frequency slots in S subject to technological constraints while optimizing some linear objective function(s). The main aim of our work is to introduce a new extended integer linear programming based on the so-called path formulation for the C-RSA. This formulation has an exponential number of variables. A column generation algorithm is then used to solve its linear relaxation. To do so, we investigate the structure and properties of the associated pricing problem. We further identify several classes of valid inequalities for the associated polytope and devise their separation procedures. Based on this, we devise Branch-and-Price (B&P) and Branchand-Cut-and-Price (B&C&P) algorithms to solve the problem. We give at the end a detailed behavior study of these algorithms.

Published
2021

9. Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem

Author

Diarrassouba, Ibrahima, Hadhbi, Youssouf, Mahjoub, Ali Ridha, Laboratoire de Mathématiques Appliquées du Havre (LMAH), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and HADHBI, Youssouf

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

The Constrained-Routing and Spectrum Assignment (C-RSA) problem arises in the dimensioning and management of a next-generation of optical transport networks, called Spectrally Flexible Optical Networks (SFONs). The C-RSA can be stated as follows. Given an SFONs as a graph G, and an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K, it aims at determining for each demand k ∈ K a path in G and an interval of contiguous slots in S while satisfying technological constraints, and optimizing some linear objective function(s). To the best of our knowledge, a cuttingplane-based approach has not been yet considered for the problem. For that, the main aim of our work is to introduce an integer linear programming formulation and provide several classes of valid inequalities for the associated polyhedron. We further discuss their separation problems. Using the polyhedral results and the separation procedures, we devise a Branchand-Cut algorithm to solve the problem. We also present some computational results and show the effectiveness of our approach using real and some realistic network topologies.

Published
2021

12. Combinatorial Optimization - 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4-6, 2020, Revised Selected PapersLecture Notes in Computer Science 12176, Springer

Author

Baïou, Mourad, Gendron, Bernard, Gunluk, Oktay, Mahjoub, Ali Ridha, and Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2020

20. Randomized Contractions for Multiobjective Minimum Cuts

Author

Aissi, Hassene, Mahjoub, Ali Ridha, Ravi, Ramamoorthi, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Computer Science Department - Carnegie Mellon University, University of Pittsburgh (PITT), and Pennsylvania Commonwealth System of Higher Education (PCSHE)-Pennsylvania Commonwealth System of Higher Education (PCSHE)

Subjects
minimum cut, graph algorithms, 000 Computer science, knowledge, general works, randomized algorithms, Computer Science, multiobjective optimization, [INFO]Computer Science [cs], budget constraints, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We show that Karger's randomized contraction method (SODA 93) can be adapted to multiobjective global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms. For global minimum cuts with a single edge-budget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an n-node graph improving upon the best-known randomized algorithm with running time tilde{O}(n^4) due to Armon and Zwick (Algorithmica 2006). Our analysis also gives a new upper bound of O(n^3) for the number of optimal solutions for a single edge-budget min cut problem. For the case of (k-1) edge-budget constraints, the extension of our algorithm saves a logarithmic factor from the best-known randomized running time of O(n^{2k} log^3 n). A main feature of our algorithms is to adaptively choose, at each step, the appropriate cost function used in the random selection of edges to be contracted. For the global min cut problem with a constant number of node budgets, we give a randomized algorithm with running time tilde{O}(n^2), improving the current best determinisitic running time of O(n^3) due to Goemans and Soto (SIAM Journal on Discrete Mathematics 2013). Our method also shows that the total number of distinct optimal solutions is bounded by O(n^2) as in the case of global min-cuts. Our algorithm extends to the node-budget constrained global min cut problem excluding a given sink with the same running time and bound on number of optimal solutions, again improving upon the best-known running time by a factor of O(n). For node-budget constrained problems, our improvements arise from incorporating the idea of merging any infeasible super-nodes that arise during the random contraction process. In contrast to cuts excluding a sink, we note that the node-cardinality constrained min-cut problem containing a given source is strongly NP-hard using a reduction from graph bisection.

Published
2017
Full Text
View/download PDF

21. Randomized Contractions for Multiobjective Minimum Cuts

Author

Hassene Aissi and Ali Ridha Mahjoub and R. Ravi, Aissi, Hassene, Mahjoub, Ali Ridha, Ravi, R., Hassene Aissi and Ali Ridha Mahjoub and R. Ravi, Aissi, Hassene, Mahjoub, Ali Ridha, and Ravi, R.

Abstract

We show that Karger's randomized contraction method (SODA 93) can be adapted to multiobjective global minimum cut problems with a constant number of edge or node budget constraints to give efficient algorithms. For global minimum cuts with a single edge-budget constraint, our extension of the randomized contraction method has running time tilde{O}(n^3) in an n-node graph improving upon the best-known randomized algorithm with running time tilde{O}(n^4) due to Armon and Zwick (Algorithmica 2006). Our analysis also gives a new upper bound of O(n^3) for the number of optimal solutions for a single edge-budget min cut problem. For the case of (k-1) edge-budget constraints, the extension of our algorithm saves a logarithmic factor from the best-known randomized running time of O(n^{2k} log^3 n). A main feature of our algorithms is to adaptively choose, at each step, the appropriate cost function used in the random selection of edges to be contracted. For the global min cut problem with a constant number of node budgets, we give a randomized algorithm with running time tilde{O}(n^2), improving the current best determinisitic running time of O(n^3) due to Goemans and Soto (SIAM Journal on Discrete Mathematics 2013). Our method also shows that the total number of distinct optimal solutions is bounded by O(n^2) as in the case of global min-cuts. Our algorithm extends to the node-budget constrained global min cut problem excluding a given sink with the same running time and bound on number of optimal solutions, again improving upon the best-known running time by a factor of O(n). For node-budget constrained problems, our improvements arise from incorporating the idea of merging any infeasible super-nodes that arise during the random contraction process. In contrast to cuts excluding a sink, we note that the node-cardinality constrained min-cut problem containing a given source is strongly NP-hard using a reduction from graph bisection.

Published
2017
Full Text
View/download PDF

24. Book reviews

Author

Pallaschke, D., Mahjoub, Ali Ridha, Faigle, U., Rociński, A., and Crouzeix, J. P.

Published
1988
Full Text
View/download PDF

26. Combinatorial Optimization Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers

Author

Mahjoub, Ali Ridha, Markakis, Vangelis, Milis, Ioannis, Paschos, Vangelis, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
relaxation, networks, [INFO]Computer Science [cs], graph problems, algorithms and complexity, mathematical programming
Abstract

International audience; This book constitutes the thoroughly refereed post-conference proceedings of the Second International Symposium on Combinatorial Optimization, ISCO 2012, held in Athens, Greece, in April 2012. The 37 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 94 regular and 30 short submissions. They present original research on all aspects of combinatorial optimization, ranging from mathematical foundations and theory of algorithms to computational studies and practical applications.

Published
2012

27. A branch-and-cut algorithm for the k-edge connected subgraph problem

Author

Bendali, Fatiha, Diarrassouba, Ibrahima, Mahjoub, Ali Ridha, Didi Biha, Mohamed, Mailfert, Jean, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques Appliquées du Havre ( LMAH ), Université Le Havre Normandie ( ULH ), Normandie Université ( NU ) -Normandie Université ( NU ), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes ( LIMOS ), Centre National de la Recherche Scientifique ( CNRS ) -Sigma CLERMONT ( Sigma CLERMONT ) -Université d'Auvergne - Clermont-Ferrand I ( UdA ) -Université Blaise Pascal - Clermont-Ferrand 2 ( UBP ), Laboratoire de Mathématiques Nicolas Oresme ( LMNO ), Université de Caen Normandie ( UNICAEN ), Normandie Université ( NU ) -Normandie Université ( NU ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision ( LAMSADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Mathématiques Appliquées du Havre (LMAH), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Laboratoire de Mathématiques Nicolas Oresme (LMNO), Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
separation, 021103 operations research, Computer Networks and Communications, 0211 other engineering and technologies, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, reduction operations, branch-and-cut, 010201 computation theory & mathematics, Hardware and Architecture, polytope, facet, k-edge connected graph, Software, ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO], Information Systems
Abstract

International audience; 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.

Published
2010

32. Integer programming formulations for the two 4-hop-constrained paths problem

Author

Huygens, David, Mahjoub, Ali Ridha, Huygens, David, and Mahjoub, Ali Ridha

Abstract

In this article, we consider the two 4-hop-constrained paths problem, which consists, given a graph G = (N, E) and two nodes s, t ∈ N, of finding a minimum cost subgraph in G containing at least two node- (resp. edge-) disjoint paths of length at most 4 between s and t. We give integer programming formulations, in the space of the design variables, for both the node and edge versions of this problem. © 2006 wiley Periodicals, Inc., SCOPUS: ar.j, FLWIN, info:eu-repo/semantics/published

Published
2007

33. The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut

Author

Huygens, David, Labbé, Martine, Mahjoub, Ali Ridha, Pesneau, Pierre, Huygens, David, Labbé, Martine, Mahjoub, Ali Ridha, and Pesneau, Pierre

Abstract

This article deals with the Two-edge connected Hop-constrained Network Design Problem (or THNDP for short). Given a weighted graph G = (N, E), an integer L ≥ 2, and a subset of pairs of nodes D, the problem consists of finding the minimum cost subgraph in G containing at least two edge-disjoint paths of at most L hops between all the pairs in D. First, we show that the THNDP is strongly NP-hard even when the demands in D are rooted at some node s and the costs are unitary. However, if the graph is complete, we prove that the problem in this case can be solved in polynomial time. We give an integer programming formulation of the problem in the space of the design variables when L = 2, 3. Then we study the associated polytope. In particular, we consider the case where all the pairs of nodes of D are rooted at a node s. We give several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also derive separation routines for these inequalities. We finally develop a branch-and-cut algorithm based on these results and discuss some computational results for L = 2, 3. © 2006 Wiley Periodicals, Inc., SCOPUS: cp.j, FLWIN, info:eu-repo/semantics/published

Published
2007

34. On the k edge-disjoint 2-hop-constrained paths polytope

Author

Dahl, Geir, Huygens, David, Mahjoub, Ali Ridha, Pesneau, Pierre, Dahl, Geir, Huygens, David, Mahjoub, Ali Ridha, and Pesneau, Pierre

Abstract

The k edge-disjoint 2-hop-constrained paths problem consists in finding a minimum cost subgraph such that between two given nodes s and t there exist at least k edge-disjoint paths of at most 2 edges. We give an integer programming formulation for this problem and characterize the associated polytope. © 2005 Elsevier B.V. All rights reserved., SCOPUS: ar.j, info:eu-repo/semantics/published

Published
2006

36. Two edge-disjoint HOP-constrained paths and polyhedra

Author

Huygens, David, Mahjoub, Ali Ridha, Pesneau, Pierre, Huygens, David, Mahjoub, Ali Ridha, and Pesneau, Pierre

Abstract

Given a graph G with distinguished nodes s and t, a cost on each edge of G, and a fixed integer L ≥ 2, the two edge-disjoint hop-constrained paths problem is to find a minimum cost subgraph such that between s and t there exist at least two edge-disjoint paths of length at most L. In this paper, we consider that problem from a polyhedral point of view. We give an integer programming formulation for the problem when L = 2, 3. An extension of this result to the more general case where the number of required paths is arbitrary and L = 2, 3 is also given. We discuss the associated polytope, P(G, L), for L = 2, 3. In particular, we show in this case that the linear relaxation of P(G, L), Q(G, L), given by the trivial, the st-cut, and the so-called L-path-cut inequalities, is integral. As a consequence, we obtain a polynomial time cutting plane algorithm for the problem when L = 2, 3. We also give necessary and sufficient conditions for these inequalities to define facets of P(G, L) for L ≥ 2 when G is complete. We finally investigate the dominant of P(G, L) and give a complete description of this polyhedron for L ≥ 2 when P(G, L) = Q(G, L). © 2004 Society for Industrial and Applied Mathematics., SCOPUS: ar.j, info:eu-repo/semantics/published

Published
2004

37. Balanced Matrices and the Set-Covering Polytope

Author

Euler, Reinhardt, Mahjoub, Ali Ridha, Lab-STICC_UBO_CACS_MOCS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and Euler, Reinhardt

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
1991

38. On a Composition of Independence Systems by Circuit-Identification

Author

Euler, Reinhardt, Mahjoub, Ali Ridha, Lab-STICC_UBO_CACS_MOCS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and Euler, Reinhardt

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
1991

39. On the linear relaxation of the 2-node connected subgraph polytope

Author

Mahjoub, Ali Ridha, Nocq, Charles, Mahjoub, Ali Ridha, and Nocq, Charles

Abstract

In this paper, we study the linear relaxation P(G) of the 2-node connected subgraph polytope of a graph G. We introduce an ordering on the fractional extreme points of P(G) and we give a characterization of the minimal extreme points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of P(G) from the 2-node connected subgraph polytope. It also provides a new class of facet defining inequalities for this polytope. © 1999 Elsevier Science B.V. All rights reserved., SCOPUS: ar.j, info:eu-repo/semantics/published

Published
1999

Catalog

Books, media, physical & digital resources
See catalog results