.png){kind=icon}
.png){kind=icon}
Return
A combinatorial algorithm for inverse continuous quadratic knapsack problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s00186-026-00924-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The quadratic knapsack problem is a special case of the quadratic program with exactly one linear constraint. In this paper, we consider the inverse continuous quadratic knapsack problem, where coefficients concerning the objective function are modified at minimum cost to make a prespecified feasible solution optimal with respect to the perturbed problem. Based on an optimality criterion, we induce a linear program for the inverse continuous quadratic knapsack problem. Then, a univariate optimization problem is derived based on the special structure of the induced problem. Moreover, we prove that the single variable objective function is piecewise linear and convex. This helps us develop an O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} algorithm for the corresponding problem by applying a binary search approach. Finally, computational results on a randomized dataset demonstrate the superiority of our algorithm compared with the classical method applied to the corresponding linear programming model.
Keywords:
Quadratic knapsack problem
Inverse optimization
Linear program
Convex
Journal
M
IF:
1.2
Papers:
24
Citations:
0