In service oriented architecture, workflow discovery and web service composition (WSC) are two major challenges and many works have been carried out in the recent years. In this work, we address the problem of WSC in a multi-cloud environment. All existing methods assume that a feasible solution exists and solves the WSC problem, however when user constraints are hard, a feasible solution might not exist and models fail to return an optimal solution. To address this problem, we propose an Integer Linear programming model where violations in global constraints are permitted but with an associated penalty. The results show that our method performs significantly better than the standard method when user constraints are hard. © 2017 IEEE.