Abstract In this paper, we address the difficulty of solving large-scale multi-dimensional knapsack instances (MKP), presenting a novel deep reinforcement learning (DRL) framework. In this DRL framework, we train different agents compatible with a discrete action space for sequential decision-making while still satisfying any resource constraint of the MKP. This novel framework incorporates the decision variable values in the 2D DRL where the agent is responsible for assigning a value of 1 or 0 to each of the variables. To the best of our knowledge, this is the first DRL model of its kind in which a 2D environment is formulated, and an element of the DRL solution matrix represents an item of the MKP. Our framework is configured to solve MKP instances of different dimensions and distributions. We propose a K-means approach to obtain an initial feasible solution that is used to train the DRL agent. We train four different agents in our framework and present the results comparing each of them with the CPLEX commercial solver. The results show that our agents can learn and generalize over instances with different sizes and distributions. Our DRL framework shows that it can solve medium-sized instances at least 45 times faster in CPU solution time and at least 10 times faster for large instances, with a maximum solution gap of 0.28% compared to the performance of CPLEX. Furthermore, at least 95% of the items are predicted in line with the CPLEX solution. Computations with DRL also provide a better optimality gap with respect to state-of-the-art approaches.

Emerald ash borer (EAB), a wood-boring insect native to Asia and invading North America, has killed untold millions of high-value ash trees that shade streets, homes, and parks and caused significant economic damage in cities of the United States. Local actions to reduce damage include surveillance to find EAB and control to slow its spread. We present a multistage stochastic mixed-integer programming (M-SMIP) model for the optimization of surveillance, treatment, and removal of ash trees in cities. Decision-dependent uncertainty is modeled by representing surveillance decisions and the realizations of the uncertain infestation parameter contingent on surveillance as branches in the M-SMIP scenario tree. The objective is to allocate resources to surveillance and control over space and time to maximize public benefits. We develop a new cutting-plane algorithm to strengthen the M-SMIP formulation and facilitate an optimal solution. We calibrate and validate our model of ash dynamics using seven years of observational data and apply the optimization model to a possible infestation in Burnsville, Minnesota. Proposed cutting planes improve the solution time by an average of seven times over solving the original M-SMIP model without cutting planes. Our comparative analysis shows that the M-SMIP model outperforms six different heuristic approaches proposed for the management of EAB. Results from optimally solving our M-SMIP model imply that under a belief of infestation, it is critical to apply surveillance immediately to locate EAB and then prioritize treatment of minimally infested trees followed by removal of highly infested trees. Summary of Contributions: Emerald ash borer (EAB) is one of the most damaging invasive species ever to reach the United States, damaging millions of ash trees. Much of the economic impact of EAB occurs in cities, where high-value ash trees grow in abundance along streets and in yards and parks. This paper addresses the joint optimization of surveillance and control of the emerald ash borer invasion, which is a novel application for the INFORMS society because, to our knowledge, this specific problem of EAB management has not been published before in any OR/MS journals. We develop a new multi-stage stochastic mixed-integer programming (MSS-MIP) formulation, and we apply our model to surveillance and control of EAB in cities. Our MSS-MIP model aims to help city managers maximize the net benefits of their healthy ash trees by determining the optimal timing and target population for surveying, treating, and removing infested ash trees while taking into account the spatio-temporal stochastic growth of the EAB infestation. We develop a new cutting plane methodology motivated by our problem, which could also be applied to other stochastic MIPs. Our cutting plane approach provides significant computational benefit in solving the problem. Specifically, proposed cutting planes improve the solution time by an average of seven times over solving the original M-SMIP model without cutting planes. We calibrate and validate our model using seven years of ash infestation observations in forests near Toledo, Ohio. We then apply our model to an urban forest in Burnsville, Minnesota, that is threatened by EAB. Our results provide insights into the optimal timing and location of EAB surveillance and control strategies.

Metabolic pathways show the complex interactions among enzymes that transform chemical compounds. The state of a metabolic pathway can be expressed as a vector, which denotes the yield of the compounds or the flux in that pathway at a given time. The steady state is a state that remains unchanged over time. Altering the state of the metabolism is very important for many applications such as biomedicine, biofuels, food industry, and cosmetics. The goal of the enzymatic target identification problem is to identify the set of enzymes whose knockouts lead the metabolism to a state that is close to a given goal state. Given that the size of the search space is exponential in the number of enzymes, the target identification problem is very computationally intensive. We develop efficient algorithms to solve the enzymatic target identification problem in this paper. Unlike existing algorithms, our method works for a broad set of metabolic network models. We measure the effect of the knockouts of a set of enzymes as a function of the deviation of the steady state of the pathway after their knockouts from the goal state. We develop two algorithms to find the enzyme set with minimal deviation from the goal state. The first one is a traversal approach that explores possible solutions in a systematic way using a branch and bound method. The second one uses genetic algorithms to derive good solutions from a set of alternative solutions iteratively. Unlike the former one, this one can run for very large pathways. Our experiments show that our algorithms' results follow those obtained in vitro in the literature from a number of applications. They also show that the traversal method is a good approximation of the exhaustive search algorithm and it is up to 11 times faster than the exhaustive one. This algorithm runs efficiently for pathways with up to 30 enzymes. For large pathways, our genetic algorithm can find good solutions in less than 10 minutes.