Path relinking for unconstrained binary quadratic programming

► We devise for the first time two Path Relinking methods for UBQP. ► We assess the performance of these methods on both random and structured benchmark problems. ► The proposed methods improve the previous best known results for almost 40 percent of the 103 MaxCut instances. ► The proposed methods match consistently the previous best known results for the 31 large random instances.