logic.htm
来自「optimization toolbox」· HTM 代码 · 共 499 行 · 第 1/2 页
HTM
499 行
</tr>
</table>
<p>Finally, we solve the problem by maximizing the second
coordinate of x.</p>
<table cellPadding="10" width="100%" id="table8">
<tr>
<td class="xmpcode">
<pre>solvesdp(F,-x(2));
double(x)
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 4.5949
4.2701</font></pre>
<pre>double([inp1 inp2 inp3 inp4])
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 0 0 0 1</font></pre>
</td>
</tr>
</table>
<p>The <b>IFF</b> is overloaded as equality, hence the
following code generates the same problem.</p>
<table cellPadding="10" width="100%" id="table12">
<tr>
<td class="xmpcode">
<pre>F = set(inp1 | inp2 | inp3 | inp4);
F = F + set(inp1 == (A1*x < b1));
F = F + set(inp2 == (A2*x < b2));
F = F + set(inp3 == (A3*x < b3));
F = F + set(inp4 == (A4*x < b4));
solvesdp(F,-x(2));</pre>
</td>
</tr>
</table>
<p>We should mention that it is not necessary to
use the <b>IFF</b> operator in this problem, the <b>
IMPLIES</b> operator suffice. The implies operator
should be used when possible, since it for most cases is
more efficiently implemented (less number of additional
binary variables) than the <b>IFF</b> function. As a
general comment, if you want to play it safe, stay away
from <b>IFF</b> as much as possible, and don't use <b>
IMPLIES</b> with the first argument being anything else
than a binary variable. </p>
<table cellPadding="10" width="100%" id="table10">
<tr>
<td class="xmpcode">
<pre>F = set(inp1 | inp2 | inp3 | inp4);
F = F + set(implies(inp1,A1*x < b1));
F = F + set(implies(inp2,A2*x < b2));
F = F + set(implies(inp3,A3*x < b3));
F = F + set(implies(inp4,A4*x < b4));
solvesdp(F,-x(2));
double(x)
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 4.5949
4.2701</font></pre>
</td>
</tr>
</table>
<p>The <b>IFF</b> operator is used internally to construct
mixed constraints involving <b>OR</b>.
With this functionality, we can solve the previous
problem using a more intuitive code (albeit
possibly inefficient since it will use <b>IFF</b>
instead of <b>IMPLIES</b>).</p>
<table cellPadding="10" width="100%" id="table11">
<tr>
<td class="xmpcode">
<pre>F = set( (A1*x < b1) | (A2*x < b2) | (A3*x < b3) | (A4*x < b4));
solvesdp(F,-x(2));
double(x)
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 4.5949
4.2701</font></pre>
</td>
</tr>
</table>
<h3><a name="bounds"></a>Improving the Big-M formulation</h3>
<p>The conversion from logic constraints to mixed integer
constraints is done in YALMIP using a standard big-M
formulation. By default, YALMIP uses a big-M value of
10<sup>4</sup>, but it is recommended to add constraints
to improve this. By explicitly adding bounds on
variables, YALMIP can exploit these bounds to compute a
reasonably small big-M constant.</p>
<table cellPadding="10" width="100%" id="table13">
<tr>
<td class="xmpcode">
<pre>x = sdpvar(2,1);
F = set( (A1*x < b1) | (A2*x < b2) | (A3*x < b3) | (A4*x < b4));
F = F + set(-100 < x < 100);
solvesdp(F,-x(2));
double(x)
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 4.5949
4.2701</font></pre>
</td>
</tr>
</table>
<p>Adding bounds can significantly improve the strength of
the relaxations and corresponding reduction of
computation time. Hence, if you know, or can estimate,
lower and upper bounds, let YALMIP know this. If you
fail to add bounds, YALMIP will issue warnings.</p>
<h3><a name="sudoku"></a>Sudoku example</h3>
<p>There are not many logic constructions implemented at
the moment, but
they can easily be added if you make a request. As an
example, the logic constraint <b>ALLDIFFERENT</b> was
easily implemented as a nonlinear operator. Let us use
the operator to solve a Sudoku game.</p>
<table cellPadding="10" width="100%" id="table15">
<tr>
<td class="xmpcode">
<pre>S = [0,0,1,9,0,0,0,0,8;6,0,0,0,8,5,0,3,0;0,0,7,0,6,0,1,0,0;...
0,3,4,0,9,0,0,0,0;0,0,0,5,0,4,0,0,0;0,0,0,0,1,0,4,2,0;...
0,0,5,0,7,0,9,0,0;0,1,0,8,4,0,0,0,7;7,0,0,0,0,9,2,0,0];</pre>
<pre>ans =</pre>
<pre>0 0 1 9 0 0 0 0 8
6 0 0 0 8 5 0 3 0
0 0 7 0 6 0 1 0 0
0 3 4 0 9 0 0 0 0
0 0 0 5 0 4 0 0 0
0 0 0 0 1 0 4 2 0
0 0 5 0 7 0 9 0 0
0 1 0 8 4 0 0 0 7
7 0 0 0 0 9 2 0 0</pre>
</td>
</tr>
</table>
<p>In case you have missed out on the Sudoko hype, the
goal is to replace the zeros with numbers between 1 to
9, keeping elements in all rows and columns different,
and keeping all elements in the 9 3x3 blocks different.</p>
<p>Let us create our 9x9 integer decision variable and define
the basic constraints</p>
<table cellPadding="10" width="100%" id="table16">
<tr>
<td class="xmpcode">
<pre>M = intvar(9,9,'full');
fixed = find(S);
F = set(1 <= M <= 9) + set(M(fixed) == S(fixed));</pre>
</td>
</tr>
</table>
<p>We add the logic constraints using some MATLAB indexing
tricks, add some redundant cuts, and solve the problem (The
solution time
depends highly on your MILP solver.
<a href="solvers.htm#cplex">CPLEX</a> solves
this problem in roughly 0.1 seconds, while
<a href="solvers.htm#glpk">GLPK</a> fails.)</p>
<table cellPadding="10" width="100%" id="table17">
<tr>
<td class="xmpcode">
<pre>for i = 1:3
for j = 1:3
block = M(find(kron(full(sparse(i,j,1,3,3)),ones(3))));
F = F + set(alldifferent(block));
end
end
for i = 1:9
F = F + set(alldifferent(M(i,:)));
F = F + set(alldifferent(M(:,i)));
end
F = F + set(sum(M,1) == 45) + set(sum(M,2) == 45);</pre>
<pre>solvesdp(F);</pre>
</td>
</tr>
</table>
<p>Note that this model of the Sudoku game is pretty
weak. A much better model can be obtained by using a
scheme based on having a binary for each possible value
for each element. This is left as an exercise.</p>
<h3><a name="index"></a>Variable index variables</h3>
<p>By combining the framework for
<a href="extoperators.htm">nonlinear operators</a> and
logic programming, YALMIP allows variable indices. The
following silly example picks out the two highest
indices of elements in a vector <b>p</b> smaller than or
equal to three.</p>
<table cellPadding="10" width="100%" id="table14">
<tr>
<td class="xmpcode">
<pre>sdpvar i j
x = sdpvar(1,8);
p = [0 1 7 2 3 4 3 20];
solvesdp(set(x == p)+set(x([i j]) <= 3)+set(i~=j),-i-j);
double([i j])
<font color="#000000">ans =</font></pre>
<pre><font color="#000000"> 5 7</font></pre>
</td>
</tr>
</table>
<h3>Behind the scenes</h3>
<p>The logic <b>AND</b> and <b>OR</b> operators are implemented using
<a href="extoperators.htm">nonlinear operators</a>. As an
example, to implement the <b>OR</b>
operator <b>z=or(x,y)</b> for binary <b>x</b> and <b>y</b>, the simple code below is
sufficient (the code actually used is slightly different
to improve performance for expressions with more than
two variables,
but the idea is the same). The first constraint ensures that <b>z</b> is
false if both <b>x</b> and <b>y</b> are false, the two
following constraints ensure that <b>z</b> is true if <b>x</b>
or <b>y</b> is true, while the last constraint constrains
<b>z</b> to be a binary (true/false) variable.</p>
<table cellPadding="10" width="100%">
<tr>
<td class="xmpcode">
<pre>function varargout = or(varargin)
% SDPVAR/OR
switch class(varargin{1})
case 'char'
z = varargin{2};
x = varargin{3};
y = varargin{4};
varargout{1} = set(x + y >= z) + set(z >= x) + set(z >= y) + set(binary(z));
varargout{2} = struct('convexity','milp','monotonicity','milp','definiteness','milp');
varargout{3} = [x y];</pre>
<pre> case 'sdpvar'
x = varargin{1};
y = varargin{2};
varargout{1} = yalmip('addextendedvariable','or',varargin{:});</pre>
<pre> otherwise
end</pre>
</td>
</tr>
</table>
<p>The operators <b>IFF</b> and <b>IMPLIES</b> are just
standard implementations of big-M reformulations,
implemented in the
<a href="extoperators.htm">nonlinear operators</a>
framework.</td>
</tr>
</table>
</div>
</body>
</html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?