Date of Award

9-2023

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Department of Operational Sciences

First Advisor

Raymond R. Hill, PhD

Abstract

This work focuses on instance generation methods for the multi-demand multidimensional knapsack problem (MDMKP). Specifically, instance space analysis (ISA) is used to characterize the landscape of existing instances and validate the novelty of new instances generated with a novel problem generation method, the primal problem instance generator (PPIG). The instance generator is capable of producing feasible, diverse, and challenging instances by directly controlling the problem features. PPIG contributes to the previous collections of instances and is validated through instance space analysis. The research presents an in-depth empirical evaluation of existing solution procedures for the MDMKP. The portfolio of metaheuristics examined show promising performance on existing benchmark libraries but lack robustness when the test set of instances are extended using the PPIG method. A machine learning classifier is employed to provide an interpretable link between instance configuration and solution procedure performance. The final aspect of the research is an optimization framework used to provide problem generation parameters to the PPIG methodology to further cover the instance space for the full suite of MDMKP test problems.

AFIT Designator

AFIT-ENS-DS-23-S-020

Comments

A 12-month embargo was observed for posting this dissertation on AFIT Scholar.

Approved for public release. PA case number on file.

Download

Share

COinS