The cage problem is the challenging problem of constructing graphs with the least number of vertices having the following properties: the graph most be k-regular (every vertex most has k neighbors); and the girth of a graph most be g (the minimum length of a cycle in the graph must be g). We say that a k-regular graph with girth g is a (k, g)-graph, and thus the cage problem is finding a (k, g)-graph with least number of vertices. This is an interesting problem not only for graph theorists but also for computer scientists, as it has several engineering applications and requires new computational approaches to discover more cages. A matheuristic is an optimization algorithm that combines linear programming models with metaheuristic techniques. In this chapter we review approaches to find cages, and propose a matheuristic to construct (k, g)-graphs with a small number of vertices using integer programming. We show this methodology is able to find cages within reasonable computational times using limited resources.