In this paper we develop a Variable neighborhood search (VNS) heuristic for solving Mixed-Integer Programs (MIP’s). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent Local Branching (LB) method of Fischetti and Lodi [5]. Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.