The economics of the cloud model has been encouraging IT enterprises to migrate from on-premise environments to public, private, or hybrid cloud solutions. To perform such a migration, a cloud offering needs to be chosen and a cloud solution needs to be built. In industrial settings, cloud designers may spend days or even weeks to come up with an acceptable cloud solution at a low cost/price. Like any manual process, it is obvious that such a cloud solution design process is error prone, time consuming, and does not guarantee an optimal output, e.g. a solution with a minimum cost/price. Different from existing works that solve the problem from the user's angle, we solve it from the cloud provider's prospective, who aims at offering customized cloud solutions for different user requirements at low costs. Such difference requires a unique way of problem modeling. Through analyzing real business data, we abstract the problem into a general attribute–value combinations and formulate a powerful integer programming optimization model to solve it. The general form of the optimization model allows various definitions of customer requirements as well as cloud offerings. Our novel optimization approach for cloud solution design satisfies client requirements, cloud offering constraints, and produces a solution at a minimum cost in a short time, if one exists. We evaluated our solution on realistic data against two baseline approaches. The numerical results show both the effectiveness and efficiency of our approach as well as its practical potential.