1 | % ************************************************************************* |
---|
2 | % Bound strengthening, here is where we actually solve LPs |
---|
3 | % ************************************************************************* |
---|
4 | function [p,feasible,lower] = lpbmitighten(p,lower,upper,lpsolver) |
---|
5 | |
---|
6 | % Construct problem with only linear terms |
---|
7 | % and add cuts from lower/ upper bounds |
---|
8 | |
---|
9 | p_test = p; |
---|
10 | p_test.F_struc = p.lpcuts; |
---|
11 | p_test.K.l = size(p.lpcuts,2); |
---|
12 | p_test.K.f = 0; |
---|
13 | p_test.K.s = 0; |
---|
14 | p_test.K.q = 0; |
---|
15 | if ~isnan(lower) |
---|
16 | p_test.F_struc = [-(p.lower-abs(p.lower)*0.01)+p.f p_test.c';p_test.F_struc]; |
---|
17 | end |
---|
18 | if upper < inf |
---|
19 | p_test.F_struc = [upper+abs(upper)*0.01-p.f -p_test.c';p_test.F_struc]; |
---|
20 | end |
---|
21 | if ~isempty(p.bilinears) |
---|
22 | p_test = addmcgormick(p_test); |
---|
23 | end |
---|
24 | |
---|
25 | %aa = p_test.F_struc(7,:);; |
---|
26 | %p_test.F_struc = [];%p_test.F_struc(7,:); |
---|
27 | |
---|
28 | p_test.K.l = size(p_test.F_struc,1); |
---|
29 | p_test.F_struc = [p.F_struc(1:1:p.K.f,:);p_test.F_struc]; |
---|
30 | p_test.K.f = p.K.f; |
---|
31 | |
---|
32 | feasible = 1; |
---|
33 | |
---|
34 | % Perform reduction on most violating approximations at current solution |
---|
35 | if p.options.bmibnb.lpreduce ~= 1 |
---|
36 | n = ceil(max(p.options.bmibnb.lpreduce*length(p_test.linears),1)); |
---|
37 | res = zeros(length(p.lb),1); |
---|
38 | for i = 1:size(p.bilinears,1) |
---|
39 | res(p.bilinears(i,2)) = res(p.bilinears(i,2)) + abs( p.x0(p.bilinears(i,1))-p.x0(p.bilinears(i,2)).*p.x0(p.bilinears(i,3))); |
---|
40 | res(p.bilinears(i,3)) = res(p.bilinears(i,3)) + abs( p.x0(p.bilinears(i,1))-p.x0(p.bilinears(i,2)).*p.x0(p.bilinears(i,3))); |
---|
41 | end |
---|
42 | res = res(p.linears); |
---|
43 | [ii,jj] = sort(abs(res)); |
---|
44 | jj = jj(end-n+1:end); |
---|
45 | else |
---|
46 | jj=1:length(p_test.linears); |
---|
47 | end |
---|
48 | |
---|
49 | j = 1; |
---|
50 | while feasible & j<=length(jj) |
---|
51 | i = p_test.linears(jj(j)); |
---|
52 | if abs(p.ub(i)-p.lb(i)>0.1) |
---|
53 | p_test.c = eyev(length(p_test.c),i); |
---|
54 | |
---|
55 | output = feval(lpsolver,p_test); |
---|
56 | if output.problem == 0 |
---|
57 | if p_test.lb(i) < output.Primal(i)-1e-5 |
---|
58 | p_test.lb(i) = output.Primal(i); |
---|
59 | p_test = updateonenonlinearbound(p_test,i); |
---|
60 | end |
---|
61 | p_test.c = -p_test.c; |
---|
62 | output = feval(lpsolver,p_test); |
---|
63 | if output.problem == 0 |
---|
64 | if p_test.ub(i) > output.Primal(i)+1e-5 |
---|
65 | p_test.ub(i) = output.Primal(i); |
---|
66 | p_test = updateonenonlinearbound(p_test,i); |
---|
67 | end |
---|
68 | end |
---|
69 | if output.problem == 1 |
---|
70 | feasible = 0; |
---|
71 | end |
---|
72 | end |
---|
73 | if output.problem == 1 |
---|
74 | feasible = 0; |
---|
75 | end |
---|
76 | end |
---|
77 | j = j + 1; |
---|
78 | end |
---|
79 | p_test = clean_bounds(p_test); |
---|
80 | p.lb = p_test.lb; |
---|
81 | p.ub = p_test.ub; |
---|