A simple and effective algorithm for the maximum happy vertices problem

Top - 2022
Marco Ghirardi1, Fabio Salassa1
1DIGEP, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129, Turin, Italy

Tóm tắt

AbstractIn a recent paper, a solution approach to the Maximum Happy Vertices Problem has been proposed. The approach is based on a constructive heuristic improved by a matheuristic local search phase. We propose a new procedure able to outperform the previous solution algorithm both in terms of solution quality and computational time. Our approach is based on simple ingredients implying as starting solution generator an approximation algorithm and as an improving phase a new matheuristic local search. The procedure is then extended to a multi-start configuration, able to further improve the solution quality at the cost of an acceptable increase in computational time.

Từ khóa


Tài liệu tham khảo

Agrawal A (2017) On the parameterized complexity of happy vertex coloring. In IWOCA

Aravind N, Kalyanasundaram S, Anjeneya SK (2016) Linear time algorithms for happy vertex coloring problems for trees. In IWOCA

Ball M (2011) Heuristics based on mathematical programming. Surv Oper Res Manag Sci 16:21–38

Billaut J, Croce F, Grosso A (2015) A single machine scheduling problem with two-dimensional vector packing constraints. Eur J Oper Res 243:75–81

Blum C, Pinacho P, López-Ibáñez P, Lozano JA (2016) Construct, merge, solve and adapt a new general algorithm for combinatorial optimization. Comput Oper Res 68:75–88

Croce F, Grosso A, Salassa F (2019) Minimizing total completion time in the two-machine no-idle no-wait flow shop problem. J Heuristics 1:1–15

Della Croce F, Salassa F (2014) A variable neighborhood search based matheuristic for nurse rostering problems. Ann Oper Res 218:185–199

Della Croce F, Grosso A, Salassa F (2013) Matheuristics: embedding milp solvers into heuristic algorithms for combinatorial optimization problems. Heuristics: theory and applications. Nova Science Publishers, New York, pp 31–52

Della Croce F, Grosso A, Salassa F (2014) A matheuristic approach for the two-machine total completion time flow shop problem. Ann Oper Res 213:67–78

Doi Tsubasa, Nishi Tatsushi, Voß Stefan (2018) Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. Eur J Oper Res 267:428–438

Ghirardi M, Amerio A (2019) Matheuristics for the lot sizing problem with back-ordering, setup carry-overs, and non-identical machines. Comput Ind Eng 127:822–831

Giusy Macrina G, Laporte F. Guerriero, Pugliese L (2019) An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows. Eur J Oper Res 276:971–982

Lewis R, Thiruvady D, Morgan K (2018a) Algorithm source code. http://www.rhydlewis.eu/resources/happyalgs.zip. Accessed date 7 Jun 2021

Lewis R, Thiruvady D, Morgan K (2018b) Problem instance generator. http://www.rhydlewis.eu/resources/happygen.zip. Accessed date 7 Jun 2021

Lewis R, Thiruvady D, Morgan K (2019) Finding happiness: an analysis of the maximum happy vertices problem. Comput Oper Res 103:265–276

Luis Fanjul-Peyro F, Perea R. Ruiz (2017) Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. Eur J Oper Res 260:482–493

Malaguti E, Toth P (2010) A survey on vertex coloring problems. Int Trans Oper Res 17:1–34

Martinez-Sykora A, Alvarez-Valdés R, Bennell J, Ruiz R, Tamarit JM (2017) Matheuristics for the irregular bin packing problem with free rotations. Eur J Oper Res 258:440–455

Shahmanzari Masoud, Aksen D, Salhi S (2020) Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics. Eur J Oper Res 280:656–670

Zhang P, Li A (2015) Algorithmic aspects of homophyly of networks. Theor Comput Sci 593:117–131

Zhang P, Xu Y, Li A, Lin G (2018) Improved approximation algorithms for the maximum happy vertices and edges problems. Algorithmica 80:1412–1438

Thông tin
Thông tin xuất bản

Top

Thông tin tác giả