Promoting healthy lifestyles is nowadays a public priority among most public entities. The ability to design an array of nutritious and appealing diets is very valuable. Menu Planning still presents a challenge which complexity derives from the
problems’ many dimensions and the idiosyncrasies of human behavior towards eating. Among the difculties encountered by researchers when facing the Menu Planning Problem, being able of fnding a rich feasible region stands out. We consider
it as a system of inequalities to which we try to fnd solutions. We have developed and implemented a two-phase algorithm -that mainly stems from the Randomized Search and the Genetic- that is capable of rapidly fnding an pool of solutions to the
system with the aim of properly identifying the feasible region of the underlying
problem and proceed to its densifcation. It consists of a hybrid algorithm inspired on a GRASP metaheuristic and a later recombination. First, it generates initial seeds, identifying best candidates and guiding the search to create solutions to the system, thus attempting to verify every inequality. Afterwards, the recombination of diferent promising candidates helps in the densifcation of the feasible region with new solutions. This methodology is an adaptation of other previously used in literature,
and that we apply to the MPP. For this, we generated a database of a 227 recipes and 272 ingredients. Applying this methodology to the database, we are able to obtain a pool of feasible (healthy and nutritious) complete menus for a given D number of days.
