Separation of partition inequalities for the \((1,2)\)-survivable network design problem

DOI10.1016/S0167-6377(02)00182-7zbMath1049.90010MaRDI QIDQ1866009

Hervé L. M. Kerivin, Ali Ridha Mahjoub

Publication date: 3 April 2003

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

zbMATH Keywords

algorithmsubmodular functionseparationSurvivable networkPartition inequalities

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Related Items

Separation of partition inequalities with terminals, A Network Design Problem with Two-Edge Matching Failures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• The ellipsoid method and its consequences in combinatorial optimization
• Submodular functions and optimization
• Separating from the dominant of the spanning tree polytope
• Design of survivable networks
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Separation of Partition Inequalities
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Optimal attack and reinforcement of a network
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints