<br><br><div class="gmail_quote">On Tue, May 17, 2011 at 6:32 AM, Sebastian Berckey <span dir="ltr"><<a href="mailto:sebastian.berckey@tu-dortmund.de">sebastian.berckey@tu-dortmund.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
We want to use CSDP in a branch & bound program for calculating bounds<br>
for integer quadratic<br>
programs using SDP-relaxation. In this context we want to use<br>
inequality constraints.<br>
<br>
We can't find any hint how to use inequalities with csdp 6.1.1, though<br>
it seems that older<br>
versions of csdp provided that feature. So is it still possible to use<br>
inequality constraints with csdp 6.1.1? We thought about introducing<br>
slack variables ourselves, but don't know how to ensure the<br>
nonnegativity of them in csdp.<br>
<br></blockquote><div><br>As you've noted, early versions of CSDP had direct support for
inequality constraints, because slack variables would have needed to be
included in a single large matrix block. Once support for block
structured problems was in the code there really wasn't any advantage to
including direct support for inequality constraints, since slack
variables can easily be put into a diagonal block. That's why this
feature was removed from CSDP. <br><br clear="all"></div></div>The way to do this is by introducing slack variables. The slack variables are stored in a separate block of the block diagonal matrix, and that block should be a "diagonal block" rather than a normal matrix block. If you're familiar with SeDuMi, this means putting the slacks into K.l.<br>
<br>For example, suppose that X is a two by two matrix variable and your problem is:<br> <br> max X(1,1)+2*X(2,2)<br> s.t. X(1,1)+X(2,2) <= 5<br> X(1,1)+X(1,2)+X(2,1)+X(2,2) <= 10<br> X is positive semidefinite. <br>
<br>Introduce slack variables X(3,3) and X(4,4) and write this as:<br> <br> max X(1,1)+2*X(2,2)<br>
s.t. X(1,1)+X(2,2) + X(3,3) = 5<br> X(1,1)+X(1,2)+X(2,1)+X(2,2) + X(4,4) = 10<br>
X is positive semidefinite. <br><br>The constraint that X is PSD ensures that X(3,3)>=0 and X(4,4)>=0. (The diagonal elements of a PSD matrix are always nonnegative.) <br> <br>You could simply set this problem up as a problem involving a 4 by 4 PSD matrix X. For this tiny example, that would work well, but for a very large problem with thousands of inequality constraints, that would be very inefficient. <br>
<br>You can improve this formulation by treating X as a block diagonal matrix consisting of a 2x2 positive semidefinite block and a 2 element diagonal block. That is:<br> <br> X=[X11 X12 0 0;<br> X21 X22 0 0;<br>
0 0 X33 0;<br> 0 0 0 X44];<br><br>This block diagonal formulation saves storage, and also saves CPU time in solving the problem.<br><br>If you aren't already familiar with it, please read the description of the SDPA sparse problem format at <br>
<br> <a href="http://euler.nmt.edu/~brian/sdplib/FORMAT">http://euler.nmt.edu/~brian/sdplib/FORMAT</a><br><br>The above example can be formulated in SDPA sparse format (with comments added) as <br> <br>2 # 2 constraints<br>
2 # 2 blocks<br>2 -2 # a 2x2 block and 2 nonnegative variables. <br>5.0 10.0 # the right hand side, b.<br>
0 1 1 1 1.0 # C(1,1)=1.0<br>0 1 2 2 2.0 # C(2,2)=2.0<br>1 1 1 1 1.0 # A1(1,1)=1.0<br>1 1 2 2 1.0 # A1(2,2)=1.0<br>
1 2 1 1 1.0 # A1(3,3)=1.0 this is the (1,1) element of block 2.<br>2 1 1 1 1.0 # A2(1,1)=1.0<br>2 1 1 2 1.0 # A2(1,2)=1.0 it's implied that A2(2,1)=1.0.<br>
2 1 2 2 1.0 # A2(2,2)=1.0<br>2 2 2 2 1.0 # A2(4,4)=1.0 this is the 2,2 element of block 2.<br> <br>The solution is:<br><br>2.000000000000005773e+00 5.434131996250952711e-09 # y=[2 0]<br>
1 1 1 1 1.000000007247586531e+00 # Z(1,1)=1.0<br>1 1 1 2 5.434131996250952711e-09 # Z(1,2)=0.0<br>1 1 2 2 7.247586593901009102e-09 # Z(2,2)=0.0<br>
1 2 1 1 2.000000001813454720e+00 # Z(3,3)=2.0<br>1 2 2 2 7.247580806281872776e-09 # Z(4,4)=0.0<br>2 1 1 1 3.623790669100295336e-08 # X(1,1)=0.0<br>
2 1 1 2 -2.759429726476486466e-08 # X(1,2)=0.0<br>2 1 2 2 4.999999945643135213e+00 # X(2,2)=5.0<br>2 2 1 1 1.811895773879953503e-08 # X(3,3)=0.0<br>
2 2 2 2 5.000000073307552917e+00 # X(4,4)=5.0<br><br>I hope this example has been helpful to you. Please let me know if you have any questions about the example. <br><br>I assume that you're going to be using the C subroutine interface to CSDP to solve your problems. I would strongly encourage you to use the latest trunk version of CSDP from the subversion repository, because it has improved error checking that will help you to find any problems with the data structures that you pass into CSDP. <br>
<br><br>-- <br>Brian Borchers <a href="mailto:borchers@nmt.edu" target="_blank">borchers@nmt.edu</a><br>Department of Mathematics <a href="http://www.nmt.edu/%7Eborchers/" target="_blank">http://www.nmt.edu/~borchers/</a><br>
New Mexico Tech Phone: (575) 322-2592<br>Socorro, NM 87801 FAX: (575) 835-5366<br>