Dr Ayse Aslan A.Aslan@napier.ac.uk
Research Fellow
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.
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 |
A Precedence Constrained Knapsack Problem With Uncertain Item Weights For Personalized Learning Systems (accepted version)
(805 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Lead time prediction with the Bosch production line dataset
(2022)
Dataset
Optimal admission and routing with congestion-sensitive customer classes
(2021)
Journal Article
A Memetic Random Key Algorithm for the Balanced Travelling Salesman Problem
(2021)
Conference Proceeding
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Advanced Search