An optimization-based procedure for studying the response of metabolic networks after gene knockouts or additions is introduced and applied to a linear flux balance analysis (FBA) Escherichia coli model. Both the gene addition problem of optimally selecting which foreign genes to recombine into E. coli, as well as the gene deletion problem of removing a given number of existing ones, are formulated as mixed-integer optimization problems using binary 0-1 variables. The developed modeling and optimization framework is tested by investigating the effect of gene deletions on biomass production and addressing the maximum theoretical production of the 20 amino acids for aerobic growth on glucose and acetate substrates. In the gene deletion study, the smallest gene set necessary to achieve maximum biomass production in E. coli is determined for aerobic growth on glucose. The subsequent gene knockout analysis indicates that biomass production decreases monotonically, rendering the metabolic network incapable of growth after only 18 gene deletions. In the gene addition study, the E. coli flux balance model is augmented with 3,400 non-E. coli reactions from the KEGG database to form a multispecies model. This model is referred to as the Universal model. This study reveals that the maximum theoretical production of six amino acids could be improved by the addition of only one or two genes to the native amino acid production pathway of E. coli, even though the model could choose from 3,400 foreign reaction candidates. Specifically, manipulation of the arginine production pathway showed the most promise with 8.75% and 9.05% predicted increases with the addition of genes for growth on glucose and acetate, respectively. The mechanism of all suggested enhancements is either by: 1) improving the energy efficiency and/or 2) increasing the carbon conversion efficiency of the production route.