The Altai-Uliastai regional power system (AURPS) is a regional power system radially interconnected to the power system of Mongolia. The 110 kV interconnection is exceptionally long and susceptible to frequent trips because of weather conditions. The load-rich and low-inertia AURPS must be islanded during interconnection outages, and the under-frequency load shedding (UFLS) scheme must act to ensure secure operation. Traditional UFLS over-sheds local demand, negatively affecting the local population, especially during the cold Mongolian winter season. This research paper proposes a novel methodology to optimally calculate the settings of the UFLS scheme, where each parameter of the scheme is individually adjusted to minimise the total amount of disconnected load. This paper presents a computationally efficient methodology that is illustrated in a specially created co-simulation environment (DIgSILENT® PowerFactoryTM + Python). The results demonstrate an outstanding performance of the proposed approach when compared with the traditional one.@en