We consider a given set of offshore platforms and onshore wells, producing known (or estimated) amounts of oil, to be connected to a port. Connections may take place directly between platforms, well sites and the port or may go though connection points at given locations. The configuration of the network and sizes of pipes used must be chosen in order to minimize construction costs. This problem is expressed as a mixed integer program, and solved both heuristically by Tabu Search and Variable Neighbourhood Search methods and exactly by a branch-and-bound method. Two new types of valid inequalities are used. Tests are made with data from the South Gabon oil field and randomly-generated problems.