[37] | 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; |
---|