The water pump scheduling problem is an optimisation model that determines which water pumps will be turned on or off at each time period over a given time horizon for a given water supply system. This problem has received considerable attention in mining and desalination due to the high power consumption of water pumps and desalination plants and the complicated dynamics of water flows and the power market. Motivated by this, in this paper, we solve the optimal operation of a desalinated water supply system consisting of interconnected tanks and pumps that transport water to high-altitude reservoirs. The optimisation of this process encounters several difficulties arising from: i) the nonlinearities of the equations for the frictional losses along the pipes and pumps, which makes the problem a nonlinear mixed-integer model, and ii) many possible combinations of pressure head and flow rates, which quickly leads to high computational costs. These limitations prevent the problem from being solved in a reasonable computational time in high-altitude water supply systems with more than six pumps and reservoirs, as in many networks worldwide. Therefore, in this work, we develop new exact methods for the optimal pump scheduling problem that use a binary expansion approach to efficiently account for the existing nonlinearities by reducing the computational difficulties of the original problem while keeping an excellent representation of the physical phenomena involved. We also extensively tested the proposed approach in different network topologies and a case study for a real-world copper mine water network, and we conclude that the binary expansion approach significantly reduces the computational time for solving the problem with high precision, which can be very relevant for the practical daily operation of real-world water supply systems.