1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> |
---|
2 | <html> |
---|
3 | |
---|
4 | <head> |
---|
5 | <meta http-equiv="Content-Language" content="en-us"> |
---|
6 | <title>YALMIP Example : Integer programming</title> |
---|
7 | <meta http-equiv="Content-Type" content="text/html; charset=windows-1251"> |
---|
8 | <meta content="Microsoft FrontPage 6.0" name="GENERATOR"> |
---|
9 | <meta name="ProgId" content="FrontPage.Editor.Document"> |
---|
10 | <link href="yalmip.css" type="text/css" rel="stylesheet"> |
---|
11 | <base target="_self"> |
---|
12 | </head> |
---|
13 | |
---|
14 | <body leftMargin="0" topMargin="0"> |
---|
15 | |
---|
16 | <div align="left"> |
---|
17 | |
---|
18 | <table border="0" cellpadding="4" cellspacing="3" style="border-collapse: collapse" bordercolor="#000000" width="100%" align="left" height="100%"> |
---|
19 | <tr> |
---|
20 | <td width="100%" align="left" height="100%" valign="top"> |
---|
21 | <h2>Integer programming</h2> |
---|
22 | <hr noShade SIZE="1"> |
---|
23 | <p>YALMIP supports several mixed integer programming solvers, but also comes |
---|
24 | with built-in module for mixed integer programming, based on a simple |
---|
25 | standard branch-and-bound algorithm. </p> |
---|
26 | <h3>Mixed integer conic programming</h3> |
---|
27 | <p>Defining binary and integer variables is done with the commands <a href="reference.htm#binvar">binvar</a> and |
---|
28 | <a href="reference.htm#intvar"> |
---|
29 | intvar</a>. The resulting objects are essentially <a href="reference.htm#sdpvar">sdpvar</a> |
---|
30 | objects with implicit constraints.</p> |
---|
31 | <table cellPadding="10" width="100%"> |
---|
32 | <tr> |
---|
33 | <td class="xmpcode"> |
---|
34 | <pre>x = intvar(n,m); |
---|
35 | y = binvar(n,m);</pre> |
---|
36 | </td> |
---|
37 | </tr> |
---|
38 | </table> |
---|
39 | <p>Objects with integer variables are manipulated as standard |
---|
40 | <a href="reference.htm#sdpvar"> |
---|
41 | sdpvar</a> objects.</p> |
---|
42 | <table cellPadding="10" width="100%"> |
---|
43 | <tr> |
---|
44 | <td class="xmpcode"> |
---|
45 | <pre>z = x + y + trace(x) + sum(sum(y)); |
---|
46 | F = set(z >= 0) + set(x <= 0);</pre> |
---|
47 | </td> |
---|
48 | </tr> |
---|
49 | </table> |
---|
50 | <p>In the code above, integrality was imposed by using integer and binary |
---|
51 | variables. An equivalent alternative is to use explicit constraints.</p> |
---|
52 | <table cellPadding="10" width="100%"> |
---|
53 | <tr> |
---|
54 | <td class="xmpcode"> |
---|
55 | <pre>x = sdpvar(n,m); |
---|
56 | y = sdpvar(n,m); |
---|
57 | z = x + y + trace(x) + sum(sum(y)); |
---|
58 | F = set(z >= 0) + set(x <= 0) + set(integer(x)) + set(binary(y));</pre> |
---|
59 | </td> |
---|
60 | </tr> |
---|
61 | </table> |
---|
62 | <p>Note that we use non-strict inequalities. This is highly recommended when |
---|
63 | working with integer models since, see the <a href="faq.htm#reallystrict"> |
---|
64 | FAQ</a>.</p> |
---|
65 | <p>The global integer solver can be applied to any kind of conic program |
---|
66 | that can be defined within the YALMIP framework, and defining integer programs is as simple as |
---|
67 | defining standard problems. The supported integer solvers are |
---|
68 | <a href="solvers.htm#glpk"> |
---|
69 | GLPK</a>, <a href="solvers.htm#cplex"> |
---|
70 | CPLEX</a>, <a href="solvers.htm#xpress"> |
---|
71 | XPRESS</a> and <a href="solvers.htm#mosek">MOSEK</a>. In addition to these |
---|
72 | solvers, YALMIP comes with an internal branch-and-bound solver, |
---|
73 | called <code>'bnb'</code>, to |
---|
74 | be used together with any continuous solver. Hence, it is possible to |
---|
75 | (globally) solve |
---|
76 | mixed integer linear/quadratic/second order cone/semidefinite/geometric programs |
---|
77 | in YALMIP. Note |
---|
78 | that the internal branch-and-bound algorithm is rudimentary and useful only for small problems. See the help-text on <code>'bnb'</code> for |
---|
79 | more information on this solver.</p> |
---|
80 | <p>As an example, let us return to the <a href="linearregression.htm">linear regression problem</a>. Solving the same problems, but looking for |
---|
81 | integer solutions can be done by changing one line of code</p> |
---|
82 | <table cellPadding="10" width="100%"> |
---|
83 | <tr> |
---|
84 | <td class="xmpcode"> |
---|
85 | <pre>a = [1 2 3 4 5 6]'; |
---|
86 | t = (0:0.02:2*pi)'; |
---|
87 | x = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)]; |
---|
88 | y = x*a+(-4+8*rand(length(x),1)); |
---|
89 | |
---|
90 | a_hat = intvar(6,1); |
---|
91 | |
---|
92 | residuals = y-x*a_hat; |
---|
93 | bound = sdpvar(length(residuals),1); |
---|
94 | F = set(-bound <= residuals <= bound); |
---|
95 | solvesdp(F,sum(bound)); |
---|
96 | a_L1 = double(a_hat); |
---|
97 | solvesdp([],residuals'*residuals); |
---|
98 | a_L2 = double(a_hat); |
---|
99 | bound = sdpvar(1,1); |
---|
100 | F = set(-bound <= residuals <= bound); |
---|
101 | solvesdp(F,bound); |
---|
102 | a_Linf = double(a_hat);</pre> |
---|
103 | </td> |
---|
104 | </tr> |
---|
105 | </table> |
---|
106 | <h3>General mixed integer programming</h3> |
---|
107 | <p>The mixed integer programming solvers discussed above are all guaranteed |
---|
108 | to find a globally optimal solution, if one exists. The built-in |
---|
109 | branch-and-bound module can be applied also to general nonlinear programs |
---|
110 | with discrete data. The difference is that there is no guarantee on global |
---|
111 | optimality for these problems. It can however be a useful strategy for |
---|
112 | finding reasonably good feasible solutions to mixed integer nonlinear |
---|
113 | programs. For the following example to work, you need to have |
---|
114 | <a href="solvers.htm#fmincon">fmincon</a>, or possibly |
---|
115 | <a href="solvers.htm#PENBMI">PENBMI</a>, installed on your system.</p> |
---|
116 | <table cellPadding="10" width="100%" id="table1"> |
---|
117 | <tr> |
---|
118 | <td class="xmpcode"> |
---|
119 | <pre>x = sdpvar(5,1); |
---|
120 | A = randn(15,5); |
---|
121 | b = rand(15,1)*10; |
---|
122 | |
---|
123 | obj = sum(x) + sum((x-3).^4); % 4th order objective |
---|
124 | solvesdp(set(A*x < b) + set(integer(x)),obj,sdpsettings('bnb.solver','fmincon')) |
---|
125 | <font color="#000000"> |
---|
126 | * Starting YALMIP integer branch & bound. |
---|
127 | * Lower solver : fmincon-standard |
---|
128 | * Upper solver : rounder |
---|
129 | * Max iterations : 300 |
---|
130 | |
---|
131 | Warning : The relaxed problem may be nonconvex. This means |
---|
132 | that the branching process not is guaranteed to find a |
---|
133 | globally optimal solution, since the lower bound can be |
---|
134 | invalid. Hence, do not trust the bound or the gap... |
---|
135 | Node Upper Gap(%) Lower Open |
---|
136 | 1 : -6.400E+001 44.57 -1.155E+002 2 |
---|
137 | 2 : -6.400E+001 44.57 -1.155E+002 3 |
---|
138 | 3 : -6.400E+001 41.27 -1.090E+002 4 |
---|
139 | 4 : -6.400E+001 41.27 -1.090E+002 5 |
---|
140 | 5 : -6.400E+001 36.58 -1.009E+002 6 |
---|
141 | 6 : -6.400E+001 36.58 -1.009E+002 7 |
---|
142 | 7 : -6.400E+001 33.44 -9.615E+001 8 |
---|
143 | 8 : -6.400E+001 33.44 -9.615E+001 9 |
---|
144 | 9 : -6.400E+001 30.38 -9.193E+001 8 |
---|
145 | 10 : -6.400E+001 30.38 -9.193E+001 9 |
---|
146 | 11 : -7.800E+001 13.85 -9.054E+001 6 |
---|
147 | 12 : -7.800E+001 13.85 -9.054E+001 5 |
---|
148 | 13 : -7.800E+001 12.19 -8.883E+001 4 |
---|
149 | 14 : -7.800E+001 12.19 -8.883E+001 3 |
---|
150 | 15 : -7.800E+001 10.41 -8.706E+001 2 |
---|
151 | 16 : -7.800E+001 10.41 -8.706E+001 3 |
---|
152 | 17 : -7.800E+001 0.60 -7.847E+001 2 |
---|
153 | 18 : -7.800E+001 0.60 -7.847E+001 1 |
---|
154 | 19 : -7.800E+001 0.60 -7.847E+001 0 |
---|
155 | + 19 Finishing. Cost: -78</font></pre> |
---|
156 | <pre> </pre> |
---|
157 | </td> |
---|
158 | </tr> |
---|
159 | </table> |
---|
160 | <p>For an additional example, check out the <a href="geometric.htm#migp"> |
---|
161 | mixed integer geometric programming example</a></td> |
---|
162 | </tr> |
---|
163 | </table> |
---|
164 | |
---|
165 | </div> |
---|
166 | |
---|
167 | </body> |
---|
168 | |
---|
169 | </html> |
---|