Skip to main content

Research Repository

Advanced Search

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

Aslan, Ayse; Ursavas, Evrim; Romeijnders, Ward

Authors

Ayse Aslan

Evrim Ursavas

Ward Romeijnders



Abstract

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.

Citation

Aslan, A., Ursavas, E., & Romeijnders, W. (2023). A Precedence Constrained Knapsack Problem with Uncertain Item Weights for Personalized Learning Systems. Omega, 115, Article 102779. https://doi.org/10.1016/j.omega.2022.102779

Journal Article Type Article
Acceptance Date Sep 29, 2022
Online Publication Date Oct 3, 2022
Publication Date 2023-02
Deposit Date Oct 5, 2022
Publicly Available Date Oct 5, 2022
Journal Omega
Print ISSN 0305-0483
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 115
Article Number 102779
DOI https://doi.org/10.1016/j.omega.2022.102779
Keywords Knapsack Problems, Chance-constrained Programming, Cutting Plane Methods, Personalized Learning, OR in Education, Precedence Constraints
Public URL http://researchrepository.napier.ac.uk/Output/2855722

Files





Downloadable Citations