While various platforms are offering facilities for single-cloud application design, deployment and provisioning, there is a need to move to multiple clouds in order to achieve cost-effectiveness and avoid vendor lock-in. Apart from not supporting multi-cloud application management, many platforms usually focus on the deployment and provisioning phases of the cloud-based application lifecycle by neglecting the design phase. However, the design selection of the best possible cloud service composition affects the provisioning phase, as the more distant from optimality is the selected solution, the more adaptation actions will be enacted. To this end, there is a high need for cloud application design tools and methods which can select the best possible cloud service composition based on user requirements. This paper satisfies this need by proposing a cloud service composition approach able to optimally compose different types of cloud services by simultaneously satisfying various types of user requirements. These types, not concurrently supported by any cloud application design tool, include quality, deployment, security, placement and cost requirements. Moreover, the proposed approach addresses a particular design choice type not currently considered in literature.