[Csdp] inequality-constraints vs. equality-constraints

[Brian Borchers]

On Wed, Jan 20, 2010 at 7:27 AM,  <angelika.wiegele at uni-klu.ac.at> wrote:
> we use csdp within a branch-and-bound code for solving quadratic integer
> programs and experienced the following problem:
>
> if the sdp, for instance, includes the two constraints:
>
> x_{1,3} + x_{3,3} \le a
> x_{1,3} + x_{3,3} \ge a
>
> then csdp terminates with error code 3. whereas when we formulate the
> constraint as
>
> x_{1,3} + x_{3,3} = a
>
> instead, csdp has no problem and terminates successfully.
> since constraints are not added at once, we would prefer to formulate them as
> in the first version, i.e., an equality-constraint as two
> inequality-constraints.
>
> does somebody know, what the reason for this behaviour of csdp is?
> and has anybody an idea how to overcome this problem without merging the
> inequality- into equality-constraints?
>
> best, angelika
>
> _______________________________________________
> Csdp mailing list
> Csdp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/csdp
>
>

Unfortunately, direct emails from my address (borchers at nmt.edu) to
angelika.wiegele at uni-klu.ac.at are being blocked by a spam filter at
uni-klu.  I hope that this reply gets to you through the mailing
list...

When you formulate the problem as

> x_{1,3} + x_{3,3} \le a
> x_{1,3} + x_{3,3} \ge a

you introduce two nonnegative slack variables which are forced to 0 in
order to satisfy the two constraints.  This degeneracy appears to be
causing some kind of numerical problem.  The return code of 3
indicates that CSDP found a solution, but it didn't quite satisfy the
required primal and dual feasibility.  It would be interesting to see
whether primal or
dual feasibility (or both) were problems here.  Assuming that you're
just using the solution to get a bound for use within your branch and
bound code, it may be that you only need dual feasibility
(respectively primal feasibility), so it might be that this isn't
really a problem for your code anyway.

I would be interested in experimenting with one of these problems to
see what's going on in more detail.  Could you send me one of these as
a .dat-s file?  (You could have your code write out the problem using
the write_prob() routine.)