@inproceedings {pub5368,
	title = {Mixed Integer Linear Programming Based Large Neighborhood Search Approaches for the Directed Feedback Vertex Set Problem },
	author = {Maria Bresich AND Johannes Varga AND Guenther Raidl AND Steffen Limmer},
	year = {2024},
	month = {September},
	abstract = { A directed feedback vertex set (DFVS) of a directed graph is a subset of vertices whose removal makes the graph acyclic. Finding a DFVS of minimum cardinality is the goal
of the directed feedback vertex set problem, an NP-hard combinatorial optimization problem. We first consider two mixed integer linear programming (MILP) models for this problem,
which, when solved with Gurobi, are effective on graphs of small to medium complexity but do not scale well to large instances. Aiming at better scalability and higher robustness
over a large variety of graphs, we investigate a large neighborhood search (LNS) in which a destroy operator removes randomly chosen nodes from an incumbent DFVS and one of the
MILP models is used for repair. Regarding the destroy operator, finding a best degree of destruction is challenging. A main contribution lies in proposing several selection strategies for
this parameter as well as a strategy for choosing the more promising MILP model for repair. We evaluate the performance of the MILP models and diff erent LNS variants on benchmark
instances and compare the approaches to each other as well as to state-of-the-art procedures. Results show that our LNS variants yield clearly better solutions on average than standalone
MILP solving. Even though our approaches cannot outperform the state-of-the-art, we gain valuable insights on beneficially configuring such a MILP-based LNS.},
	publisher = {Springer, LNCS, LNAI, LNBI},
	isbn = {9783031692574},
	booktitle = {9th International Conference on Metaheuristics and Nature Inspired Computing (META)},
	pages = {3-20}
}