1 | clc |
---|
2 | echo on |
---|
3 | |
---|
4 | % YALMIP supports mixed integer (LP/QP/SOCP/SDP) programming. If no |
---|
5 | % specialized MIP solver is installed, such as GLPK or CPLEX, an internal |
---|
6 | % branch-and bound scheme is applied, using the installed continuous |
---|
7 | % solvers for solving the node problems. |
---|
8 | % |
---|
9 | % Notice that this is a very rudimentary branch-and-bound solver, so |
---|
10 | % for performance and anything but small academic examples, a dedicated |
---|
11 | % integer solver is required. |
---|
12 | % |
---|
13 | % Type help bnb to obtain inforamtion about the solver. |
---|
14 | % |
---|
15 | % Let us test the internal solver on MILP, MIQP, MISOCP and MISDPP |
---|
16 | |
---|
17 | pause |
---|
18 | yalmip('clear') |
---|
19 | clc |
---|
20 | |
---|
21 | % We are given a noisy Toeplitz matrix P, and the goal is to find an |
---|
22 | % integer Toeplitz matrix Z minimizing sum_i sum_j |Pij-Zij| |
---|
23 | % |
---|
24 | % Obviously, this is a MILP problem. |
---|
25 | % |
---|
26 | pause % Strike any key to continue. |
---|
27 | |
---|
28 | % Create a noisy Toeplitz matrix |
---|
29 | n = 5; |
---|
30 | P = toeplitz(randn(n,1)*100)+randn(n,n)*5 |
---|
31 | pause % Strike any key to continue. |
---|
32 | |
---|
33 | % Define an integer Toeplitz matrix |
---|
34 | Z = intvar(n,n,'toeplitz'); |
---|
35 | pause % Strike any key to continue. |
---|
36 | |
---|
37 | % Introduce a variable to deal with the absolute values |
---|
38 | % note : P is not symmetric so constraints are automatically |
---|
39 | % interpreted as element-wise. |
---|
40 | t = sdpvar(n,n,'full'); |
---|
41 | F = set(-t < P-Z < t); |
---|
42 | pause % Strike any key to continue. |
---|
43 | |
---|
44 | % Solve (using the internal branch-and-bound solver |
---|
45 | % Turn on display in branching, but turn off display in |
---|
46 | % the local LP-solver |
---|
47 | solvesdp(F,sum(sum(t)),sdpsettings('solver','bnb','verbose',2)); |
---|
48 | pause % Strike any key to continue. |
---|
49 | |
---|
50 | % Check the result |
---|
51 | P |
---|
52 | double(Z) |
---|
53 | pause |
---|
54 | |
---|
55 | clc |
---|
56 | % As an alternative, let us solve the corrsponding MIQP |
---|
57 | % problem where we minimize sum_i sum_j |Pij-Zij|^2 |
---|
58 | pause |
---|
59 | |
---|
60 | % Define the residuals |
---|
61 | e = P(:)-Z(:) |
---|
62 | % and optimize |
---|
63 | solvesdp([],e'*e,sdpsettings('solver','bnb','verbose',2)); |
---|
64 | pause % Strike any key to continue. |
---|
65 | |
---|
66 | % Check the result |
---|
67 | P |
---|
68 | double(Z) |
---|
69 | pause |
---|
70 | |
---|
71 | |
---|
72 | clc |
---|
73 | % Finally, let us do things the hard way, and formulate |
---|
74 | % the problem a mixed integer second order cone problem! |
---|
75 | pause |
---|
76 | |
---|
77 | % Define the residuals |
---|
78 | e = P(:)-Z(:) |
---|
79 | % and a bound |
---|
80 | t = sdpvar(1,1); |
---|
81 | % and optimize the bound t subject to ||e||<t |
---|
82 | solvesdp(set(cone(e,t)),t,sdpsettings('solver','bnb','verbose',2)); |
---|
83 | pause % Strike any key to continue. |
---|
84 | |
---|
85 | % Check the result |
---|
86 | P |
---|
87 | double(Z) |
---|
88 | pause |
---|
89 | |
---|
90 | |
---|
91 | clc |
---|
92 | % ...or why not a plain stupid implementation using |
---|
93 | % mixed integer semi-definite programming! |
---|
94 | pause |
---|
95 | |
---|
96 | % A Shur complement gives a LMI |
---|
97 | F = set([t e';e eye(length(e))]>0); |
---|
98 | solvesdp(F,t,sdpsettings('solver','bnb','verbose',2)); |
---|
99 | pause % Strike any key to continue. |
---|
100 | |
---|
101 | % Check the result |
---|
102 | P |
---|
103 | double(Z) |
---|
104 | pause |
---|
105 | echo off |
---|
106 | |
---|
107 | |
---|