SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning

DOI10.1287/ijoc.2021.1075OpenAlexW3206965766MaRDI QIDQ5084594

Frank de Meijer, Renata Sotirov

Publication date: 28 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.03616

zbMATH Keywords

semidefinite programmingreinforcement learningfacial reductioncutting-plane methodDykstra's projection algorithmquadratic cycle cover problem

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (2)

SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems

Uses Software

• SDPNAL+
• ADMM_QAP

Cites Work

• Unnamed Item
• Unnamed Item
• Iterative methods for fixed point problems in Hilbert spaces
• On minimum reload cost cycle cover
• Using tabu search techniques for graph coloring
• Alternating direction augmented Lagrangian methods for semidefinite programming
• A boundary point method to solve semidefinite programs
• Computing a nearest symmetric positive semidefinite matrix
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A cyclic projection algorithm via duality
• A successive projection method
• On the Slater condition for the SDP relaxations of nonconvex sets
• ADMM for the SDP relaxation of the QAP
• A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
• Hybrid evolutionary algorithms for graph coloring
• Geometric and LP-based heuristics for angular travelling salesman problems in the plane
• The quadratic cycle cover problem: special cases and efficient bounds
• Deriving solution value bounds from the ADMM
• Covering tours and cycle covers with turn costs: hardness and approximation
• A survey of local search methods for graph coloring
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• A Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming
• Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Convergence Study on the Symmetric Version of ADMM with Larger Step Sizes
• An Algorithm for Restricted Least Squares Regression
• On Solving the Quadratic Shortest Path Problem
• Assignment Problems
• Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
• On Directed 2-factors in Digraphs and 2-factors Containing Perfect Matchings in Bipartite Graphs
• Validation of subgradient optimization
• The Angular-Metric Traveling Salesman Problem
• SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
• Minimum reload cost cycle cover in complete graphs
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Optimal Covering Tours with Turn Costs
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• Reload cost problems: Minimum diameter spanning tree

This page was built for publication: SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning