Background: Food consumption is one of the most important drivers of the relation between human well-being and Earth's ecosystems. The current production level is difficult to sustain without compromising environmental integrity or public health. This calls for a decisive change in food consumption patterns in order to improve nutrition quality while respecting biodiversity and ecosystems. This change will produce some effect only if it is also culturally acceptable, accessible, economically fair and affordable. The design of food plans is traditionally carried out using mathematical optimization models, such as linear programming. This method has proved to be successful in providing nutritionally adequate diets while minimizing their economic and environmental impact. Nevertheless, cultural habits as well as attractiveness and variety of meals is very difficult to deal with, and no fully satisfactory way to include these issues in linear programming has been found. Objective: The aim of this paper is to move from traditional linear programming to a new programming methodology in order to cope also with acceptability in the design of meal plans. Method: Binary integer linear programming is the new modeling paradigm. In the proposed model, meal plans consist of providing the sequence and composition of daily meals over a given period of time and each meal can be composed using dishes from a given set. Therefore, instead of defining just a level of consumption of food groups or food items, the proposed model provides a realistic menu. To cope with sustainability, the energy and nutritional content of each dish is calculated together with its price and environmental impact. Furthermore, acceptability can be explicitly taken into account in a very natural way, that is bounding the daily, weekly, or total repetitions of single dishes and of dishes in the same food groups. Results: The paper reviews three successful studies with increasing complexity considering lunch plans for schools and full-board menus for nursing homes. The case studies show a great reduction of the environmental impact of the meal plans while ensuring an adequate nutritional intake, affordable prices and most importantly the plans are varied and culturally acceptable.