Browsing by Author "Layeb, S. B."

Now showing 1 - 4 of 4

Metadata only
Algorithmic expedients for the prize collecting Steiner tree problem
(Elsevier, 2010) Haouari, Mohamed; Layeb, S. B.; Sherali, H. D.; Industrial Engineering; HAOUARI, Mohamed
This paper investigates the Prize Collecting Steiner Tree Problem (PCSTP) on a graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, node prizes and penalties, as well as a preset quota, the PCSTP seeks to find a subtree that includes the root node and collects a total prize not smaller than the specified quota, while minimizing the sum of the total edge costs of the tree plus the penalties associated with the nodes that are not included in the subtree. For this challenging network design problem that arises in telecommunication settings, we present two valid 0-1 programming formulations and use them to develop preprocessing procedures for reducing the graph size. Also, we design an optimization-based heuristic that requires solving a PCSTP on a specific tree-subgraph. Although, this latter special case is shown to be NP-hard, it is effectively solvable in pseudo-polynomial time. The worst-case performance of the proposed heuristic is also investigated. In addition, we describe new valid inequalities for the PCSTP and embed all the aforementioned constructs in an exact row-generation approach. Our computational study reveals that the proposed approach can solve relatively large-scale PCSTP instances having up to 1000 nodes to optimality.
Metadata only
Solving the steiner tree problem with revenues, budget and hop constraints to optimality
(IEEE, 2013) Layeb, S. B.; Hajri, I.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. These constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the Reformulation-Linearization Technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.
Metadata only
Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint
(Elsevier, 2010-08-01) Haouari, Mohamed; Layeb, S. B.; Sherali, H. D.; Industrial Engineering; HAOUARI, Mohamed
This paper investigates the quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver.
Metadata only
Tight compact models and comparative analysis for the prize collecting Steiner tree problem
(Elsevier, 2013-03) Haouari, Mohamed; Layeb, S. B.; Sherali, H. D.; Industrial Engineering; HAOUARI, Mohamed
We investigate a generalized version of the prize collecting Steiner tree problem (PCSTP), where each node of a given weighted graph is associated with a prize as well as a penalty cost. The problem is to find a tree spanning a subset of nodes that collects a total prize not less than a given quota Q, such that the sum of the weights of the edges in the tree plus the sum of the penalties of those nodes that are not covered by the tree is minimized. We formulate several compact mixed-integer programming models for the PCSTP and enhance them by appending valid inequalities, lifting constraints, or reformulating the model using the Reformulation–Linearization Technique (RLT). We also conduct a theoretical comparison of the relative strengths of the associated LP relaxations. Extensive results are presented using a large set of benchmark instances to compare the different formulations. In particular, a proposed hybrid compact formulation approach is shown to provide optimal or very near-optimal solutions for instances having up to 2500 nodes and 3125 edges.