The environmental impacts of food are currently at unsustainable levels. Consumers undoubtedly play a central role in reducing the impacts of the food system to more sustainable levels via dietary changes and food waste reduction. Mathematical optimisation is one approach to identifying less environmentally impactful dietary patterns. A limited number of studies, however, have assessed whether impact reductions offered by optimised diets are enough to remain within planetary boundaries (i.e. attain ‘absolute’ environmental sustainability). Using UK food consumption as a case study, here we employ linear programming to identify nutritionally adequate diets that meet sociocultural acceptability criteria whilst minimising (a) environmental impact transgressions of their allocated share of the safe operating space (SoSOS) for nine planetary boundaries (PBs), (b) cost, or (c) deviation from the current diet. We show that the current diet is unsustainable as it transgresses six or seven PBs, depending on the SoSOS allocation principle. Optimising for minimum SoSOS transgressions yields diets offering significant impact reductions (66 - 95% reduction across all PBs) compared to the current average dietary pattern, but whether they completely mitigate SoSOS transgressions depends on the sharing principle adopted to assign the SoSOS to national food consumption. Additionally, by comparing least-cost and least-transgression solutions, we find a trade-off between cost and environmental sustainability indicating that more sustainable dietary patterns are not currently incentivised by the relative prices of food items in the UK. Our work demonstrates the value in embedding ‘absolute’ sustainability in diet optimisation so that solutions inherently provide a more clear-cut understanding of their broad implications on the environment.