A Precedence Constrained Knapsack Problem with Uncertain Item Weights for Personalized Learning Systems

This paper studies a unique precedence constrained knapsack problem in which there are two methods available to place an item in the knapsack. Whether or not an item weight is uncertain depends on which one of the two methods is selected. This knapsack problem models students’ decisions on choosing subjects to study in hybrid personalized learning systems in which students can study either under teacher supervision or in an unsupervised self-study mode by using online tools. We incorporate the uncertainty in the problem using a chance-constrained programming framework. Under the assumption that uncertain item weights are independently and normally distributed, we focus on the deterministic reformulation in which the capacity constraint involves a nonlinear and convex function of the decision variables. By using the first-order linear approximations of this function, we propose an exact cutting plane method that iteratively adds feasibility cuts. To supplement this, we develop novel approximate cutting plane methods that converge quickly to high-quality feasible solutions. To improve the computational efficiency of our methods, we introduce new pre-processing procedures to eliminate items beforehand and cover cuts to refine the feasibility space. Our computational experiments on small and large problem instances show that the optimality gaps of our approximate methods are very small overall, and that they are even able to find solutions with no optimality gaps as the number of items increases in the instances. Moreover, our experiments demonstrate that our pre-processing methods are particularly effective when the precedence relations are dense, and that our cover cuts may significantly speed up our exact cutting plane approach in challenging instances.