Decision-making software is used to automatically make informed decisions by leveraging large amounts of data. Advances in machine learning have extended the implementation of these systems to processes that have a significant impact on the lives of people, such as credit scoring, employment applications, or insurance rates. Due to their impact, these systems must guarantee fairness from social and legal points of view, operating in a non-discriminatory manner. Several methods have been studied in the literature to improve the fairness of these systems, but often at the cost of accuracy. In this work, we propose two methods based on the Variable Neighborhood Search scheme to optimize the fairness of machine learning models after the training phase. In particular, we apply the proposed approaches to optimize Linear Regression models, which are frequently used in decision-making software. The proposed methods are competitive with a state-of-the-art Hill Climbing algorithm, using a set of publicly available instances.