This work tackles the simultaneous synthesis and design of heat exchanger networks (HEN) integrated with complex utility systems, such as Heat Recovery Steam Cycles or Organic Rankine Cycles. Thanks to the combination of two superstructures (Rankine cycles and HEN), all the key heat integration options between process and utility system can be considered, and the trade-off between efficiency and costs is optimized. The superstructure for complex utility systems involves streams with variable flow rate. The resulting MINLP problem is very challenging due to its large number of binary variables and non-convex terms. We present a novel bilevel decomposition algorithm, combining the outer-approximation linearization technique with McCormick relaxation, valid redundant constraints, piecewise linearization of cost functions and "nested" integer cuts. The algorithm successfully tackled real-world problems with up to 35 streams showing considerable improvements in solution quality and computational time over commercial MINLP solvers and meta-heuristic algorithms. (C) 2019 Elsevier Ltd. All rights reserved.