Cloud computing technologies can be used to more flexibly provision application resources. By exploiting multi-tenancy, instances can be shared between users, lowering the cost of providing applications. A weakness of current cloud offerings however, is the difficulty of creating customizable applications that retain these advantages. In this article, we define a feature-based cloud resource management model, making use of Software Product Line Engineering techniques, where applications are composed of feature instances using a service-oriented architecture. We focus on how resources can be allocated in a cost-effective way within this model, a problem which we refer to as the feature placement problem. A formal description of this problem, that can be used to allocate resources in a cost-effective way, is provided. We take both the cost of failure to place features, and the cost of using servers into account, making it possible to take energy costs or the cost of public cloud infrastructure into consideration during the placement calculation. Four algorithms that can be used to solve the feature placement problem are defined. We evaluate the algorithm solutions, comparing them with the optimal solution determined using an integer linear problem solver, and evaluating the execution times of the algorithms, making use of both generated inputs and a use case based on three applications. We show that, using our approach a higher degree of multi-tenancy can be achieved, and that for the considered scenarios, taking the relationships between features into account and using application-oriented placement performs 25–40 % better than a purely feature-oriented placement.