New approaches for optimizing over the semimetric polytope

DOI10.1007/s10107-005-0620-5zbMath1124.90043OpenAlexW2086003967WikidataQ58002902 ScholiaQ58002902MaRDI QIDQ2576727

Antonio Frangioni, Giovanni Rinaldi, Andrea Lodi

Publication date: 14 December 2005

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

Full work available at URL: https://doi.org/10.1007/s10107-005-0620-5

zbMATH Keywords

network designmax-cutLagrangian methodssemimetric polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46)

Related Items

Inexact stabilized Benders' decomposition approaches with application to chance-constrained problems with finite support, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Stochastic graph partitioning: quadratic versus SOCP formulations, Dynamic bundle methods, A stabilized structured Dantzig-Wolfe decomposition method, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, On the computational efficiency of subgradient methods: a case study with Lagrangian bounds, Monotonizing linear programs with up to two nonzeroes per column, Improved compact formulations for a wide class of graph partitioning problems in sparse graphs, Bundle methods for sum-functions with ``easy components: applications to multicommodity network design, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, A Lagrangian approach to chance constrained routing with local broadcast, About Lagrangian methods in integer optimization

Uses Software

• GraphBase

Cites Work

• Unnamed Item
• Unnamed Item
• Pseudo-Boolean optimization
• About Lagrangian methods in integer optimization
• Combinatorial approaches to multiflow problems
• Geometric algorithms and combinatorial optimization
• On improvements to the analytic center cutting plane method
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• The volume algorithm revisited: relation with bundle methods
• The volume algorithm: Producing primal solutions with a subgradient method
• Lagrangean relaxation. (With comments and rejoinder).
• Solving semidefinite quadratic problems within nonsmooth optimization algorithms
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
• On the cut polytope
• Generalized Bundle Methods
• Integer Programming and Combinatorial Optimization
• Geometry of cuts and metrics
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design