In this article we address the problem of finding lower bounds for small Ramsey numbers $R(m,n)$ using circulant graphs. Our constructive approach is based on finding feasible colorings of circulant graphs using Integer Programming (IP) techniques. First we show how to model the problem as a Stackelberg game and, using the tools of bilevel optimization, we transform it into a single-level IP problem with an exponential number of constraints. Using related results from graph theory, we provide strengthening valid inequalities for whose separation we develop a tailored branch-and-bound algorithm. With our new method, we improve 17 best-known lower bounds for $R(3,n)$ where $n$ ranges between 26 and 46. The graphs representing feasible circulant $(m,n)$-colorings used to prove these new lower bounds are made publicly available. To the best of our knowledge, this is a first IP-based approach to tackle this very challenging combinatorial optimization problem.