Biological production of chemicals is an attractive alternative to petrochemical-based production, due to advantages in environmental impact and the spectrum of feasible targets. However, engineering microbial strains to overproduce a compound of interest can be a long, costly and painstaking process. If production can be coupled to cell growth it is possible to use adaptive laboratory evolution to increase the production rate. Strategies for coupling production to growth, however, are often not trivial to find. Here we present OptCouple, a constraint-based modeling algorithm to simultaneously identify combinations of gene knockouts, insertions and medium supplements that lead to growth-coupled production of a target compound. We validated the algorithm by showing that it can find novel strategies that are growth-coupled in silico for a compound that has not been coupled to growth previously, as well as reproduce known growth-coupled strain designs for two different target compounds. Furthermore, we used OptCouple to construct an alternative design with potential for higher production. We provide an efficient and easy-to-use implementation of the OptCouple algorithm in the cameo Python package for computational strain design.