-
Notifications
You must be signed in to change notification settings - Fork 1
/
knapsack.m
74 lines (70 loc) · 1.88 KB
/
knapsack.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
% -------------------------------------------------------------------------
% SAFFRON toolbox: https://github.com/decenter2021/SAFFRON
% AUTHORS: Leonardo Pedroso, Pedro Batista, Markos Papageorgiou, and Elias
% Kosmatopoulos
% LICENSE: MIT License
% If you use SAFFRON, reference the publication below
% Pedroso, L., Batista, P., Papageorgiou, M. and Kosmatopoulos, E., 2022
% [not published yet]
% -------------------------------------------------------------------------
%% knapsack - Description
% This function solves the knapsack problem
% Implementation of algorithm in [1]
% Input: - a,b,c,d as defined in [2]
% Output: - x: knapsack solution
function x = knapsack(a,b,c,d)
% Variables
aux = a-d.*b;
aux = [aux;a];
y = sort(aux);
n = length(a);
% 0. Initialization
if c<0 || c>sum(b)
x = NaN;
return;
else
l = 1;
r = 2*n;
R = 0;
L = sum(b);
end
% 1. Test for bracketing
while true
if r-l == 1
% 5. Interpolate
lambda = y(l) + (y(r)-y(l))*(c-L)/(R-L);
break;
else
m = floor((l+r)/2);
end
% 3. Compute new value
aux = (a-y(m))./d;
for i = 1:n
aux(i) = max(min(aux(i),b(i)),0);
end
C = sum(aux);
% 4. Update
if C == c
lambda = y(m);
break;
elseif C > c
l = m;
L = C;
else
r = m;
R = C;
end
end
x = zeros(n,1);
for i = 1:n
x(i) = max(min((a(i)-lambda)/d(i),b(i)),0);
end
end
%% References
% [1] Helgason, R., Kennington, J., Lall, H., 1980. A polynomially bounded
% algorithm for a singly constrained quadratic program. Math. Program.
% 18 (1), 338-343.
% [2] Pedroso, L. and Batista, P., 2021. Decentralized store-and-forward
% based strategies for the signal control problem in large-scale congested
% urban road networks. Transportation Research Part C: Emerging
% Technologies, 132, p.103412. doi:10.1016/j.trc.2021.103412.