The problem of optimal location and sizing of off-shore platforms for oil exploration can be formulated as follows: given a set of oil wells to be drilled and a set of possible locations for platforms of standard sizes, determine the location and capacity of the platforms to be built as well as the assignment of wells to platforms from which they will be drilled in order to minimize investment costs. This problem is formulated as a multicapacitated plant location problem and both its exact and its approximate solution (by MIP/MPSX and by a Tabu Search heuristic) are discussed. Current and planned use of the program implementing this approach at PETROBRAS (the Brazilian state-owned company in charge of oil prospection, exploitation and distribution) is discussed.