A Novel Core-Based Optimization Framework for Binary Integer Programs- the Multidemand Multidimesional Knapsack Problem as a Test Problem

Sameh Al-Shihabi

Operations Research Perspectives, 2021, vol. 8, issue C

Abstract: The effectiveness and efficiency of optimization algorithms might deteriorate when solving large-scale binary integer programs (BIPs). Consequently, researchers have tried to fix the values of certain variables called adjunct variables, and only optimize a small problem version formed from the remaining variables called core variables, by relying on information obtained from the BIP’s LP-relaxation solution. The resulting reduced problem is called a core problem (CP), and finding an optimal solution to a CP does not mean finding an optimal solution to the BIP unless the adjunct variables are fixed to their optimal values. Thus, in this work, we borrow several concepts from local search (LS) heuristics to move from a CP to a neighbouring CP to find a CP whose optimal solution is also optimal for the BIP. Thus, we call our framework CORE-LP-LS. We also propose a new mechanism to choose core variables based on reduced costs. To demonstrate and test the CORE-LP-LS framework, we solve a set of 126 multidemand multidimensional knapsack problem (MDMKP) instances. We solve the resulting CPs using two algorithms, namely, commercial branch and bound solver and the state-of-the-art meta-heuristic algorithm to solve MDMKP. As a by-product to our experiments, the CORE-LP-LS framework variants found 28 new best-known solutions and better average solutions for most of the solved instances.

Keywords: Combinatorial optimization; Core problem; Multidemand multidimensional knapsack problem; Branch & Bound; Dual prices (search for similar items in EconPapers)
Date: 2021
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/S2214716021000051
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:oprepe:v:8:y:2021:i:c:s2214716021000051

DOI: 10.1016/j.orp.2021.100182

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().