Devising genetic interventions for desired cellular phenotypes remains challenging regarding time and resources. Kinetic models can accelerate this task by simulating metabolic responses to genetic perturbations. However, exhaustive design evaluations with kinetic models are computationally impractical, especially when targeting multiple enzymes. Here, we introduce a framework for efficiently scouting the design space while respecting cellular physiological requirements. The framework employs mixed-integer linear programming and nonlinear simulations with large-scale nonlinear kinetic models to devise genetic interventions while accounting for the network effects of these perturbations. Importantly, it ensures the engineered strain's robustness by maintaining its phenotype close to that of the reference strain. The framework, applied to improve the anthranilate production in E. coli, devises designs for experimental implementation, including eight previously experimentally validated targets. We expect this framework to play a crucial role in future design-build-test-learn cycles, significantly expediting the strain design compared to exhaustive design enumeration.