A crystal structure prediction algorithm for use in periodic boundary conditions with empirical rigid models is presented, which employs (i) unrestricted cutoff radii for the real-space interactions, thus allowing the treatment of even very small unit cells, and (ii) a global-optimization algorithm based on the basin-hopping method of Wales et al. (D. J. Wales and J. P. K. Doye, J. Phys. Chem. A 1997, 101, 5111). The algorithm is then applied to the TIP4P model of water (W. L. Jorgensen et al., J. Chem. Phys. 1983, 79, 926.) in order to find the lowest enthalpy water-ice crystalline structures in the pressure region 0-8000 bar, in unit cells holding in the range of 1-16 molecules, and a database of the 10 lowest enthalpy structures found at pressures 0, 4000, and 8000 bar is presented. The algorithm finds many of the ice polymorphs and, in particular, finds that the lowest energy structure at zero pressure is almost exactly tied between an ice Ic (cubic ice) and ice Ih (hexagonal ice) structure, having near-identical energies.