.png){kind=icon}
返回
A Novel Core-Based Optimization Framework for Binary Integer Programs-the Multidemand Multidimesional Knapsack Problem as a Test Problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.orp.2021.100182.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 bestknown solutions and better average solutions for most of the solved instances.
Keyword:
Combinatorial optimization
Core problem
Multidemand multidimensional knapsack problem
Branch & Bound
Dual prices
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.7
论文数:
288
被引数:
951
机构
引用论文
Recovery of salinity gradient energy in desalination plants by reverse electrodialysis.png)
DesalinationOAAI
DesalinationIF0
OAAI分享收藏分享收藏
Alginate surfactant derivatives as an ecofriendly corrosion inhibitor for carbon steel in acidic environmentsRSC Advances
RSC AdvancesIF0
PREAI
分享收藏
查看更多内容