Objective: To identify optimal food choices that meet nutritional recommendations to reduce prevalence of inadequate nutrient intakes. Design: Linear programming was used to obtain an optimized diet with sixty-eight foods with the least difference from the observed population mean dietary intake while meeting a set of nutritional goals that included reduction in the prevalence of inadequate nutrient intakes to ≤20 %. Setting: Brazil. Subjects: Participants (men and women, n 25 324) aged 20 years or more from the first National Dietary Survey (NDS) 2008-2009. Results: Feasible solution to the model was not found when all constraints were imposed; infeasible nutrients were Ca, vitamins D and E, Mg, Zn, fibre, linolenic acid, monounsaturated fat and Na. Feasible solution was obtained after relaxing the nutritional constraints for these limiting nutrients by including a deviation variable in the model. Estimated prevalence of nutrient inadequacy was reduced by 60-70 % for most nutrients, and mean saturated and trans-fat decreased in the optimized diet meeting the model constraints. Optimized diet was characterized by increases especially in fruits (+92 g), beans (+64 g), vegetables (+43 g), milk (+12 g), fish and seafood (+15 g) and whole cereals (+14 g), and reductions of sugar-sweetened beverages (-90 g), rice (-63 g), snacks (-14 g), red meat (-13 g) and processed meat (-9·7 g). Conclusion: Linear programming is a unique tool to identify which changes in the current diet can increase nutrient intake and place the population at lower risk of nutrient inadequacy. Reaching nutritional adequacy for all nutrients would require major dietary changes in the Brazilian diet.