Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem

DOI10.1016/j.ejor.2020.07.006zbMath1487.90624OpenAlexW3041516214MaRDI QIDQ2028800

Celso Carneiro Ribeiro, Michell F. Queiroz, Rafael A. Melo

Publication date: 3 June 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.07.006

zbMATH Keywords

metaheuristicsmixed integer programmingfeedback vertex setiterated local searchmatheuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Decycling bipartite graphs ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic ⋮ An improved configuration checking-based algorithm for the unicost set covering problem

Uses Software

• irace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower and upper bounds for the spanning tree with minimum branch vertices
• A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• Size bounds for dynamic monopolies
• The Steiner tree problem with hop constraints
• Minimum energy target tracking with coverage guarantee in wireless sensor networks
• A matheuristic for the driver scheduling problem with staff cars
• Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design
• Combining simulated annealing with local search heuristics
• Solving the feedback vertex set problem on undirected graphs
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Deadlock resolution in wait-for graphs by vertex/arc deletion
• Wavelength Conversion in Optical Networks
• A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem
• Integer Programming Formulation of Traveling Salesman Problems
• Minimum Weighted Feedback Vertex Set on Diamonds
• Feedback vertex sets and cyclically reducible graphs
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• A polyhedral approach to the feedback vertex set problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Reducibility among Combinatorial Problems
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Preface to the Special Issue on Matheuristics: Model‐Based Metaheuristics

This page was built for publication: Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem