  The partition of a problem into smaller sub-problems satisfying certain
properties is often a key ingredient in the design of divide-and-conquer
algorithms. For questions related to location, the partition problem can be
modeled, in geometric terms, as finding a subdivision of a planar map -- which
represents, say, a geographical area -- into regions subject to certain
conditions while optimizing some objective function. In this paper, we
investigate one of these geometric problems known as the Minimum Convex
Partition Problem (MCPP). A convex partition of a point set $P$ in the plane is
a subdivision of the convex hull of $P$ whose edges are segments with both
endpoints in $P$ and such that all internal faces are empty convex polygons.
The MCPP is an NP-hard problem where one seeks to find a convex partition with
the least number of faces.
  We present a novel polygon-based integer programming formulation for the
MCPP, which leads to better dual bounds than the previously known edge-based
model. Moreover, we introduce a primal heuristic, a branching rule and a
pricing algorithm. The combination of these techniques leads to the ability to
solve instances with twice as many points as previously possible while
constrained to identical computational resources. A comprehensive experimental
study is presented to show the impact of our design choices.
