A virtual computer system service receives a request to migrate a virtual machine instance from a first physical host to another physical host. The virtual computer system service identifies a configuration of the first physical host and obtains a data structure that specifies compatibility values for pairings of physical host configurations. The virtual computer system uses the configuration of the first physical host and the data structure to select a compatible physical host configuration. Using this compatible physical host configuration, the virtual computer system service selects a set of physical hosts that have this compatible physical host configuration. The set of physical hosts is used to select a second physical host onto which the virtual machine instance is migrated.