MIP models for connected facility location: a theoretical and computational study

DOI10.1016/J.COR.2010.07.002MaRDI QIDQ709181zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Gollowitzer, Ivana Ljubić

Publication date 15 October 2010

Published in Computers \& Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.cor.2010.07.002

zbMATH Keywords

facility locationLP-relaxationsmixed integer programming modelsSteiner trees

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Branch-and-cut-and-price for capacitated connected facility location
• MIP modeling of incremental connected facility location
• Dual-based local search for the connected facility location and related problems
• The incremental connected facility location problem
• Primal-dual algorithms for connected facility location problems

Cites work

• A Branch and Cut Algorithm for a Steiner Tree-Star Problem
• A catalog of steiner tree formulations
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A comparison of Steiner tree relaxations
• A faster approximation algorithm for the Steiner problem in graphs
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An analytical comparison of different formulations of the travelling salesman problem
• Branch-and-cut-and-price for capacitated connected facility location
• Dual-based local search for the connected facility location and related problems
• scientific article; zbMATH DE number 5764866 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Hybrid metaheuristics. 4th international workshop, HM 2007, Dortmund, Germany, October 8--9, 2007. Proceedings
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Neighborhood search heuristics for the uncapacitated facility location problem
• Network flows. Theory, algorithms, and applications.
• On implementing the push-relabel method for the maximum flow problem
• On the exact solution of large-scale simple plant location problems
• Primal-dual algorithms for connected facility location problems
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Solving Steiner tree problems in graphs to optimality
• Solving the simple plant location problem by genetic algorithm
• Strong lower bounds for the prize collecting Steiner problem in graphs
• The General Steiner Tree-Star problem.
• The regenerator location problem
• The Steiner tree polytope and related polyhedra
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The tree of hubs location problem
• Tight bounds from a path based formulation for the tree of hub location problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints

Cited in

(32)

• Upgrading nodes in tree-shaped hub location
• The p-arborescence star problem: formulations and exact solution approaches
• The online multicommodity connected facility location problem
• The connected facility location polytope
• Fiber cable network design in tree networks
• An algorithmic framework for the exact solution of tree-star problems
• Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
• General network design: a unified view of combined location and network design problems
• Optimizing splitter and fiber location in a multilevel optical FTTH network
• A tailored Benders decomposition approach for last-mile delivery with autonomous robots
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• A two-level off-grid electric distribution problem on the continuous space
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• A MIP-based approach to solve the prize-collecting local access network design problem
• A branch-and-cut algorithm for the maximum covering cycle problem
• The incremental connected facility location problem
• A cutting plane algorithm for the capacitated connected facility location problem
• Towards optimizing the deployment of optical access networks
• Dual-based local search for the connected facility location and related problems
• Approximate robust optimization for the connected facility location problem
• MIP modeling of incremental connected facility location
• Benders decomposition of the passive optical network design problem
• ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design
• Modelling the hop constrained connected facility location problem on layered graphs
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Configuration‐based approach for topological problems in the design of wireless sensor networks
• New formulations for two location problems with interconnected facilities
• Branch-and-cut-and-price for capacitated connected facility location
• A polynomial-time exact algorithm for the connected k-facility location problem on trees
• The ordered median tree location problem
• Lagrangian decompositions for the two-level FTTx network design problem

Describes a project that uses

Uses Software

• SteinLib
• CPLEX
• OR-Library

This page was built for publication: MIP models for connected facility location: a theoretical and computational study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q709181)