In this paper, we propose a new approach to solve combinatorial optimization problems. Our approach is simple to implement but powerful in terms of performance and speed. We combine the strengths of a meta-heuristic approach with the integer programming method by partitioning the problem into two interrelated subproblems, where the higher level problem is solved by the metahueristic and the lower level problem is solved by integer programming. We discuss the selection of key variables to facilitate an effective partitioning, and test our approach on two real world cross-docking problems which is very popular in this part of the world. Our experimental results indicate that our new approach is very promising.