Industrial operations consume energy and water in large quantities without accounting for potential economic and environmental burdens on future generations. Consumption of energy (mainly in the form of high pressure steam) and water (in the form of process water and cooling water) are essential to all processes and are strongly correlated, which requires development of systematic methodologies to address their interconnectivity. To this end, the subject of heat-integrated water allocation network design has received considerable attention within the research community in recent decades while further growth is expected due to imposed national and global regulations within the context of sustainable development. The overall mathematical model of these networks has a mixed-integer nonlinear programming formulation. As discussed in this work, proposed models in the literature have two main difficulties dealing with heat–water specificities, which result in complex formulations. These difficulties are addressed in this work through proposition of a novel nonlinear hyperstructure and a sequential solution strategy. The solution strategy is to solve three sub-problems sequentially and iteratively generate a set of potential solutions through the implementation of integer cut constraints. The novel mathematical approach also lends itself to an additional innovation for proposing multiple solutions balancing various performance indicators. This is exemplified with both a literature test case and an industrial-scale problem. The proposed solutions address a variety of performance indicators which guides decision-makers toward selecting the most appropriate configuration(s) among a large number of potential possibilities. Results exhibit that despite having a sequential solution strategy, better performance can be reached compared to previous approaches with the additional benefit of providing many potential solutions for further consideration by decision-makers to select the best case-specific solution.