Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

Jorik Jooken, Pieter Leyman and Patrick De Causmaecker

European Journal of Operational Research, 2023, vol. 311, issue 1, 36-55

Abstract: Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate the structure of problem instances that are hard for existing solvers. In the current paper we are interested in investigating which features make 0-1 knapsack problem instances hard to solve to optimality for the state-of-the-art 0-1 knapsack solver. We propose a set of 14 features based on previous work by the authors in which so-called inclusionwise maximal solutions (IMSs) play a central role. Calculating these features is computationally expensive and requires one to solve hard combinatorial problems. Based on new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for calculating these features. These algorithms were executed for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Moreover, we show that these features can be cheaply approximated at the cost of less accurate hardness predictions. Using the instance space analysis methodology, we show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.

Keywords: Combinatorial optimization; 0-1 knapsack problem; Packing; Problem instance hardness; Instance space analysis (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723003065
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:311:y:2023:i:1:p:36-55

DOI: 10.1016/j.ejor.2023.04.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().