On imposing connectivity constraints in integer programs

DOI10.1007/s10107-017-1117-8zbMath1386.90023OpenAlexW2586469794MaRDI QIDQ1683690

Austin Buchanan, Sergiy I. Butenko, Yi-Ming Wang

Publication date: 1 December 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1117-8

zbMATH Keywords

contiguityconnectivity constraintsconnected subgraph polytopemaximum-weight connected subgraphprize-collecting Steiner tree

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) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (18)

Computational approaches for zero forcing and related problems ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach ⋮ A relax-and-cut framework for large-scale maximum weight connected subgraph problems ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Vertex covering with capacitated trees ⋮ Linear-size formulations for connected planar graph partitioning and political districting ⋮ Thinning out Steiner trees: a node-based model for uniform edge costs ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ Parsimonious formulations for low-diameter clusters ⋮ Parliament seating assignment problems ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Strong IP formulations need large coefficients ⋮ Congress seat allocation using mathematical optimization ⋮ Political districting to minimize cut edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connected dominating set. Theory and applications
• Polyhedral study of the connected subgraph problem
• Greedoids
• Geometric algorithms and combinatorial optimization.
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• Imposing Connectivity Constraints in Forest Planning Models
• The Maximum Weight Connected Subgraph Problem
• Optimal Political Districting by Implicit Enumeration Techniques
• The NP-completeness column: An ongoing guide

This page was built for publication: On imposing connectivity constraints in integer programs