Regenerator location problem: polyhedral study and effective branch-and-cut algorithms

DOI10.1016/j.ejor.2016.07.032zbMath1394.90548OpenAlexW2476038618MaRDI QIDQ1752767

Xiangyong Li, Yash P. Aneja

Publication date: 24 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.07.032

zbMATH Keywords

integer programmingbranch and cutfacetsoptical network designregenerator placement

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

A new branch-and-cut approach for the generalized regenerator location problem, The Optimal Design of Low-Latency Virtual Backbones, A branch-and-Benders-cut approach for the fault tolerant regenerator location problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks
• An exact algorithm for the maximum leaf spanning tree problem
• Integer linear programming models for topology optimization in sheet metal design
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• Approximation algorithms for connected dominating sets
• An exact algorithm for the maximum leaf spanning tree problem.
• Metaheuristic hybridizations for the regenerator placement and dimensioning problem in sub-wavelength switching optical networks
• On connected dominating sets of restricted diameter
• On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters
• Online Optimization of Busy Time on Parallel Machines
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• The regenerator location problem
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
• The Generalized Regenerator Location Problem
• The maximum-leaf spanning tree problem: Formulations and facets
• Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron
• Improved heuristics for the regenerator location problem
• A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem
• The Maximum Weight Connected Subgraph Problem