Layered graph approaches for combinatorial optimization problems
From MaRDI portal
Publication:1628112
DOI10.1016/j.cor.2018.09.007zbMath1458.90612OpenAlexW2890623929WikidataQ129208090 ScholiaQ129208090MaRDI QIDQ1628112
Markus Leitner, Mario Ruthmair, Luís Gouveia
Publication date: 3 December 2018
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2018.09.007
Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items (10)
Linearized formulations for failure aware barter exchange ⋮ Minimum cost noncrossing flow problem on layered networks ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ The travelling salesman problem with positional consistency constraints: an application to healthcare services ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Perspectives on integer programming for time-dependent models ⋮ Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization ⋮ Branch-and-refine for solving time-expanded MILP formulations
Uses Software
Cites Work
- Unnamed Item
- Hop constrained Steiner trees with multiple root nodes
- Load-dependent and precedence-based models for pickup and delivery problems
- On the hop-constrained survivable network design problem with reliable edges
- Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
- The \(k\) edge-disjoint 3-hop-constrained paths polytope
- Natural and extended formulations for the time-dependent traveling salesman problem
- Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
- Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model
- Combined route capacity and route length models for unit demand vehicle routing problems
- A comparative analysis of several asymmetric traveling salesman problem formulations
- Hop-constrained node survivable network design: An application to MPLS over WDM
- Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem
- Extended formulation for hop constrained distribution network configuration problems
- Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem
- A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
- Thinning out Steiner trees: a node-based model for uniform edge costs
- Decomposition methods for the two-stage stochastic Steiner tree problem
- Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints
- An algorithmic framework for the exact solution of tree-star problems
- The time dependent traveling salesman problem: polyhedra and algorithm
- The two-level diameter constrained spanning tree problem
- Modeling and solving the rooted distance-constrained minimum spanning tree problem
- Dynamic graph generation for the shortest path problem in time expanded networks
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- Projection results for vehicle routing
- A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems
- A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows
- Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem
- Time-Indexed Formulations and the Total Weighted Tardiness Problem
- A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems
- A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem
- Models for optimal survivable routing with a minimum number of hops: comparing disaggregated with aggregated models
- On Solving the Rooted Delay- and Delay-Variation-Constrained Steiner Tree Problem
- A dual ascent approach for steiner tree problems on a directed graph
- Two exact algorithms for the distance-constrained vehicle routing problem
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
- A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
- Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
- The Continuous-Time Service Network Design Problem
- Integer programming formulations for thek-edge-connected 3-hop-constrained network design problem
- Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
- A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
- A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
- On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
- Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
- Hop‐level flow formulation for the survivable network design with hop constraints problem
- Solution of a Large-Scale Traveling-Salesman Problem
- Quickest Flows Over Time
- Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
- A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
This page was built for publication: Layered graph approaches for combinatorial optimization problems
