Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem

DOI10.1287/opre.2021.2110zbMath1503.91039OpenAlexW3201637698MaRDI QIDQ5106375

Enrico Malaguti, Paolo Paronuzzi, Fabio Furini, Ivana Ljubić

Publication date: 19 September 2022

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.2021.2110

zbMATH Keywords

branch-and-cutBenders decompositiongraph decompositionbilevel optimizationStackelberg games

Mathematics Subject Classification ID

Applications of graph theory (05C90) Hierarchical games (including Stackelberg games) (91A65) 2-person games (91A05) Combinatorial optimization (90C27)

Related Items

Critical node/edge detection problems on trees, Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem, An exact method for binary fortification games, Mathematical programming formulations for the collapsed k-core problem, Political districting to minimize cut edges

Uses Software

• MIPLIB
• DIMACS
• Algorithm 447
• k-Vertex-Cut-Problem

Cites Work

• Unnamed Item
• Stackelberg bipartite vertex cover and the preflow algorithm
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Finding good approximate vertex and edge partitions is NP-hard
• Partitioning planar graphs with vertex costs: Algorithms and applications
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• The bilevel programming problem: reformulations, constraint qualifications and optimality conditions
• A study of general and security Stackelberg game formulations
• A branch-and-price algorithm for capacitated hypergraph vertex separation
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• The vertex \(k\)-cut problem
• Epidemic dynamics on complex networks
• The vertex separator problem: algorithms and computations
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• Stochastic Network Interdiction
• Joint Design and Pricing on a Network
• A Separator Theorem for Planar Graphs
• Parallel Algorithms for Sparse Linear Systems
• Decomposing Matrices into Blocks
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
• A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Sequential Interdiction with Incomplete Information and Learning
• Multilevel Approaches for the Critical Node Problem
• A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization
• NP-completeness of the Planar Separator Problems
• Collective dynamics of ‘small-world’ networks
• Benchmarking optimization software with performance profiles.