An Effective Matheuristic for the Capacitated Total Quantity Discount Problem

New generation algorithms focus on hybrid miscellaneous of exact and heuristic methods. Combining meta-heuristics and exact methods based on mathematical models appears to be a very promising alternative in solving many combinatorial optimization problems. In this paper we introduce a matheuristic method exploiting the optimal solution of mixed integer subproblems to solve the complex supplier selection problem of a company that needs to select a subset of suppliers so to minimize purchasing costs while satisfying products demand. Suppliers offer products at given prices and apply discounts according to the total quantity purchased. The problem, known as Total Quantity Discount Problem (TQDP), is strongly NP-hard thus motivating the study of effective and efficient heuristic methods. The proposed solution method is strengthened by the introduction of an Integer Linear Programming (ILP) refinement approach. An extensive computational analysis on a set of benchmark instances available in the literature has shown how the method is efficient and extremely effective allowing to improve existing best known solution values.