source: proiecte/pmake3d/make3d_original/Make3dSingleImageStanford_version0.1/third_party/opt/yalmip/htmldata/integer.htm @ 37

Last change on this file since 37 was 37, checked in by (none), 14 years ago

Added original make3d
File size: 6.7 KB
Line 
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&nbsp;<a href="reference.htm#binvar">binvar</a>&nbsp;and
28    <a href="reference.htm#intvar">
29    intvar</a>. The resulting objects are essentially&nbsp;<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);
35y = 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));
46F = set(z &gt;= 0) + set(x &lt;= 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);
56y = sdpvar(n,m);
57z = x + y + trace(x) + sum(sum(y));
58F = set(z &gt;= 0) + set(x &lt;= 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]';
86t = (0:0.02:2*pi)';
87x = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)];
88y = x*a+(-4+8*rand(length(x),1));
89
90a_hat = intvar(6,1);
91
92residuals = y-x*a_hat;
93bound = sdpvar(length(residuals),1);
94F = set(-bound &lt;= residuals &lt;= bound);
95solvesdp(F,sum(bound));
96a_L1 = double(a_hat);
97solvesdp([],residuals'*residuals);
98a_L2 = double(a_hat);
99bound = sdpvar(1,1);
100F = set(-bound &lt;= residuals &lt;= bound);
101solvesdp(F,bound);
102a_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);
120A = randn(15,5);
121b = rand(15,1)*10;
122
123obj = sum(x) + sum((x-3).^4); % 4th order objective
124solvesdp(set(A*x &lt; b) + set(integer(x)),obj,sdpsettings('bnb.solver','fmincon'))
125<font color="#000000">
126* Starting YALMIP integer branch &amp; bound.
127* Lower solver   : fmincon-standard
128* Upper solver   : rounder
129* Max iterations : 300
130
131Warning : The relaxed problem may be nonconvex. This means
132that the branching process not is guaranteed to find a
133globally optimal solution, since the lower bound can be
134invalid. 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>&nbsp;</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>
Note: See TracBrowser for help on using the repository browser.