solver return infeasible for a solvable problem

[zying0827]

Hello,

When I input the attached ISDP problem, the solver returned "infeasible". However, there are some feasible solutions to this problem, such as x_2, x_5, and x_11 are 1, and 0 for the rest variables. What's more interesting is that when I add the 53th constraint x_5>=1, the solver returns "optimal solution found", which is unreasonable since adding constraints will not enlarge the solution space. Could you please provide some guidance? Thanks in advance.

The following is the content of test.dat-s, which is a binary SDP problem.

15
2
4 -52
0 1 2 0 1 2 0 0 0 0 0 0 0 0 0 
0 1 1 1 -17834.694217631153
0 1 1 2 165.3057823691147
0 1 1 3 -291.61806365614996
0 1 1 4 -1.0
0 1 2 2 -1834.694217630329
0 1 2 3 -291.61806365605264
0 1 2 4 -2.0
0 1 3 3 -52.08506915514171
0 1 3 4 -1.0
0 1 4 4 -4.0
1 1 1 1 160006.66555574554
1 1 1 2 -1664.7225462411939
1 1 1 3 416.5972337945695
2 1 1 1 -12000.666555574515
2 1 1 2 332.9445092482388
2 1 1 3 -83.3194467589139
3 1 1 1 18667.555407432712
3 1 1 2 -332.9445092482388
3 1 1 3 83.3194467589139
4 1 1 2 -13329.445092483375
4 1 2 2 46685.5524079284
4 1 2 3 833.1944675886523
5 1 1 2 2665.889018496675
5 1 2 2 -1334.4442592900086
5 1 2 3 -166.63889351773045
6 1 1 2 -2665.889018496675
6 1 2 2 4001.9996667218993
6 1 2 3 166.63889351773045
7 1 1 2 -33327.77870354647
8 1 1 2 6665.555740709295
9 1 1 2 -6665.555740709295
10 1 1 2 6665.555740709295
11 1 1 2 -1333.1111481418588
12 1 1 2 1333.1111481418588
13 1 1 2 -6665.555740709295
14 1 1 2 1333.1111481418588
15 1 1 2 -1333.1111481418588
1 2 1 1 1
1 2 2 2 -1
0 2 2 2 -1
2 2 3 3 1
2 2 4 4 -1
0 2 4 4 -1
3 2 5 5 1
3 2 6 6 -1
0 2 6 6 -1
4 2 7 7 1
4 2 8 8 -1
0 2 8 8 -1
5 2 9 9 1
5 2 10 10 -1
0 2 10 10 -1
6 2 11 11 1
6 2 12 12 -1
0 2 12 12 -1
7 2 13 13 1
1 2 14 14 1
7 2 14 14 -1
4 2 15 15 1
7 2 15 15 -1
7 2 16 16 1
1 2 16 16 -1
4 2 16 16 -1
0 2 16 16 -1
8 2 17 17 1
1 2 18 18 1
8 2 18 18 -1
5 2 19 19 1
8 2 19 19 -1
8 2 20 20 1
1 2 20 20 -1
5 2 20 20 -1
0 2 20 20 -1
9 2 21 21 1
1 2 22 22 1
9 2 22 22 -1
6 2 23 23 1
9 2 23 23 -1
9 2 24 24 1
1 2 24 24 -1
6 2 24 24 -1
0 2 24 24 -1
10 2 25 25 1
2 2 26 26 1
10 2 26 26 -1
4 2 27 27 1
10 2 27 27 -1
10 2 28 28 1
2 2 28 28 -1
4 2 28 28 -1
0 2 28 28 -1
11 2 29 29 1
2 2 30 30 1
11 2 30 30 -1
5 2 31 31 1
11 2 31 31 -1
11 2 32 32 1
2 2 32 32 -1
5 2 32 32 -1
0 2 32 32 -1
12 2 33 33 1
2 2 34 34 1
12 2 34 34 -1
6 2 35 35 1
12 2 35 35 -1
12 2 36 36 1
2 2 36 36 -1
6 2 36 36 -1
0 2 36 36 -1
13 2 37 37 1
3 2 38 38 1
13 2 38 38 -1
4 2 39 39 1
13 2 39 39 -1
13 2 40 40 1
3 2 40 40 -1
4 2 40 40 -1
0 2 40 40 -1
14 2 41 41 1
3 2 42 42 1
14 2 42 42 -1
5 2 43 43 1
14 2 43 43 -1
14 2 44 44 1
3 2 44 44 -1
5 2 44 44 -1
0 2 44 44 -1
15 2 45 45 1
3 2 46 46 1
15 2 46 46 -1
6 2 47 47 1
15 2 47 47 -1
15 2 48 48 1
3 2 48 48 -1
6 2 48 48 -1
0 2 48 48 -1
1 2 49 49 1
2 2 49 49 1
3 2 49 49 1
0 2 49 49 1
1 2 50 50 -1
2 2 50 50 -1
3 2 50 50 -1
0 2 50 50 -1
4 2 51 51 1
5 2 51 51 1
6 2 51 51 1
0 2 51 51 1
4 2 52 52 -1
5 2 52 52 -1
6 2 52 52 -1
0 2 52 52 -1
*This is constraint (x_5 >= 1)
*5 2 53 53 1
*0 2 53 53 1
*INTEGER
*1
*2
*3
*4
*5
*6
*7
*8
*9
*10
*11
*12
*13
*14
*15

[pfetsch]

When I use Mosek as SDP-solver, the solution of the first SDP fails with status "UNKNOWN". SCIP-SDP then tries to solve a penalty formulation, for which Mosek says that one cannot drive the penalty term to 0. But it is only very slightly off, with a value of 1.45e-05 (the tolerance is 1e-5). Thus, SCIP-SDP decides that the relaxation and thus the problem is infeasible.

When I use DSDP, the problem is solved without problem. The same happens when I only solve LPs.

I am not sure why Mosek cannot solve the relaxation. However, the matrices are "not nice" in the sense that they contain values of very different magnitude (160006.6 vs. -1).

[zying0827]

Hello,

I have been working on the SCIP-SDP solver based on Mosek for weeks, and I have found that the solution quality is quite unstable. The optimality cannot be guaranteed even for small problems with fewer than 100 binary variables. Sometimes, the solver takes thousands of seconds without finding the optimal solution, or even returns infeasible. When the integer constraints are relaxed, the objective value of the SDP can be larger than the original MISDP, or even become infeasible. Do you have any suggestions for improving the solution quality? Thank you for your help.

[pfetsch]

This is a difficult question. Here are some ideas what you might do:

• Try to scale the problem such that the coefficients has similar sizes. It will depend on your application whether this will work.
• Check whether the relaxed problem (and its dual) have a Slater point. Sometimes there are implied equations that you can manage to remove such that the feasible sets have an interior. Usually, interior point solvers (like Mosek) are quite sensitive to this. It might happen in your case (without looking into the details), that fixing the integer variables removes some of the difficulties, e.g., after fixing and removing the variable, the problem might have a Slater point. But again, whether you can improve the situation will most likely depend on your problem.

I you have an idea of what SCIP-SDP could do to improve the situation, please let me know.

[zying0827]

Hello,

Thanks for your reply and suggestion. I will keep trying to improve my formulation to enhance stability.
Could you please help me with the following error message? I have no idea whether there is something wrong with my MISDP model. Thanks

SCIP-SDP> read test.dat-s

read problem <test.dat-s>
============

Number of conflict constraints generated:               1
Number of CMIR-strengthened conflict constraints:       0
Remove 45 zero objective coefficients.
original problem has 50 variables (0 bin, 50 int, 0 impl, 0 cont) and 200 constraints
    190 constraints of type <linear>
     10 constraints of type <SDP>
Reading Time: 0.01
SCIP-SDP> optimize

LP Solver <Soplex 7.1.2>: barrier convergence tolerance cannot be set -- tolerance of SCIP and LP solver may differ
LP Solver <Soplex 7.1.2>: fastmip setting not available -- SCIP parameter has no effect
LP Solver <Soplex 7.1.2>: number of threads settings not available -- SCIP parameter has no effect
transformed problem has 50 variables (0 bin, 50 int, 0 impl, 0 cont) and 200 constraints
    190 constraints of type <linear>
     10 constraints of type <SDP>

original problem has 860 active (8.6%) nonzeros and 860 (8.6%) check nonzeros

presolving:
(round 1, fast)       0 del vars, 60 del conss, 0 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 90 clqs
(round 2, medium)     5 del vars, 60 del conss, 0 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 80 clqs
(round 3, fast)       5 del vars, 70 del conss, 0 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 80 clqs
(round 4, exhaustive) 5 del vars, 70 del conss, 0 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 120 upgd conss, 0 impls, 80 clqs
(round 5, exhaustive) 5 del vars, 190 del conss, 40 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 120 upgd conss, 0 impls, 80 clqs
Added 1400 linear constraints based on variable bounds from 2 x 2 SDP-minors.
(round 6, exhaustive) 5 del vars, 190 del conss, 1440 add conss, 100 chg bounds, 0 chg sides, 0 chg coeffs, 120 upgd conss, 0 impls, 80 clqs
(round 7, fast)       5 del vars, 1590 del conss, 1440 add conss, 100 chg bounds, 600 chg sides, 0 chg coeffs, 120 upgd conss, 0 impls, 80 clqs
   (0.0s) probing cycle finished: starting next cycle
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present (symcode time: 0.00)
clique table cleanup detected 0 bound changes

presolved problem has 570 active (25.3333%) nonzeros and 570 (25.3333%) check nonzeros

presolving (8 rounds: 8 fast, 5 medium, 4 exhaustive):
 5 deleted vars, 1590 deleted constraints, 1440 added constraints, 100 tightened bounds, 0 added holes, 600 changed sides, 0 changed coefficients
 0 implications, 380 cliques
presolved problem has 45 variables (45 bin, 0 int, 0 impl, 0 cont) and 50 constraints
     40 constraints of type <and>
     10 constraints of type <SDP>
transformed objective value is always integral (scale: 5)
Presolving Time: 0.03

 time | node  | left  |SDP iter|SDP it/n|SDP  uns|mem/heur|mdpt |vars |cons |rows |cuts |confs|  dualbound   | primalbound  |  gap   | compl.
p 0.1s|     1 |     0 |      0 |      - |   --   | vbounds|   0 |  45 |  51 |   0 |   0 |   0 | 0.000000e+00 | 2.000000e+01 |    Inf | unknown
  0.1s|     1 |     2 |     14 |   14.0 |   0.00%|  5263k |   0 |  45 |  52 |  80 |   0 |   0 | 1.296223e-01 | 2.000000e+01 |  Large | unknown
scipsdp: <path>/scipsdp-4.3.0/src/scipsdp/relax_sdp.c:1066: computeConflictCut: Assertion `SCIPisFeasEQ(scip, primalval, primalmatrices[b][col * blocksize + row])' failed.
Aborted (core dumped)

Attached is the input file (in the dat-s format)
test.txt
:

[zying0827]

It seems that the above error has been fixed when I restarted my computer. But do you have any thoughts on this error and the reason behind it? Thanks

[pfetsch]

The assert is a double check that the dual solution of the problem that is solved has a symmetric matrix. The failure might be a numerical problem. Since, I cannot reproduce, I can't tell.

[zying0827]

Received with thanks. The solution quality did improve after I normalized the coefficients of LMIs. I will perform more experiment and check if there are further questions related to the solver. Thanks!

[zying0827]

Hello,
Could you please try running the following two files? Both files contain the same 50 binary variables, 190 linear constraints. The only difference is that test1.dat-s includes an LMI constraint, while test2.dat-s duplicates the LMI (so the two LMIs in test2.dat-s are identical). SCIP-SDP can find an optimal value of 15 for test1.dat-s, but it crashes when processing test2.dat-s. It would be greatly appreciated if you can reproduce the error and investigate the cause, so that I can understand how to improve my model. Thank you in advance.

Here are the two input files (in dat-s format):
test1.txt
test2.txt

[pfetsch]

Sorry, but I cannot reproduce this. Both problems give me a value of 15 (without crashing).

[zying0827]

Alright, thank you for your help.