On exact solution approaches for bilevel quadratic 0–1 knapsack problem
On exact solution approaches for bilevel quadratic 0–1 knapsack problem
复制标题
双层二次0-1背包问题的精确求解方法
DOI：
10.1007/s10479-018-2970-4
复制
发表时间：
2018
影响因子：
4.8
通讯作者：
Pasiliao, Eduardo L.
中科院分区：
文献类型：
--
作者：
Zenarosa, Gabriel Lopez;Prokopyev, Oleg A.;Pasiliao, Eduardo L.
我们考虑两层二次背包问题(BQKP)，它是一个模型，其中领导者为追随者分配预算，追随者解决一个二次0-1背包问题。BQKP推广了Dempe和Richter(CENT EUR J Oper Res 8(2)：93-107,2000)提出的两层背包问题，其中跟随者解决了一个线性的0-1背包问题。基于QKP边界的动态规划扩展和分支回溯算法，提出了一种BQKP问题的精确解方法。我们将我们的方法与使用优化求解器在两个阶段计算的两阶段方法进行了比较：它首先计算所有可行领导者决策的跟随者的值函数，然后将BQKP的值函数重新表示为混合整数二次约束规划。我们的计算实验表明，我们的方法比商业最先进的优化软件包计算的两阶段方法要好。
We consider the bilevel quadratic knapsack problem (BQKP) that model settings where a leader appropriates a budget for a follower, who solves a quadratic 0–1 knapsack problem. BQKP generalizes the bilevel knapsack problem introduced by Dempe and Richter (Cent Eur J Oper Res 8(2):93–107, 2000), where the follower solves a linear 0–1 knapsack problem. We present an exact-solution approach for BQKP based on extensions of dynamic programs for QKP bounds and the branch-and-backtrack algorithm. We compare our approach against a two-phase method computed using an optimization solver in both phases: it first computes the follower’s value function for all feasible leader’s decisions, and then solves a single-level, value-function reformulation of BQKP as a mixed-integer quadratically constrained program. Our computational experiments show that our approach for solving BQKP outperforms the two-phase method computed by a commercial state-of-the-art optimization software package.
登录
查看更多内容
影响因子：
2.2
作者：
B. Beheshti;O. Prokopyev;E. Pasiliao
通讯作者：
E. Pasiliao
影响因子：
2.7
作者：
Osman Y. Özaltın;O. Prokopyev;A. Schaefer
通讯作者：
A. Schaefer
具有随机右侧的两阶段整数规划：超加性对偶方法
影响因子：
2.7
作者：
N. Kong;A. Schaefer;Brady Hunsaker
通讯作者：
Brady Hunsaker
0-1 二次背包问题：基于 t 线性化的精确方法
DOI：
10.1137/110820762
发表时间：
2012
期刊：
SIAM J. Optim.
影响因子：
--
作者：
C. Rodrigues;Dominique Quadri;P. Michelon;Serigne Gueye
通讯作者：
Serigne Gueye
关于两阶段随机整数规划的约束聚合和值函数的注释
影响因子：
1.1
作者：
Andrew C. Trapp;O. Prokopyev
通讯作者：
O. Prokopyev