67 #include "scip/cons_linear.h" 68 #include "scip/cons_nonlinear.h" 69 #include "scip/cons_quadratic.h" 70 #include "scip/cons_soc.h" 71 #include "scip/cons_linear.h" 72 #include "scip/scip_cons.h" 73 #include "scip/scip.h" 83 #define CONSHDLR_NAME "SDP" 84 #define CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd" 86 #define CONSHDLRRANK1_NAME "SDPrank1" 87 #define CONSHDLRRANK1_DESC "rank 1 SDP constraints" 89 #define CONSHDLR_SEPAPRIORITY +1000000 90 #define CONSHDLR_ENFOPRIORITY -2000000 91 #define CONSHDLR_CHECKPRIORITY -2000000 92 #define CONSHDLR_PROPFREQ 1 93 #define CONSHDLR_SEPAFREQ 1 94 #define CONSHDLR_EAGERFREQ 100 96 #define CONSHDLR_MAXPREROUNDS -1 97 #define CONSHDLR_DELAYSEPA FALSE 98 #define CONSHDLR_NEEDSCONS TRUE 100 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE 101 #define CONSHDLR_PROPTIMING SCIP_PROPTIMING_BEFORELP 103 #define PARSE_STARTSIZE 1 104 #define PARSE_SIZEFACTOR 10 106 #define DEFAULT_PROPUPPERBOUNDS TRUE 107 #define DEFAULT_PROPUBPRESOL TRUE 108 #define DEFAULT_PROPTIGHTENBOUNDS TRUE 109 #define DEFAULT_PROPTBPROBING FALSE 110 #define DEFAULT_TIGHTENBOUNDSCONT FALSE 111 #define DEFAULT_TIGHTENMATRICES FALSE 112 #define DEFAULT_TIGHTENBOUNDS TRUE 113 #define DEFAULT_DIAGGEZEROCUTS FALSE 114 #define DEFAULT_DIAGZEROIMPLCUTS TRUE 115 #define DEFAULT_TWOMINORLINCONSS FALSE 116 #define DEFAULT_TWOMINORPRODCONSS FALSE 117 #define DEFAULT_TWOMINORVARBOUNDS TRUE 118 #define DEFAULT_QUADCONSRANK1 TRUE 119 #define DEFAULT_UPGRADEQUADCONSS FALSE 120 #define DEFAULT_UPGRADEKEEPQUAD FALSE 121 #define DEFAULT_MAXNVARSQUADUPGD 1000 122 #define DEFAULT_RANK1APPROXHEUR FALSE 123 #define DEFAULT_SEPARATEONECUT FALSE 124 #define DEFAULT_CUTSTOPOOL TRUE 125 #define DEFAULT_SPARSIFYCUT FALSE 126 #define DEFAULT_SPARSIFYFACTOR 0.1 127 #define DEFAULT_SPARSIFYTARGETSIZE -1 128 #define DEFAULT_MULTIPLESPARSECUTS FALSE 129 #define DEFAULT_MAXNSPARSECUTS 0 130 #define DEFAULT_ENFORCESDP FALSE 131 #define DEFAULT_ONLYFIXEDINTSSDP FALSE 132 #define DEFAULT_ADDSOCRELAX FALSE 133 #define DEFAULT_USEDIMACSFEASTOL FALSE 134 #define DEFAULT_GENERATEROWS TRUE 137 #define DEFAULT_NTHREADS 1 141 #define DEFAULT_RECOMPUTESPARSEEV FALSE 142 #define DEFAULT_RECOMPUTEINITIAL FALSE 143 #define DEFAULT_EXACTTRANS FALSE 161 SCIP_Real maxrhsentry;
164 SCIP_Bool addedquadcons;
166 SCIP_VAR** matrixvar;
167 SCIP_Real* matrixval;
168 SCIP_Real* matrixconst;
170 SCIP_Real tracebound;
171 SCIP_Bool allmatricespsd;
172 SCIP_Bool initallmatricespsd;
176 struct SCIP_ConshdlrData
179 SCIP_Bool diaggezerocuts;
182 SCIP_Bool propupperbounds;
183 SCIP_Bool propubpresol;
184 SCIP_Bool tightenboundscont;
185 SCIP_Bool proptightenbounds;
186 SCIP_Bool proptbprobing;
187 SCIP_Bool tightenmatrices;
188 SCIP_Bool tightenbounds;
189 SCIP_Bool diagzeroimplcuts;
190 SCIP_Bool twominorlinconss;
191 SCIP_Bool twominorprodconss;
192 SCIP_Bool twominorvarbounds;
193 SCIP_Bool quadconsrank1;
194 SCIP_Bool upgradequadconss;
195 SCIP_Bool upgradekeepquad;
196 SCIP_Bool separateonecut;
197 SCIP_Bool cutstopool;
198 SCIP_Bool sparsifycut;
199 SCIP_Real sparsifyfactor;
200 int sparsifytargetsize;
201 SCIP_Bool multiplesparsecuts;
203 SCIP_Bool enforcesdp;
204 SCIP_Bool onlyfixedintssdp;
205 SCIP_Bool addsocrelax;
206 int maxnvarsquadupgd;
207 SCIP_Bool triedlinearconss;
208 SCIP_Bool triedvarbounds;
209 SCIP_Bool rank1approxheur;
210 SCIP_Bool generaterows;
215 SCIP_VAR** quadconsvars;
220 SCIP_CONSHDLRDATA* sdpconshdlrdata;
221 SCIP_RANDNUMGEN* randnumgen;
222 SCIP_RELAX* relaxsdp;
223 SCIP_Bool usedimacsfeastol;
224 SCIP_Real dimacsfeastol;
225 SCIP_Bool recomputesparseev;
226 SCIP_Bool recomputeinitial;
227 SCIP_Bool exacttrans;
237 SCIP_Real* rowmatrix,
248 assert( rowmatrix != NULL );
249 assert( colmatrix != NULL );
251 for (i = 0; i < rows; ++i)
253 for (j = 0; j < cols; ++j)
255 act = rowmatrix[i*cols + j];
256 colmatrix[j*rows + i] = act;
274 assert( blocksize >= 0 );
275 assert( matrix != NULL );
276 assert( scale != NULL );
278 for (r = 0; r < blocksize; r++)
280 for (c = 0; c < blocksize; c++)
283 matrix[r * blocksize + c] *= scale[r];
303 assert( symMat != NULL );
304 assert( fullMat != NULL );
307 for (i = 0; i < size; i++)
309 for (j = 0; j <= i; j++)
312 fullMat[i*size + j] = symMat[ind];
313 fullMat[j*size + i] = symMat[ind];
327 SCIP_CONSDATA* consdata,
338 assert( consdata != NULL );
339 assert( matrix != NULL );
341 nvars = consdata->nvars;
342 blocksize = consdata->blocksize;
345 for (i = 0; i < (blocksize * (blocksize + 1))/2; ++i)
349 for (i = 0; i < nvars; i++)
351 yval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
352 if ( ! SCIPisZero(scip, yval) )
354 for (j = 0; j < consdata->nvarnonz[i]; ++j)
360 for (j = 0; j < consdata->constnnonz; ++j)
370 SCIP_CONSDATA* consdata,
372 SCIP_Real* fullmatrix
383 assert( scip != NULL );
384 assert( consdata != NULL );
385 assert( fullmatrix != NULL );
387 nvars = consdata->nvars;
388 blocksize = consdata->blocksize;
391 for (i = 0; i < blocksize * blocksize; ++i)
395 for (i = 0; i < nvars; i++)
399 yval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
400 if ( ! SCIPisZero(scip, yval) )
402 for (j = 0; j < consdata->nvarnonz[i]; ++j)
404 r = consdata->row[i][j];
405 c = consdata->col[i][j];
406 aval = consdata->val[i][j];
409 fullmatrix[r * blocksize + c] += yval * aval;
412 fullmatrix[r * blocksize + c] += yval * aval;
413 fullmatrix[c * blocksize + r] += yval * aval;
420 for (j = 0; j < consdata->constnnonz; ++j)
422 r = consdata->constrow[j];
423 c = consdata->constcol[j];
424 aval = consdata->constval[j];
427 fullmatrix[r * blocksize + c] -= aval;
430 fullmatrix[r * blocksize + c] -= aval;
431 fullmatrix[c * blocksize + r] -= aval;
443 SCIP_CONSDATA* consdata
446 SCIP_Real* constmatrix;
447 SCIP_Real** matrices;
454 assert( scip != NULL );
455 assert( consdata != NULL );
457 if ( consdata->matrixvar != NULL )
460 consdata->nsingle = 0;
461 blocksize = consdata->blocksize;
464 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
467 SCIP_CALL( SCIPallocBufferArray(scip, &matrices, consdata->nvars) );
468 for (i = 0; i < consdata->nvars; ++i)
470 SCIP_CALL( SCIPallocBufferArray(scip, &matrices[i], blocksize * blocksize) );
474 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->matrixvar, blocksize * (blocksize+1)/2) );
475 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->matrixval, blocksize * (blocksize+1)/2) );
476 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->matrixconst, blocksize * (blocksize+1)/2) );
478 for (s = 0; s < blocksize; ++s)
480 for (t = 0; t <= s; ++t)
482 SCIP_VAR* var = NULL;
486 pos = s * blocksize + t;
488 for (i = 0; i < consdata->nvars; ++i)
490 if ( ! SCIPisZero(scip, matrices[i][pos]) )
494 var = consdata->vars[i];
495 val = matrices[i][pos];
503 if ( i >= consdata->nvars )
505 consdata->matrixvar[cnt] = var;
506 consdata->matrixval[cnt] = val;
507 consdata->matrixconst[cnt] = constmatrix[pos];
512 consdata->matrixvar[cnt] = NULL;
513 consdata->matrixval[cnt] = SCIP_INVALID;
514 consdata->matrixconst[cnt] = SCIP_INVALID;
519 assert( cnt == blocksize * (blocksize + 1)/2 );
521 SCIPfreeBufferArray(scip, &constmatrix);
522 for (i = consdata->nvars - 1; i >= 0; --i)
523 SCIPfreeBufferArray(scip, &matrices[i]);
524 SCIPfreeBufferArray(scip, &matrices);
526 if ( SCIPgetSubscipDepth(scip) == 0 )
527 SCIPdebugMsg(scip,
"Number of entries depending on a single variable: %d.\n", consdata->nsingle);
536 SCIP_CONSHDLRDATA* conshdlrdata,
539 SCIP_Bool printreason,
543 SCIP_CONSDATA* consdata;
544 SCIP_Real* fullmatrix = NULL;
545 SCIP_Real eigenvalue;
549 assert( scip != NULL );
550 assert( cons != NULL );
551 assert( result != NULL );
553 consdata = SCIPconsGetData(cons);
554 assert( consdata != NULL );
555 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLR_NAME) == 0 );
556 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLRRANK1_NAME) == 0 );
557 blocksize = consdata->blocksize;
559 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize) );
565 if ( conshdlrdata->sdpconshdlrdata->usedimacsfeastol )
567 assert( conshdlrdata->dimacsfeastol != SCIP_INVALID );
568 tol = conshdlrdata->dimacsfeastol;
571 tol = SCIPfeastol(scip);
573 if ( eigenvalue >= -tol )
574 *result = SCIP_FEASIBLE;
577 *result = SCIP_INFEASIBLE;
580 SCIPinfoMessage(scip, NULL,
"SDP-constraint <%s> violated: non psd matrix (eigenvalue %f).\n", SCIPconsGetName(cons), eigenvalue);
581 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
586 SCIPupdateSolConsViolation(scip, sol, -eigenvalue, (-eigenvalue) / (1.0 + consdata->maxrhsentry));
588 SCIPfreeBufferArray(scip, &fullmatrix);
597 SCIP_CONSHDLRDATA* conshdlrdata,
603 SCIP_CONSDATA* consdata;
604 SCIP_Real* matrix = NULL;
605 SCIP_Real* fullmatrix = NULL;
606 SCIP_Real eigenvalue;
608 SCIP_RESULT resultSDPtest;
613 SCIP_Real submatrix[4];
614 SCIP_Real largestminev = 0.0;
616 assert( cons != NULL );
617 assert( result != NULL );
619 consdata = SCIPconsGetData(cons);
620 assert( consdata != NULL );
622 blocksize = consdata->blocksize;
624 resultSDPtest = SCIP_INFEASIBLE;
628 if ( resultSDPtest == SCIP_INFEASIBLE )
630 SCIPerrorMessage(
"Try to check for a matrix to be rank 1 even if the matrix is not psd.\n");
635 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, (blocksize * (blocksize+1))/2 ) );
636 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize ) );
652 if ( SCIPisFeasEQ(scip, 0.1 * eigenvalue, 0.0) )
659 for (i = 0; i < blocksize; ++i)
661 for (j = 0; j < i; ++j)
671 if ( eigenvalue > largestminev )
673 largestminev = eigenvalue;
680 assert( ind1 > 0 || ind2 > 0 );
681 assert( SCIPisFeasPositive(scip, largestminev) );
684 consdata->maxevsubmat[0] = ind1;
685 consdata->maxevsubmat[1] = ind2;
688 SCIPfreeBufferArray(scip, &fullmatrix);
689 SCIPfreeBufferArray(scip, &matrix);
703 SCIP_CONSDATA* consdata;
709 assert( cons != NULL );
711 assert( vAv != NULL );
713 consdata = SCIPconsGetData(cons);
714 assert( consdata != NULL );
716 assert( j < consdata->nvars );
718 for (i = 0; i < consdata->nvarnonz[j]; i++)
720 r = consdata->row[j][i];
721 c = consdata->col[j][i];
723 s += v[c] * consdata->val[j][i] * v[r];
727 s += 2.0 * v[c] * consdata->val[j][i] * v[r];
744 SCIP_CONSDATA* consdata;
748 consdata = SCIPconsGetData(cons);
749 assert( consdata != NULL );
752 for (i = 0; i < consdata->constnnonz; i++)
754 if ( REALABS(consdata->constval[i]) > max )
755 max = REALABS(consdata->constval[i]);
758 consdata->maxrhsentry = max;
773 SCIP_Real* fullmatrix,
777 SCIP_Real convergencetol,
778 SCIP_Real* eigenvector,
780 SCIP_Real* eigenvalue
791 assert( scip != NULL );
792 assert( blocksize > 0 );
793 assert( fullmatrix != NULL );
794 assert( vector != NULL );
795 assert( sparsity > 0 && sparsity <= blocksize );
796 assert( eigenvector != NULL );
797 assert( eigenvalue != NULL );
799 SCIPdebugMsg(scip,
"Executing truncatedPowerMethod\n");
801 SCIP_CALL( SCIPallocBufferArray(scip, &indices, blocksize) );
802 SCIP_CALL( SCIPallocBufferArray(scip, &sortedev, blocksize) );
803 SCIP_CALL( SCIPallocBufferArray(scip, &oldev, blocksize) );
808 for (i = 0; i < blocksize; i++)
809 eigenvector[i] = vector[i];
811 while ( neweig - oldeig > convergencetol )
817 for (i = 0; i < blocksize; i++)
818 oldev[i] = eigenvector[i];
823 for (i = 0; i < blocksize; i++)
826 sortedev[i] = REALABS(eigenvector[i]);
829 SCIPsortDownRealInt(sortedev, indices, blocksize);
832 for (i = sparsity; i < blocksize; i++)
834 eigenvector[indices[i]] = 0.0;
835 support[indices[i]] = 0;
840 for (i = 0; i < sparsity; i++)
842 norm += eigenvector[indices[i]] * eigenvector[indices[i]];
843 support[indices[i]] = 1;
847 for (i = 0; i < sparsity; i++)
848 eigenvector[indices[i]] /= norm;
853 for (i = 0; i < blocksize; i++)
854 neweig += eigenvector[i] * oldev[i];
857 SCIPfreeBufferArray(scip, &oldev);
858 SCIPfreeBufferArray(scip, &sortedev);
859 SCIPfreeBufferArray(scip, &indices);
861 *eigenvalue = neweig;
875 SCIP_CONSHDLR* conshdlr,
877 SCIP_CONSDATA* consdata,
880 SCIP_Real* fullconstmatrix,
881 SCIP_Real* eigenvector,
889 char cutname[SCIP_MAXSTRLEN];
890 SCIP_CONSHDLRDATA* conshdlrdata;
892 SCIP_Real norm = 0.0;
900 assert( scip != NULL );
901 assert( conshdlr != NULL );
902 assert( fullconstmatrix != NULL );
903 assert( eigenvector != NULL );
904 assert( vector != NULL );
905 assert( success != NULL );
906 assert( result != NULL );
907 assert( *result != SCIP_CUTOFF );
911 conshdlrdata = SCIPconshdlrGetData(conshdlr);
912 assert( conshdlrdata != NULL );
915 SCIP_CALL( SCIPallocBufferArray(scip, &idx, blocksize) );
916 for (j = 0; j < blocksize; ++j)
920 assert( conshdlrdata->randnumgen != NULL );
921 SCIPrandomPermuteIntArray(conshdlrdata->randnumgen, idx, 0, blocksize);
924 if ( conshdlrdata->sdpconshdlrdata->sparsifytargetsize > 0 )
925 size = conshdlrdata->sdpconshdlrdata->sparsifytargetsize;
927 size = MAX(10, (
int) conshdlrdata->sdpconshdlrdata->sparsifyfactor * consdata->nvars);
930 if ( size > blocksize )
932 SCIPdebugMsg(scip,
"Eigenvector cut is not sparsified since desired sparsity %d is larger than SDP blocksize %d.\n", size, blocksize);
936 assert( size <= blocksize );
939 SCIP_CALL( SCIPallocClearBufferArray(scip, &ev, blocksize) );
940 for (j = 0; j < size; ++j)
942 ev[idx[j]] = eigenvector[j];
943 norm += eigenvector[j] * eigenvector[j];
947 if ( SCIPisFeasZero(scip, norm) )
949 SCIPfreeBufferArray(scip, &ev);
950 SCIPfreeBufferArray(scip, &idx);
956 for (j = 0; j < size; ++j)
962 for (j = 0; j < blocksize; ++j)
963 lhs += ev[j] * vector[j];
966 for (j = 0; j < consdata->nvars; ++j)
970 if ( SCIPisFeasZero(scip, coef) )
973 vars[cnt] = consdata->vars[j];
977 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
978 if ( conshdlrdata->sdpconshdlrdata->generaterows )
980 SCIP_Bool infeasible;
983 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, cutname, lhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
984 SCIP_CALL( SCIPaddVarsToRow(scip, row, cnt, vars, vals) );
987 if ( SCIPisCutEfficacious(scip, sol, row) )
989 #ifdef SCIP_MORE_DEBUG 990 SCIP_CALL( SCIPprintRow(scip, row, NULL) );
992 SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
993 SCIP_CALL( SCIPresetConsAge(scip, cons) );
995 if ( conshdlrdata->sdpconshdlrdata->cutstopool )
997 SCIP_CALL( SCIPaddPoolCut(scip, row) );
1000 assert( *result != SCIP_CONSADDED );
1002 *result = SCIP_CUTOFF;
1004 *result = SCIP_SEPARATED;
1007 SCIP_CALL( SCIPreleaseRow(scip, &row) );
1013 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, cutname, cnt, vars, vals, lhs, SCIPinfinity(scip),
1014 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE) );
1015 SCIP_CALL( SCIPaddCons(scip, newcons) );
1016 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1018 assert( *result != SCIP_SEPARATED );
1019 *result = SCIP_CONSADDED;
1023 SCIPfreeBufferArray(scip, &ev);
1024 SCIPfreeBufferArray(scip, &idx);
1037 SCIP_CONSHDLR* conshdlr,
1039 SCIP_CONSDATA* consdata,
1042 SCIP_Real* fullmatrix,
1043 SCIP_Real* fullconstmatrix,
1044 SCIP_Real* eigenvector,
1055 char cutname[SCIP_MAXSTRLEN];
1056 SCIP_CONSHDLRDATA* conshdlrdata;
1057 SCIP_Real* fullmatrixcopy;
1058 SCIP_Real* modmatrix;
1059 SCIP_Real* submatrix;
1060 SCIP_Real* sparseev;
1061 SCIP_Real* liftedev;
1063 SCIP_Real convergencetol;
1064 SCIP_Real eigenvalue;
1067 SCIP_Real lhs = 0.0;
1075 assert( scip != NULL );
1076 assert( conshdlr != NULL );
1077 assert( fullmatrix != NULL );
1078 assert( fullconstmatrix != NULL );
1079 assert( eigenvector != NULL );
1080 assert( maxncuts > 0 );
1081 assert( vector != NULL );
1082 assert( ncuts != NULL );
1083 assert( result != NULL );
1084 assert( *result != SCIP_CUTOFF );
1089 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1090 assert( conshdlrdata != NULL );
1092 SCIPdebugMsg(scip,
"Executing addMultipleSparseCuts.\n");
1095 if ( conshdlrdata->sdpconshdlrdata->sparsifytargetsize > 0 )
1096 size = conshdlrdata->sdpconshdlrdata->sparsifytargetsize;
1098 size = MAX(10, (
int) conshdlrdata->sdpconshdlrdata->sparsifyfactor * consdata->nvars);
1101 if ( size > blocksize )
1103 SCIPdebugMsg(scip,
"No sparse eigenvector cuts produced since desired sparsity %d is larger than SDP blocksize %d.\n", size, blocksize);
1107 assert( size <= blocksize );
1110 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrixcopy, blocksize * blocksize) );
1111 for (i = 0; i < blocksize * blocksize; i++)
1112 fullmatrixcopy[i] = fullmatrix[i];
1116 SCIPdebugMsg(scip,
"Largest eigenvalue of A(y): %.15g\n", maxeig);
1119 SCIP_CALL( SCIPallocBufferArray(scip, &modmatrix, blocksize * blocksize) );
1120 for (i = 0; i < blocksize; i++)
1122 for (j = 0; j < blocksize; j++)
1125 modmatrix[i * blocksize + j] = maxeig - fullmatrix[i * blocksize + j];
1127 modmatrix[i * blocksize + j] = -fullmatrix[i * blocksize + j];
1132 SCIP_CALL( SCIPallocBufferArray(scip, &submatrix, size * size) );
1133 SCIP_CALL( SCIPallocBufferArray(scip, &liftedev, blocksize) );
1134 SCIP_CALL( SCIPallocBufferArray(scip, &support, blocksize) );
1135 SCIP_CALL( SCIPallocBufferArray(scip, &sparseev, size) );
1136 SCIP_CALL( SCIPallocBufferArray(scip, &minev, blocksize) );
1139 convergencetol = 1e-6;
1140 SCIP_CALL(
truncatedPowerMethod(scip, blocksize, modmatrix, eigenvector, size, convergencetol, liftedev, support, &eigenvalue) );
1142 SCIPdebugMsg(scip,
"Smallest sparse eigenvalue computed by TPower: %.15g\n", maxeig - eigenvalue);
1146 scalar = maxeig - eigenvalue;
1148 if ( ! SCIPisFeasNegative(scip, scalar) )
1150 SCIPdebugMsg(scip,
"Did not add any sparse eigenvector cuts, since sparsified initial eigenvector cut does not cut off the solution!\n");
1156 while ( SCIPisFeasNegative(scip, scalar) && *ncuts < maxncuts )
1158 if ( conshdlrdata->sdpconshdlrdata->recomputesparseev )
1168 for (i = 0; i < blocksize; i++)
1170 if ( support[i] == 1 )
1172 for (j = 0; j < blocksize; j++)
1174 if ( support[j] == 1 )
1175 submatrix[cnt++] = fullmatrix[i * blocksize + j];
1179 assert( cnt == size * size );
1183 assert( SCIPisFeasNegative(scip, eigenvalue) );
1185 if ( eigenvalue >= -tol )
1188 SCIPdebugMsg(scip,
"Smallest eigenvalue of principal submatrix: %.15g\n", eigenvalue);
1192 for (j = 0; j < size; j++)
1193 norm += sparseev[j] * sparseev[j];
1196 for (j = 0; j < size; j++)
1197 sparseev[j] /= norm;
1201 for (i = 0; i < blocksize; i++)
1203 if ( support[i] == 1 )
1206 liftedev[i] = sparseev[cnt++];
1211 assert( cnt == size );
1216 eigenvalue = scalar;
1224 for (j = 0; j < blocksize; ++j)
1225 lhs += liftedev[j] * vector[j];
1229 for (j = 0; j < consdata->nvars; ++j)
1233 if ( SCIPisFeasZero(scip, coef) )
1236 vars[cnt] = consdata->vars[j];
1240 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
1241 if ( conshdlrdata->sdpconshdlrdata->generaterows )
1243 SCIP_Bool infeasible;
1246 #if ( SCIP_VERSION >= 700 || (SCIP_VERSION >= 602 && SCIP_SUBVERSION > 0) ) 1247 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, cutname, lhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
1249 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, cutname, lhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
1252 SCIP_CALL( SCIPaddVarsToRow(scip, row, cnt, vars, vals) );
1255 if ( SCIPisCutEfficacious(scip, sol, row) )
1257 #ifdef SCIP_MORE_DEBUG 1258 SCIP_CALL( SCIPprintRow(scip, row, NULL) );
1260 SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
1261 SCIP_CALL( SCIPresetConsAge(scip, cons) );
1263 if ( conshdlrdata->sdpconshdlrdata->cutstopool )
1265 SCIP_CALL( SCIPaddPoolCut(scip, row) );
1268 assert( *result != SCIP_CONSADDED );
1271 *result = SCIP_CUTOFF;
1272 SCIPdebugMsg(scip,
"Detected infeasibility.\n");
1273 SCIP_CALL( SCIPreleaseRow(scip, &row) );
1278 *result = SCIP_SEPARATED;
1280 SCIPdebugMsg(scip,
"Successfully added sparse eigenvector cut.\n");
1284 SCIPdebugMsg(scip,
"Cut is not efficacious!\n");
1285 SCIP_CALL( SCIPreleaseRow(scip, &row) );
1291 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, cutname, cnt, vars, vals, lhs, SCIPinfinity(scip),
1292 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE) );
1293 SCIP_CALL( SCIPaddCons(scip, newcons) );
1294 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1296 assert( *result != SCIP_SEPARATED );
1297 *result = SCIP_CONSADDED;
1299 SCIPdebugMsg(scip,
"Successfully added sparse eigenvector cut.\n");
1303 for (i = 0; i < blocksize; i++)
1305 for (j = 0; j < blocksize; j++)
1306 fullmatrix[i * blocksize + j] -= eigenvalue * liftedev[i] * liftedev[j];
1310 if ( conshdlrdata->sdpconshdlrdata->recomputeinitial )
1317 for (i = 0; i < blocksize * blocksize; i++)
1318 fullmatrixcopy[i] = fullmatrix[i];
1322 SCIPdebugMsg(scip,
"Smallest eigenvalue: %.15g\n", mineig);
1326 for (i = 0; i < blocksize; i++)
1327 minev[i] = eigenvector[i];
1330 if ( conshdlrdata->sdpconshdlrdata->exacttrans )
1335 for (i = 0; i < blocksize * blocksize; i++)
1336 fullmatrixcopy[i] = fullmatrix[i];
1340 SCIPdebugMsg(scip,
"Largest eigenvalue: %.15g\n", maxeig);
1345 maxeig -= eigenvalue;
1349 for (i = 0; i < blocksize; i++)
1351 for (j = 0; j < blocksize; j++)
1354 modmatrix[i * blocksize + j] = maxeig - fullmatrix[i * blocksize +j];
1356 modmatrix[i * blocksize + j] = -fullmatrix[i * blocksize +j];
1361 SCIP_CALL(
truncatedPowerMethod(scip, blocksize, modmatrix, minev, size, convergencetol, liftedev, support, &eigenvalue) );
1363 SCIPdebugMsg(scip,
"Smallest sparse eigenvalue computed by TPower: %.15g\n", maxeig - eigenvalue);
1366 scalar = maxeig - eigenvalue;
1369 if ( *ncuts > 0 || *result == SCIP_CUTOFF )
1372 SCIPdebugMsg(scip,
"Added %d sparse eigenvector cuts\n", *ncuts);
1376 SCIPfreeBufferArray(scip, &minev);
1377 SCIPfreeBufferArray(scip, &sparseev);
1378 SCIPfreeBufferArray(scip, &support);
1379 SCIPfreeBufferArray(scip, &liftedev);
1380 SCIPfreeBufferArray(scip, &submatrix);
1381 SCIPfreeBufferArray(scip, &modmatrix);
1382 SCIPfreeBufferArray(scip, &fullmatrixcopy);
1392 SCIP_CONSHDLR* conshdlr,
1399 char cutname[SCIP_MAXSTRLEN];
1400 SCIP_CONSDATA* consdata;
1401 SCIP_CONSHDLRDATA* conshdlrdata;
1402 SCIP_RETCODE retcode;
1405 SCIP_Real* eigenvectors;
1407 SCIP_Real* fullmatrix;
1408 SCIP_Real* fullmatrixcopy;
1409 SCIP_Real* fullconstmatrix = NULL;
1410 SCIP_Real* eigenvalues;
1419 assert( cons != NULL );
1420 assert( result != NULL );
1422 consdata = SCIPconsGetData(cons);
1423 assert( consdata != NULL );
1425 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1426 assert( conshdlrdata != NULL );
1429 nvars = consdata->nvars;
1430 blocksize = consdata->blocksize;
1432 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars ) );
1433 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars ) );
1435 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize ) );
1436 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrixcopy, blocksize * blocksize ) );
1437 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvectors, blocksize * blocksize) );
1438 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvalues, blocksize) );
1439 SCIP_CALL( SCIPallocBufferArray(scip, &vector, blocksize) );
1445 for (i = 0; i < blocksize * blocksize; i++)
1446 fullmatrixcopy[i] = fullmatrix[i];
1449 if ( conshdlrdata->sdpconshdlrdata->usedimacsfeastol )
1451 assert( conshdlrdata->dimacsfeastol != SCIP_INVALID );
1452 tol = conshdlrdata->dimacsfeastol;
1457 tol = SCIPfeastol(scip);
1459 tol = SCIPgetSepaMinEfficacy(scip);
1463 if ( conshdlrdata->sdpconshdlrdata->separateonecut || conshdlrdata->sdpconshdlrdata->multiplesparsecuts )
1467 if ( retcode == SCIP_OKAY )
1469 if ( eigenvalues[0] < -tol )
1482 if ( retcode != SCIP_OKAY )
1484 SCIPfreeBufferArray(scip, &vector);
1485 SCIPfreeBufferArray(scip, &eigenvalues);
1486 SCIPfreeBufferArray(scip, &eigenvectors);
1487 SCIPfreeBufferArray(scip, &fullmatrixcopy);
1488 SCIPfreeBufferArray(scip, &fullmatrix);
1490 SCIPfreeBufferArray(scip, &vals);
1491 SCIPfreeBufferArray(scip, &vars);
1496 SCIP_CALL( retcode );
1502 if ( neigenvalues > 0 )
1505 if ( consdata->nvars == 0 )
1506 *result = SCIP_CUTOFF;
1510 SCIP_CALL( SCIPallocBufferArray(scip, &fullconstmatrix, blocksize * blocksize) );
1516 for (i = 0; i < neigenvalues && *result != SCIP_CUTOFF; ++i)
1518 SCIP_Real* eigenvector;
1519 SCIP_Real lhs = 0.0;
1525 eigenvector = &(eigenvectors[i * blocksize]);
1528 if ( ! enforce && conshdlrdata->sdpconshdlrdata->sparsifycut )
1530 SCIP_CALL(
sparsifyCut(scip, conshdlr, cons, consdata, sol, blocksize, fullconstmatrix, eigenvector, vector, vars, vals, &success, result) );
1538 else if ( conshdlrdata->sdpconshdlrdata->multiplesparsecuts )
1540 SCIPdebugMsg(scip,
"Smallest eigenvalue: %.15g\n", eigenvalues[i]);
1541 SCIP_CALL(
addMultipleSparseCuts(scip, conshdlr, cons, consdata, sol, blocksize, fullmatrix, fullconstmatrix,
1542 eigenvector, tol, conshdlrdata->sdpconshdlrdata->maxnsparsecuts, vector, vars, vals, &ncuts, &success, result) );
1546 SCIPdebugMsg(scip,
"Successfully added %d sparse eigenvector cuts.\n", ncuts);
1554 for (j = 0; j < consdata->blocksize; ++j)
1556 if ( SCIPisFeasZero(scip, eigenvector[j]) )
1557 eigenvector[j] = 0.0;
1564 for (j = 0; j < blocksize; ++j)
1565 lhs += eigenvector[j] * vector[j];
1568 for (j = 0; j < consdata->nvars; ++j)
1574 if ( ! SCIPisFeasZero(scip, coef) )
1576 vars[cnt] = consdata->vars[j];
1581 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
1582 if ( conshdlrdata->sdpconshdlrdata->generaterows )
1584 SCIP_Bool infeasible;
1587 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, cutname, lhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
1588 SCIP_CALL( SCIPaddVarsToRow(scip, row, cnt, vars, vals) );
1591 if ( enforce || SCIPisCutEfficacious(scip, sol, row) )
1593 #ifdef SCIP_MORE_DEBUG 1594 SCIP_CALL( SCIPprintRow(scip, row, NULL) );
1596 SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
1598 *result = SCIP_CUTOFF;
1600 *result = SCIP_SEPARATED;
1601 SCIP_CALL( SCIPresetConsAge(scip, cons) );
1603 if ( conshdlrdata->sdpconshdlrdata->cutstopool )
1605 SCIP_CALL( SCIPaddPoolCut(scip, row) );
1610 SCIP_CALL( SCIPreleaseRow(scip, &row) );
1616 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, cutname, cnt, vars, vals, lhs, SCIPinfinity(scip),
1617 TRUE, TRUE, enforce, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE) );
1618 SCIP_CALL( SCIPaddCons(scip, newcons) );
1619 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1620 *result = SCIP_CONSADDED;
1624 SCIPdebugMsg(scip,
"<%s>: Separated cuts = %d.\n", SCIPconsGetName(cons), ngen);
1626 SCIPfreeBufferArrayNull(scip, &fullconstmatrix);
1627 SCIPfreeBufferArray(scip, &vector);
1628 SCIPfreeBufferArray(scip, &eigenvalues);
1629 SCIPfreeBufferArray(scip, &eigenvectors);
1630 SCIPfreeBufferArray(scip, &fullmatrixcopy);
1631 SCIPfreeBufferArray(scip, &fullmatrix);
1633 SCIPfreeBufferArray(scip, &vals);
1634 SCIPfreeBufferArray(scip, &vars);
1649 SCIP_CONSDATA* consdata;
1654 assert( scip != NULL );
1655 assert( cons != NULL );
1656 consdata = SCIPconsGetData(cons);
1657 assert( consdata != NULL );
1658 assert( consdata->rankone );
1661 if ( consdata->initallmatricespsd )
1664 assert( consdata->allmatricespsd == FALSE );
1666 blocksize = consdata->blocksize;
1667 SCIP_CALL( SCIPallocBufferArray(scip, &Aj, blocksize * blocksize) );
1669 SCIPdebugMsg(scip,
"Computing allmatricespsd for constraint <%s>.\n", SCIPconsGetName(cons));
1671 consdata->allmatricespsd = TRUE;
1672 for (v = 0; v < consdata->nvars && consdata->allmatricespsd; ++v)
1674 SCIP_Real eigenvalue;
1680 if ( SCIPisNegative(scip, eigenvalue) )
1681 consdata->allmatricespsd = FALSE;
1684 SCIPfreeBufferArray(scip, &Aj);
1686 consdata->initallmatricespsd = TRUE;
1702 assert( scip != NULL );
1703 assert( nchgcoefs != NULL );
1705 for (c = 0; c < nconss; ++c)
1707 SCIP_CONSDATA* consdata;
1708 SCIP_Real* constmatrix;
1713 assert( conss != NULL );
1714 assert( conss[c] != NULL );
1716 consdata = SCIPconsGetData(conss[c]);
1717 assert( consdata != NULL );
1718 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLR_NAME) == 0 );
1719 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLRRANK1_NAME) == 0 );
1722 if ( consdata->rankone )
1728 if ( ! consdata->allmatricespsd )
1732 nvars = consdata->nvars;
1733 for (i = 0; i < nvars; ++i)
1735 if ( SCIPisNegative(scip, SCIPvarGetLbGlobal(consdata->vars[i])) )
1741 SCIPdebugMsg(scip,
"Trying to tighten matrices for constraint <%s>.\n", SCIPconsGetName(conss[c]));
1744 blocksize = consdata->blocksize;
1745 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
1749 for (i = 0; i < nvars; ++i)
1757 if ( ! SCIPvarIsBinary(consdata->vars[i]) )
1761 lb = SCIPvarGetLbLocal(consdata->vars[i]);
1762 ub = SCIPvarGetLbLocal(consdata->vars[i]);
1763 if ( SCIPisEQ(scip, lb, ub) )
1766 assert( SCIPisEQ(scip, lb, 0.0) );
1767 assert( SCIPisEQ(scip, ub, 1.0) );
1770 SCIP_CALL(
SCIPsolveOneVarSDPDense(SCIPbuffer(scip), 1.0, 0.0, 1.0, blocksize, constmatrix, consdata->nvarnonz[i], consdata->row[i], consdata->col[i], consdata->val[i],
1771 SCIPinfinity(scip), SCIPfeastol(scip), &objval, &factor) );
1773 if ( SCIPisInfinity(scip, objval) )
1776 if ( factor == SCIP_INVALID )
1779 if ( ! SCIPisFeasEQ(scip, factor, 1.0) )
1783 SCIPdebugMsg(scip,
"Tightened coefficent matrix of variable <%s> with tightening factor %g.\n", SCIPvarGetName(consdata->vars[i]), factor);
1786 for (j = 0; j < consdata->nvarnonz[i]; j++)
1787 consdata->val[i][j] *= factor;
1793 SCIPfreeBufferArray(scip, &constmatrix);
1805 SCIP_Bool tightenboundscont,
1807 SCIP_Bool* infeasible
1812 assert( scip != NULL );
1813 assert( nchgbds != NULL );
1814 assert( infeasible != NULL );
1816 *infeasible = FALSE;
1818 for (c = 0; c < nconss && !(*infeasible); ++c)
1820 SCIP_CONSDATA* consdata;
1821 SCIP_Real* matrix = NULL;
1822 SCIP_Real* constmatrix;
1824 SCIP_Bool havebinaryvar = FALSE;
1829 assert( conss != NULL );
1830 assert( conss[c] != NULL );
1832 consdata = SCIPconsGetData(conss[c]);
1833 assert( consdata != NULL );
1834 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLR_NAME) == 0 );
1835 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLRRANK1_NAME) == 0 );
1838 if ( consdata->rankone )
1844 if ( ! consdata->allmatricespsd )
1848 nvars = consdata->nvars;
1849 for (i = 0; i < nvars; ++i)
1851 if ( SCIPisInfinity(scip, SCIPvarGetUbLocal(consdata->vars[i])) )
1854 if ( SCIPvarIsBinary(consdata->vars[i]) )
1855 havebinaryvar = TRUE;
1860 SCIPdebugMsg(scip,
"Trying to tighten bounds for constraint <%s>.\n", SCIPconsGetName(conss[c]));
1863 blocksize = consdata->blocksize;
1864 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
1865 if ( havebinaryvar )
1867 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, blocksize * blocksize) );
1870 for (i = 0; i < nvars; ++i)
1886 if ( tightenboundscont && SCIPvarIsIntegral(consdata->vars[i]) )
1890 lb = SCIPvarGetLbLocal(consdata->vars[i]);
1891 ub = SCIPvarGetUbLocal(consdata->vars[i]);
1892 if ( SCIPisEQ(scip, lb, ub) )
1896 assert( ! SCIPisInfinity(scip, ub) );
1897 if ( SCIPisInfinity(scip, -lb) )
1904 for (k = 0; k < nvars; ++k)
1909 ubk = SCIPvarGetUbLocal(consdata->vars[k]);
1912 if ( ! SCIPisZero(scip, ubk) )
1914 sdprow = consdata->row[k];
1915 sdpcol = consdata->col[k];
1916 sdpval = consdata->val[k];
1917 sdpnnonz = consdata->nvarnonz[k];
1918 for (l = 0; l < sdpnnonz; ++l)
1922 constmatrix[row * blocksize + col] -= sdpval[l] * ubk;
1924 constmatrix[col * blocksize + row] -= sdpval[l] * ubk;
1930 if ( SCIPvarIsBinary(consdata->vars[i]) )
1932 SCIP_Real eigenvalue;
1934 assert( matrix != NULL );
1937 for (l = 0; l < blocksize * blocksize; ++l)
1938 matrix[l] = - constmatrix[l];
1944 eigenvalue = -eigenvalue;
1947 if ( SCIPisFeasGE(scip, eigenvalue, 0.0) )
1949 assert( SCIPisFeasNegative(scip, eigenvalue) );
1954 sdprow = consdata->row[i];
1955 sdpcol = consdata->col[i];
1956 sdpval = consdata->val[i];
1957 sdpnnonz = consdata->nvarnonz[i];
1958 for (l = 0; l < sdpnnonz; ++l)
1962 matrix[row * blocksize + col] += sdpval[l];
1964 matrix[col * blocksize + row] += sdpval[l];
1971 if ( SCIPisFeasNegative(scip, eigenvalue) )
1973 SCIPdebugMsg(scip,
"Binary variable <%s> yields infeasibility.\n", SCIPvarGetName(consdata->vars[i]));
1980 SCIPdebugMsg(scip,
"Tighten lower bound for binary variable <%s> to 1.\n", SCIPvarGetName(consdata->vars[i]));
1985 SCIP_CALL(
SCIPsolveOneVarSDPDense(SCIPbuffer(scip), 1.0, lb, ub, blocksize, constmatrix, consdata->nvarnonz[i], consdata->row[i], consdata->col[i], consdata->val[i],
1986 SCIPinfinity(scip), SCIPfeastol(scip), &objval, &factor) );
1989 if ( SCIPisInfinity(scip, objval) )
1991 SCIPdebugMsg(scip,
"Variable <%s> yields infeasibility.\n", SCIPvarGetName(consdata->vars[i]));
1996 if ( factor == SCIP_INVALID )
2000 if ( SCIPisGT(scip, factor, lb) )
2002 SCIP_Bool tightened;
2004 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->vars[i], factor, conss[c], -(i+1), FALSE, infeasible, &tightened) );
2011 SCIPdebugMsg(scip,
"%sTightened lower bound of variable <%s> from %g to %g.\n", SCIPinProbing(scip) ?
"In probing: " :
"", SCIPvarGetName(consdata->vars[i]), lb, factor);
2017 SCIPfreeBufferArrayNull(scip, &matrix);
2018 SCIPfreeBufferArray(scip, &constmatrix);
2030 SCIP_CONSHDLR* conshdlr,
2033 SCIP_Bool solvesdps,
2036 SCIP_Bool* infeasible
2039 char cutname[SCIP_MAXSTRLEN];
2040 SCIP_CONSHDLRDATA* conshdlrdata;
2041 SCIP_CONSDATA* consdata;
2043 SCIP_Real* consvals;
2044 SCIP_VAR** consvars;
2045 SCIP_Real* diagentries;
2053 assert( scip != NULL );
2054 assert( naddconss != NULL );
2055 assert( nchgbds != NULL );
2056 assert( infeasible != NULL );
2058 *infeasible = FALSE;
2060 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2061 assert( conshdlrdata != NULL );
2063 for (c = 0; c < nconss; ++c)
2065 consdata = SCIPconsGetData(conss[c]);
2066 assert( consdata != NULL );
2067 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLR_NAME) == 0 );
2068 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLRRANK1_NAME) == 0 );
2070 blocksize = consdata->blocksize;
2071 nvars = consdata->nvars;
2073 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
2074 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nvars) );
2076 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, (blocksize * (blocksize + 1)) / 2) );
2080 SCIP_CALL( SCIPallocClearBufferArray(scip, &diagentries, blocksize * nvars) );
2083 for (j = 0; j < nvars; ++j)
2086 for (i = 0; i < consdata->nvarnonz[j]; i++)
2088 if ( consdata->col[j][i] == consdata->row[j][i] )
2089 diagentries[consdata->col[j][i] * nvars + j] = consdata->val[j][i];
2094 for (k = 0; k < blocksize && !(*infeasible); ++k)
2098 SCIP_Real activitylb = 0.0;
2101 for ( j = 0; j < nvars; ++j)
2106 val = diagentries[k * nvars + j];
2107 if ( ! SCIPisZero(scip, val) )
2109 var = consdata->vars[j];
2110 consvals[cnt] = val;
2111 consvars[cnt++] = var;
2115 activitylb += val * SCIPvarGetLbGlobal(var);
2117 activitylb += val * SCIPvarGetUbGlobal(var);
2127 if ( SCIPisPositive(scip, lhs) )
2130 else if ( cnt == 1 && SCIPvarGetStatus(consvars[0]) != SCIP_VARSTATUS_MULTAGGR )
2132 SCIP_Bool tightened;
2138 assert( var != NULL );
2141 if ( SCIPisPositive(scip, val) )
2143 SCIP_CALL( SCIPtightenVarLb(scip, var, lhs / val, FALSE, infeasible, &tightened) );
2146 SCIPdebugMsg(scip,
"Tightend lower bound of <%s> to %g because of diagonal values of SDP-constraint <%s>!\n",
2147 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPconsGetName(conss[c]));
2151 else if ( SCIPisNegative(scip, val) )
2153 SCIP_CALL( SCIPtightenVarUb(scip, var, lhs / val, FALSE, infeasible, &tightened) );
2156 SCIPdebugMsg(scip,
"Tightend upper bound of <%s> to %g because of diagonal values of SDP-constraint <%s>!\n",
2157 SCIPvarGetName(var), SCIPvarGetUbGlobal(var), SCIPconsGetName(conss[c]));
2163 else if ( SCIPisLT(scip, activitylb, lhs) )
2165 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"diag_ge_zero_%d", ++(conshdlrdata->ndiaggezerocuts));
2168 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, cutname, cnt, consvars, consvals, lhs, SCIPinfinity(scip),
2169 FALSE, ! solvesdps, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2171 SCIP_CALL( SCIPaddCons(scip, cons) );
2172 #ifdef SCIP_MORE_DEBUG 2173 SCIPinfoMessage(scip, NULL,
"Added diagonal lp-constraint: ");
2174 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2175 SCIPinfoMessage(scip, NULL,
"\n");
2177 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2182 SCIPfreeBufferArray(scip, &diagentries);
2183 SCIPfreeBufferArray(scip, &matrix);
2184 SCIPfreeBufferArray(scip, &consvals);
2185 SCIPfreeBufferArray(scip, &consvars);
2206 char name[SCIP_MAXSTRLEN];
2207 SCIP_CONSDATA* consdata;
2210 assert( scip != NULL );
2211 assert( naddconss != NULL );
2213 for (c = 0; c < nconss; ++c)
2215 SCIP_Shortbool* nonzeroentries;
2216 SCIP_Shortbool* diagnonzero;
2219 SCIP_Bool negintvar = FALSE;
2222 int ndiagnonzero = 0;
2231 assert( conss[c] != NULL );
2232 consdata = SCIPconsGetData(conss[c]);
2233 assert( consdata != NULL );
2235 blocksize = consdata->blocksize;
2236 nvars = consdata->nvars;
2239 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2240 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
2241 SCIP_CALL( SCIPallocClearBufferArray(scip, &nonzeroentries, blocksize * (blocksize+1) / 2) );
2242 SCIP_CALL( SCIPallocClearBufferArray(scip, &diagnonzero, blocksize) );
2243 SCIP_CALL( SCIPallocClearBufferArray(scip, &ndiagvars, blocksize) );
2244 SCIP_CALL( SCIPallocBufferArray(scip, &diagvars, blocksize) );
2245 for (j = 0; j < blocksize; ++j)
2247 SCIP_CALL( SCIPallocClearBufferArray(scip, &diagvars[j], nvars) );
2251 for (v = 0; v < nvars; ++v)
2253 if ( SCIPvarIsIntegral(consdata->vars[v]) && SCIPisNegative(scip, SCIPvarGetLbGlobal(consdata->vars[v])) )
2259 for (j = 0; j < consdata->nvarnonz[v]; j++)
2261 rowidx = consdata->row[v][j];
2262 colidx = consdata->col[v][j];
2263 assert( 0 <= rowidx && rowidx < blocksize );
2264 assert( 0 <= colidx && colidx < blocksize );
2265 assert( ! SCIPisZero(scip, consdata->val[v][j]) );
2267 pos = rowidx * (rowidx + 1)/2 + colidx;
2268 nonzeroentries[pos] = TRUE;
2271 if ( rowidx == colidx )
2274 if ( SCIPisPositive(scip, consdata->val[v][j]) )
2275 diagvars[rowidx][ndiagvars[rowidx]++] = v;
2278 if ( ! SCIPvarIsIntegral(consdata->vars[v]) )
2280 if ( ! diagnonzero[rowidx] )
2282 diagnonzero[rowidx] = TRUE;
2293 for (j = blocksize - 1; j >= 0; j--)
2295 SCIPfreeBufferArray(scip, &diagvars[j]);
2297 SCIPfreeBufferArray(scip, &diagvars);
2298 SCIPfreeBufferArray(scip, &ndiagvars);
2299 SCIPfreeBufferArray(scip, &diagnonzero);
2300 SCIPfreeBufferArray(scip, &nonzeroentries);
2301 SCIPfreeBufferArray(scip, &vals);
2302 SCIPfreeBufferArray(scip, &vars);
2307 for (j = 0; j < consdata->constnnonz; j++)
2309 rowidx = consdata->constrow[j];
2310 colidx = consdata->constcol[j];
2311 assert( 0 <= colidx && colidx < blocksize );
2312 assert( 0 <= rowidx && rowidx < blocksize );
2313 assert( ! SCIPisZero(scip, consdata->constval[j]) );
2315 if ( rowidx == colidx )
2317 if ( ! diagnonzero[rowidx] )
2319 diagnonzero[rowidx] = TRUE;
2324 assert( 0 <= ndiagnonzero && ndiagnonzero <= blocksize );
2327 if ( ndiagnonzero >= blocksize )
2329 for (j = blocksize - 1; j >= 0; j--)
2331 SCIPfreeBufferArray(scip, &diagvars[j]);
2333 SCIPfreeBufferArray(scip, &diagvars);
2334 SCIPfreeBufferArray(scip, &ndiagvars);
2335 SCIPfreeBufferArray(scip, &diagnonzero);
2336 SCIPfreeBufferArray(scip, &nonzeroentries);
2337 SCIPfreeBufferArray(scip, &vals);
2338 SCIPfreeBufferArray(scip, &vars);
2343 for (j = 0; j < consdata->constnnonz; j++)
2347 rowidx = consdata->constrow[j];
2348 colidx = consdata->constcol[j];
2349 assert( 0 <= colidx && colidx < blocksize );
2350 assert( 0 <= rowidx && rowidx < blocksize );
2351 assert( ! SCIPisZero(scip, consdata->constval[j]) );
2354 if ( rowidx == colidx )
2357 pos = rowidx * (rowidx + 1)/2 + colidx;
2360 if ( nonzeroentries[pos] )
2364 if ( ! diagnonzero[rowidx] && ndiagvars[rowidx] > 0 )
2367 for (v = 0; v < ndiagvars[rowidx]; ++v)
2369 assert( SCIPvarIsIntegral(consdata->vars[diagvars[rowidx][v]]) );
2370 assert( 0 <= diagvars[rowidx][v] && diagvars[rowidx][v] < nvars );
2371 vars[v] = consdata->vars[diagvars[rowidx][v]];
2374 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"diag_0_impl_row_%d_%d", rowidx, colidx);
2377 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, ndiagvars[rowidx], vars, vals, 1.0, SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2378 SCIP_CALL( SCIPaddCons(scip, cons) );
2379 #ifdef SCIP_MORE_DEBUG 2380 SCIPinfoMessage(scip, NULL,
"Added constraint: ");
2381 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2382 SCIPinfoMessage(scip, NULL,
"\n");
2384 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2388 diagnonzero[rowidx] = TRUE;
2392 if ( ! diagnonzero[colidx] && ndiagvars[colidx] > 0 )
2395 for (v = 0; v < ndiagvars[colidx]; ++v)
2397 assert( SCIPvarIsIntegral(consdata->vars[diagvars[colidx][v]]) );
2398 assert( 0 <= diagvars[colidx][v] && diagvars[colidx][v] < nvars );
2399 vars[v] = consdata->vars[diagvars[colidx][v]];
2402 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"diag_0_impl_col_%d_%d", rowidx, colidx);
2405 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, ndiagvars[colidx], vars, vals, 1.0, SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2406 SCIP_CALL( SCIPaddCons(scip, cons) );
2407 #ifdef SCIP_MORE_DEBUG 2408 SCIPinfoMessage(scip, NULL,
"Added constraint: ");
2409 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2410 SCIPinfoMessage(scip, NULL,
"\n");
2412 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2416 diagnonzero[colidx] = TRUE;
2421 for (j = blocksize - 1; j >= 0; j--)
2423 SCIPfreeBufferArray(scip, &diagvars[j]);
2425 SCIPfreeBufferArray(scip, &diagvars);
2426 SCIPfreeBufferArray(scip, &ndiagvars);
2427 SCIPfreeBufferArray(scip, &diagnonzero);
2428 SCIPfreeBufferArray(scip, &nonzeroentries);
2429 SCIPfreeBufferArray(scip, &vals);
2430 SCIPfreeBufferArray(scip, &vars);
2458 SCIP_Bool solvesdps,
2462 char name[SCIP_MAXSTRLEN];
2463 SCIP_VAR** consvars;
2464 SCIP_Real* consvals;
2470 assert( scip != NULL );
2471 assert( naddconss != NULL );
2473 for (c = 0; c < nconss; ++c)
2475 SCIP_CONSDATA* consdata;
2476 SCIP_Real** matrices = NULL;
2477 SCIP_Real* constmatrix;
2481 assert( conss[c] != NULL );
2482 consdata = SCIPconsGetData(conss[c]);
2483 assert( consdata != NULL );
2485 blocksize = consdata->blocksize;
2486 nvars = consdata->nvars;
2488 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
2489 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nvars) );
2492 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
2495 SCIP_CALL( SCIPallocBufferArray(scip, &matrices, nvars) );
2496 for (i = 0; i < nvars; ++i)
2498 SCIP_CALL( SCIPallocBufferArray(scip, &matrices[i], blocksize * blocksize) );
2503 for (s = 0; s < blocksize; ++s)
2505 for (t = 0; t < s; ++t)
2510 SCIP_Real activitylb = 0.0;
2515 for (i = 0; i < nvars; ++i)
2517 SCIP_Real coef = 0.0;
2519 val = matrices[i][s * blocksize + t];
2520 if ( ! SCIPisZero(scip, val) )
2527 val = matrices[i][s * blocksize + s];
2528 if ( ! SCIPisZero(scip, val) )
2531 val = matrices[i][t * blocksize + t];
2532 if ( ! SCIPisZero(scip, val) )
2535 if ( ! SCIPisZero(scip, coef) )
2537 consvals[nconsvars] = coef;
2538 consvars[nconsvars] = consdata->vars[i];
2543 activitylb += coef * SCIPvarGetLbGlobal(consdata->vars[i]);
2545 activitylb += coef * SCIPvarGetUbGlobal(consdata->vars[i]);
2550 if ( cnt <= 0 || nconsvars <= 0 )
2554 lhs = constmatrix[s * blocksize + s] + constmatrix[t * blocksize + t] - 2.0 * constmatrix[s * blocksize + t];
2557 if ( SCIPisGE(scip, activitylb, lhs) )
2561 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"2x2minorlin#%d#%d", s, t);
2562 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nconsvars, consvars, consvals, lhs, SCIPinfinity(scip),
2563 FALSE, ! solvesdps, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2564 SCIP_CALL( SCIPaddCons(scip, cons) );
2565 #ifdef SCIP_MORE_DEBUG 2566 SCIPinfoMessage(scip, NULL,
"Added 2x2 minor linear constraint: ");
2567 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2568 SCIPinfoMessage(scip, NULL,
"\n");
2570 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2575 for (i = nvars - 1; i >= 0; --i)
2576 SCIPfreeBufferArray(scip, &matrices[i]);
2577 SCIPfreeBufferArray(scip, &matrices);
2578 SCIPfreeBufferArray(scip, &constmatrix);
2579 SCIPfreeBufferArray(scip, &consvals);
2580 SCIPfreeBufferArray(scip, &consvars);
2609 SCIP_Bool solvesdps,
2613 char name[SCIP_MAXSTRLEN];
2614 SCIP_VAR*** matrixvars;
2615 SCIP_VAR** consvars;
2616 SCIP_Real* consvals;
2622 assert( scip != NULL );
2623 assert( naddconss != NULL );
2625 for (c = 0; c < nconss; ++c)
2627 SCIP_CONSDATA* consdata;
2628 SCIP_Real** matrices = NULL;
2629 SCIP_Real* constmatrix;
2634 assert( conss[c] != NULL );
2635 consdata = SCIPconsGetData(conss[c]);
2636 assert( consdata != NULL );
2638 blocksize = consdata->blocksize;
2639 nvars = consdata->nvars;
2641 size = MAX(nvars + 1, 3);
2642 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, size) );
2643 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, size) );
2646 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
2649 SCIP_CALL( SCIPallocBufferArray(scip, &matrices, nvars) );
2650 for (i = 0; i < nvars; ++i)
2652 SCIP_CALL( SCIPallocBufferArray(scip, &matrices[i], blocksize * blocksize) );
2656 SCIP_CALL( SCIPallocBufferArray(scip, &matrixvars, blocksize) );
2659 for (s = 0; s < blocksize; ++s)
2661 SCIP_CALL( SCIPallocClearBufferArray(scip, &matrixvars[s], blocksize) );
2663 for (t = s; t >= 0; --t)
2665 SCIP_VAR* matrixvar = NULL;
2666 SCIP_VAR* matrixsumvar;
2667 SCIP_VAR* matrixdiffvar;
2674 for (i = 0; i < nvars; ++i)
2676 val = matrices[i][s * blocksize + t];
2677 if ( ! SCIPisZero(scip, val) )
2679 consvals[nconsvars] = val;
2680 consvars[nconsvars++] = consdata->vars[i];
2685 if ( nconsvars == 0 )
2688 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"M%d#%d#%d", c, s, t);
2689 SCIP_CALL( SCIPcreateVarBasic(scip, &matrixvar, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
2690 SCIP_CALL( SCIPaddVar(scip, matrixvar) );
2691 SCIPdebugMsg(scip,
"Added new matrix variable <%s>\n", name );
2693 consvals[nconsvars] = -1.0;
2694 consvars[nconsvars++] = matrixvar;
2697 lhs = constmatrix[s * blocksize + t];
2700 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"C%d#%d#%d", c, s, t);
2701 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nconsvars, consvars, consvals, lhs, lhs,
2702 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2703 SCIP_CALL( SCIPaddCons(scip, cons) );
2705 #ifdef SCIP_MORE_DEBUG 2706 SCIPinfoMessage(scip, NULL,
"Added linear constraint for coupling the new matrix variable: ");
2707 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2708 SCIPinfoMessage(scip, NULL,
"\n");
2711 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2712 assert( matrixvar != NULL );
2715 matrixvars[s][t] = matrixvar;
2722 if ( matrixvars[s][s] == NULL || matrixvars[t][t] == NULL || matrixvars[s][t] == NULL )
2726 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"sum%d#%d#%d", c, s, t);
2727 SCIP_CALL( SCIPcreateVarBasic(scip, &matrixsumvar, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
2728 SCIP_CALL( SCIPaddVar(scip, matrixsumvar) );
2729 SCIPdebugMsg(scip,
"Added new variable <%s> for sum of two matrix variables.\n", name);
2731 consvars[0] = matrixvars[s][s];
2732 consvars[1] = matrixvars[t][t];
2733 consvars[2] = matrixsumvar;
2740 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"Sum%d#%d#%d", c, s, t);
2741 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 3, consvars, consvals, 0.0, 0.0,
2742 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2743 SCIP_CALL( SCIPaddCons(scip, cons) );
2745 #ifdef SCIP_MORE_DEBUG 2746 SCIPinfoMessage(scip, NULL,
"Added linear constraint for sum of two matrix variables: ");
2747 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2748 SCIPinfoMessage(scip, NULL,
"\n");
2751 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2754 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"diff%d#%d#%d", c, s, t);
2755 SCIP_CALL( SCIPcreateVarBasic(scip, &matrixdiffvar, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
2756 SCIP_CALL( SCIPaddVar(scip, matrixdiffvar) );
2757 SCIPdebugMsg(scip,
"Added new variable <%s> for difference of two matrix variables.\n", name);
2759 consvars[0] = matrixvars[s][s];
2760 consvars[1] = matrixvars[t][t];
2761 consvars[2] = matrixdiffvar;
2768 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"Diff%d#%d#%d", c, s, t);
2769 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 3, consvars, consvals, 0.0, 0.0,
2770 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2771 SCIP_CALL( SCIPaddCons(scip, cons) );
2773 #ifdef SCIP_MORE_DEBUG 2774 SCIPinfoMessage(scip, NULL,
"Added linear constraint for difference of two matrix variables: ");
2775 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2776 SCIPinfoMessage(scip, NULL,
"\n");
2779 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2782 consvars[0] = matrixvars[s][t];
2783 consvars[1] = matrixdiffvar;
2789 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"2x2minorSOC#%d#%d#%d", c, s, t);
2791 #if ( SCIP_VERSION >= 800 || ( SCIP_VERSION < 800 && SCIP_APIVERSION >= 100 ) ) 2793 consvars[2] = matrixsumvar;
2795 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &cons, name, 0, NULL, NULL, 3, consvars, consvars, consvals,
2796 - SCIPinfinity(scip), 0.0, TRUE, ! solvesdps, ! solvesdps, ! solvesdps, TRUE, FALSE, FALSE, TRUE, TRUE) );
2798 SCIP_CALL( SCIPcreateConsSOC(scip, &cons, name, 2, consvars, consvals, NULL, 0.0, matrixsumvar, 1.0, 0.0,
2799 TRUE, ! solvesdps, ! solvesdps, ! solvesdps, TRUE, FALSE, FALSE, TRUE, TRUE) );
2801 SCIP_CALL( SCIPaddCons(scip, cons) );
2803 #ifdef SCIP_MORE_DEBUG 2804 SCIPinfoMessage(scip, NULL,
"Added 2x2 minor linear constraint: ");
2805 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2806 SCIPinfoMessage(scip, NULL,
"\n");
2807 SCIPinfoMessage(scip, NULL,
"\n");
2809 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2812 SCIP_CALL( SCIPreleaseVar(scip, &matrixsumvar) );
2813 SCIP_CALL( SCIPreleaseVar(scip, &matrixdiffvar) );
2817 for (s = blocksize - 1; s >= 0; --s)
2819 for (t = 0; t <= s; ++t)
2821 if ( matrixvars[s][t] != NULL )
2823 SCIP_CALL( SCIPreleaseVar(scip, &matrixvars[s][t]) );
2826 SCIPfreeBufferArray(scip, &matrixvars[s]);
2828 SCIPfreeBufferArray(scip, &matrixvars);
2830 for (i = 0; i < nvars; ++i)
2831 SCIPfreeBufferArray(scip, &matrices[i]);
2832 SCIPfreeBufferArray(scip, &matrices);
2833 SCIPfreeBufferArray(scip, &constmatrix);
2834 SCIPfreeBufferArray(scip, &consvals);
2835 SCIPfreeBufferArray(scip, &consvars);
2851 SCIP_Bool solvesdps,
2855 char name[SCIP_MAXSTRLEN];
2856 SCIP_VAR** consvars;
2857 SCIP_Real* consvals;
2864 assert( scip != NULL );
2865 assert( naddconss != NULL );
2867 for (c = 0; c < nconss; ++c)
2869 SCIP_CONSDATA* consdata;
2870 SCIP_Real** matrices = NULL;
2871 SCIP_Real* constmatrix;
2873 assert( conss[c] != NULL );
2874 consdata = SCIPconsGetData(conss[c]);
2875 assert( consdata != NULL );
2877 blocksize = consdata->blocksize;
2878 nvars = consdata->nvars;
2880 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) );
2881 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nvars) );
2883 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
2887 for (j = 0; j < consdata->constnnonz; ++j)
2894 s = consdata->constrow[j];
2895 t = consdata->constcol[j];
2902 if ( matrices == NULL )
2904 SCIP_CALL( SCIPallocBufferArray(scip, &matrices, nvars) );
2905 for (i = 0; i < nvars; ++i)
2907 SCIP_CALL( SCIPallocBufferArray(scip, &matrices[i], blocksize * blocksize) );
2911 assert( matrices != NULL );
2914 for (i = 0; i < nvars; ++i)
2916 if ( ! SCIPisZero(scip, matrices[i][s * blocksize + s]) )
2918 if ( ! SCIPisZero(scip, matrices[i][t * blocksize + t]) )
2925 prod = constmatrix[s * blocksize + s] * constmatrix[t * blocksize + t];
2926 if ( SCIPisEfficacious(scip, prod) )
2929 SCIP_Real activitylb = 0.0;
2934 for (i = 0; i < nvars; ++i)
2936 val = matrices[i][s * blocksize + t];
2937 if ( ! SCIPisZero(scip, val) )
2939 consvals[nconsvars] = val;
2940 consvars[nconsvars] = consdata->vars[i];
2945 activitylb += val * SCIPvarGetLbGlobal(consdata->vars[i]);
2947 activitylb += val * SCIPvarGetUbGlobal(consdata->vars[i]);
2951 lhs = consdata->constval[j] - sqrt(prod);
2954 if ( SCIPisGE(scip, activitylb, lhs) )
2958 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"2x2minorprod#%d#%d", s, t);
2959 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nconsvars, consvars, consvals, lhs, SCIPinfinity(scip),
2960 FALSE, ! solvesdps, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
2961 SCIP_CALL( SCIPaddCons(scip, cons) );
2962 #ifdef SCIP_MORE_DEBUG 2963 SCIPinfoMessage(scip, NULL,
"Added 2x2 minor product constraint: ");
2964 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2965 SCIPinfoMessage(scip, NULL,
"\n");
2967 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
2972 if ( matrices != NULL )
2974 for (i = nvars - 1; i >= 0; --i)
2975 SCIPfreeBufferArray(scip, &matrices[i]);
2976 SCIPfreeBufferArray(scip, &matrices);
2978 SCIPfreeBufferArray(scip, &constmatrix);
2979 SCIPfreeBufferArray(scip, &consvals);
2980 SCIPfreeBufferArray(scip, &consvars);
2998 SCIP_Bool solvesdps,
3004 assert( scip != NULL );
3005 assert( naddconss != NULL );
3007 for (c = 0; c < nconss; ++c)
3009 char name[SCIP_MAXSTRLEN];
3010 SCIP_VAR** consvars;
3011 SCIP_Real* consvals;
3012 SCIP_CONSDATA* consdata;
3013 SCIP_Real* constmatrix;
3014 SCIP_Real** matrices;
3021 assert( conss[c] != NULL );
3022 consdata = SCIPconsGetData(conss[c]);
3023 assert( consdata != NULL );
3025 blocksize = consdata->blocksize;
3026 nvars = consdata->nvars;
3028 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2 * nvars) );
3029 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2 * nvars) );
3032 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
3035 SCIP_CALL( SCIPallocBufferArray(scip, &matrices, nvars) );
3036 for (i = 0; i < nvars; ++i)
3038 SCIP_CALL( SCIPallocBufferArray(scip, &matrices[i], blocksize * blocksize) );
3043 for (s = 1; s < blocksize; ++s)
3045 SCIP_Real ubs = 0.0;
3051 pos = s * blocksize + s;
3052 for (i = 0; i < nvars; ++i)
3054 val = matrices[i][pos];
3055 if ( ! SCIPisZero(scip, val) )
3058 bound = SCIPvarGetUbLocal(consdata->vars[i]);
3060 bound = SCIPvarGetLbLocal(consdata->vars[i]);
3062 if ( SCIPisInfinity(scip, REALABS(bound)) )
3064 ubs = SCIPinfinity(scip);
3070 assert( ! SCIPisInfinity(scip, ubs) );
3072 if ( ! SCIPisInfinity(scip, ubs) )
3073 ubs -= constmatrix[pos];
3076 for (t = s-1; t >= 0; --t)
3079 SCIP_Real ubt = 0.0;
3080 SCIP_Real ubst = 0.0;
3083 pos = s * blocksize + t;
3084 for (i = 0; i < nvars; ++i)
3086 val = matrices[i][pos];
3087 if ( ! SCIPisZero(scip, val) )
3090 bound = SCIPvarGetUbLocal(consdata->vars[i]);
3092 bound = SCIPvarGetLbLocal(consdata->vars[i]);
3094 if ( SCIPisInfinity(scip, REALABS(bound)) )
3096 ubst = SCIPinfinity(scip);
3100 ubst += val * bound;
3102 assert( ! SCIPisInfinity(scip, ubst) );
3104 if ( ! SCIPisInfinity(scip, ubst) )
3105 ubst -= constmatrix[pos];
3108 if ( SCIPisZero(scip, ubst) )
3112 if ( SCIPisInfinity(scip, ubst) )
3116 pos = t * blocksize + t;
3117 for (i = 0; i < nvars; ++i)
3119 val = matrices[i][pos];
3120 if ( ! SCIPisZero(scip, val) )
3123 bound = SCIPvarGetUbLocal(consdata->vars[i]);
3125 bound = SCIPvarGetLbLocal(consdata->vars[i]);
3127 if ( SCIPisInfinity(scip, REALABS(bound)) )
3129 ubt = SCIPinfinity(scip);
3135 assert( ! SCIPisInfinity(scip, ubt) );
3137 if ( ! SCIPisInfinity(scip, ubt) )
3138 ubt -= constmatrix[pos];
3140 assert( ! SCIPisZero(scip, ubst) );
3141 assert( ! SCIPisInfinity(scip, ubst) );
3144 if ( ! SCIPisInfinity(scip, ubt) )
3151 if ( ! SCIPisZero(scip, ubst) )
3153 for (i = 0; i < nvars; ++i)
3155 val = matrices[i][s * blocksize + t];
3156 if ( ! SCIPisZero(scip, val) )
3158 consvals[nconsvars] = 2.0 * ubst * val;
3159 consvars[nconsvars++] = consdata->vars[i];
3162 rhs += 2.0 * ubst * constmatrix[s * blocksize + t];
3165 if ( ! SCIPisZero(scip, ubt) )
3167 for (i = 0; i < nvars; ++i)
3169 val = matrices[i][s * blocksize + s];
3170 if ( ! SCIPisZero(scip, val) )
3172 consvals[nconsvars] = - ubt * val;
3173 consvars[nconsvars++] = consdata->vars[i];
3176 rhs -= ubt * constmatrix[s * blocksize + s];
3179 if ( nconsvars >= 1 )
3182 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"twominorvarbounda#%d#%d", s, t);
3183 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
3184 FALSE, ! solvesdps, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
3185 SCIP_CALL( SCIPaddCons(scip, cons) );
3186 #ifdef SCIP_MORE_DEBUG 3187 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
3188 SCIPinfoMessage(scip, NULL,
"\n");
3190 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3196 if ( ! SCIPisInfinity(scip, ubs) )
3203 if ( ! SCIPisZero(scip, ubst) )
3205 for (i = 0; i < nvars; ++i)
3207 val = matrices[i][s * blocksize + t];
3208 if ( ! SCIPisZero(scip, val) )
3210 consvals[nconsvars] = 2.0 * ubst * val;
3211 consvars[nconsvars++] = consdata->vars[i];
3214 rhs += 2.0 * ubst * constmatrix[s * blocksize + t];
3217 if ( ! SCIPisZero(scip, ubs) )
3219 for (i = 0; i < nvars; ++i)
3221 val = matrices[i][t * blocksize + t];
3222 if ( ! SCIPisZero(scip, val) )
3224 consvals[nconsvars] = - ubs * val;
3225 consvars[nconsvars++] = consdata->vars[i];
3228 rhs -= ubs * constmatrix[t * blocksize + t];
3231 if ( nconsvars >= 1 )
3234 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"twominorvarboundb#%d#%d", s, t);
3235 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
3236 FALSE, ! solvesdps, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
3237 SCIP_CALL( SCIPaddCons(scip, cons) );
3238 #ifdef SCIP_MORE_DEBUG 3239 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
3240 SCIPinfoMessage(scip, NULL,
"\n");
3242 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3249 for (i = nvars - 1; i >= 0; --i)
3250 SCIPfreeBufferArray(scip, &matrices[i]);
3251 SCIPfreeBufferArray(scip, &matrices);
3252 SCIPfreeBufferArray(scip, &constmatrix);
3253 SCIPfreeBufferArray(scip, &consvals);
3254 SCIPfreeBufferArray(scip, &consvars);
3264 SCIP_CONSHDLR* conshdlr,
3272 assert( scip != NULL );
3273 assert( conshdlr != NULL );
3274 assert( naddconss != NULL );
3276 if ( conss == NULL )
3279 for (c = 0; c < nconss; ++c)
3281 SCIP_CONSDATA* consdata;
3283 consdata = SCIPconsGetData(conss[c]);
3284 assert( consdata != NULL );
3286 consdata->maxevsubmat[0] = -1;
3287 consdata->maxevsubmat[1] = -1;
3291 if ( consdata->rankone && ! consdata->addedquadcons )
3293 SCIP_VAR** quadvars1;
3294 SCIP_VAR** quadvars2;
3296 SCIP_CONS* quadcons;
3297 SCIP_Real* lincoefs;
3298 SCIP_Real* quadcoefs;
3299 SCIP_Real* constmatrix;
3300 SCIP_Real** matrixAk;
3311 char name[SCIP_MAXSTRLEN];
3322 blocksize = consdata->blocksize;
3324 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, (blocksize * (blocksize + 1)) / 2) );
3327 SCIP_CALL( SCIPallocBufferArray(scip, &quadvars1, consdata->nvars * consdata->nvars) );
3328 SCIP_CALL( SCIPallocBufferArray(scip, &quadvars2, consdata->nvars * consdata->nvars) );
3329 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, consdata->nvars) );
3330 SCIP_CALL( SCIPallocBufferArray(scip, &quadcoefs, consdata->nvars * consdata->nvars) );
3331 SCIP_CALL( SCIPallocBufferArray(scip, &lincoefs, consdata->nvars) );
3332 SCIP_CALL( SCIPallocBufferArray(scip, &matrixAk, consdata->nvars) );
3334 for (i = 0; i < consdata->nvars; ++i)
3336 SCIP_CALL( SCIPallocBufferArray(scip, &matrixAk[i], blocksize * blocksize) );
3340 SCIP_CALL( SCIPallocBufferArray(scip, &nnonzvars, (blocksize * (blocksize + 1)) / 2) );
3341 SCIP_CALL( SCIPallocBufferArray(scip, &nonzvars, (blocksize * (blocksize + 1)) / 2) );
3343 for (i = 0; i < blocksize; ++i)
3345 for (j = 0; j <= i; ++j)
3351 for (k = 0; k < consdata->nvars; ++k)
3353 if ( ! SCIPisZero(scip, matrixAk[k][i * blocksize + j]) || ! SCIPisZero(scip, matrixAk[k][i * blocksize + i]) || ! SCIPisZero(scip, matrixAk[k][j * blocksize + j]) )
3363 for (i = 0; i < blocksize; ++i)
3365 for (j = 0; j < i; ++j)
3377 ajjk = matrixAk[varind1][j * consdata->blocksize + j];
3378 aiik = matrixAk[varind1][i * consdata->blocksize + i];
3379 aijk = matrixAk[varind1][j * consdata->blocksize + i];
3381 if ( ! SCIPisZero(scip, -cii * ajjk - cjj * aiik + cij * aijk) )
3383 linvars[lincnt] = consdata->vars[varind1];
3384 lincoefs[lincnt] = -cii * ajjk - cjj * aiik + cij * aijk;
3388 for (l = 0; l < k; ++l)
3391 ajjl = matrixAk[varind2][j * consdata->blocksize + j];
3392 aiil = matrixAk[varind2][i * consdata->blocksize + i];
3393 aijl = matrixAk[varind2][j * consdata->blocksize + i];
3395 if ( ! SCIPisZero(scip, aiik * ajjl + ajjk * aiil - 2 * aijk * aijl) )
3397 quadvars1[quadcnt] = consdata->vars[varind1];
3398 quadvars2[quadcnt] = consdata->vars[varind2];
3399 quadcoefs[quadcnt] = aiik * ajjl + ajjk * aiil - 2 * aijk * aijl;
3405 if ( ! SCIPisZero(scip, aiik * ajjk - aijk * aijk) )
3407 quadvars1[quadcnt] = consdata->vars[varind1];
3408 quadvars2[quadcnt] = consdata->vars[varind1];
3409 quadcoefs[quadcnt] = aiik * ajjk - aijk * aijk;
3413 assert( quadcnt <= consdata->nvars * consdata->nvars );
3414 assert( lincnt <= consdata->nvars );
3416 lhs = cij * cij - cii * cjj;
3418 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"quadcons#%d#%d#%d", i, j, c);
3421 #if ( SCIP_VERSION >= 800 || ( SCIP_VERSION < 800 && SCIP_APIVERSION >= 100 ) ) 3422 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &quadcons, name, lincnt, linvars, lincoefs, quadcnt, quadvars1, quadvars2, quadcoefs, lhs, lhs,
3433 SCIP_CALL( SCIPcreateConsQuadratic(scip, &quadcons, name, lincnt, linvars, lincoefs, quadcnt, quadvars1, quadvars2, quadcoefs, lhs, lhs,
3445 #ifdef SCIP_MORE_DEBUG 3446 SCIP_CALL( SCIPprintCons(scip, quadcons, NULL) );
3447 SCIPinfoMessage(scip, NULL,
"\n");
3450 SCIP_CALL( SCIPaddCons(scip, quadcons) );
3451 SCIP_CALL( SCIPreleaseCons(scip, &quadcons) );
3456 for (i = blocksize - 1; i >= 0; --i)
3458 for (j = i; j >= 0; --j)
3462 SCIPfreeBufferArray(scip, &nonzvars);
3463 SCIPfreeBufferArray(scip, &nnonzvars);
3465 for (i = consdata->nvars - 1; i >= 0; --i)
3466 SCIPfreeBufferArray(scip, &matrixAk[i]);
3468 SCIPfreeBufferArray(scip, &matrixAk);
3469 SCIPfreeBufferArray(scip, &lincoefs);
3470 SCIPfreeBufferArray(scip, &quadcoefs);
3471 SCIPfreeBufferArray(scip, &linvars);
3472 SCIPfreeBufferArray(scip, &quadvars2);
3473 SCIPfreeBufferArray(scip, &quadvars1);
3474 SCIPfreeBufferArray(scip, &constmatrix);
3476 consdata->addedquadcons = TRUE;
3487 SCIP_CONSHDLR* conshdlr,
3493 SCIP_Bool* infeasible
3496 char cutname[SCIP_MAXSTRLEN];
3497 SCIP_CONSDATA* consdata;
3498 SCIP_CONSHDLRDATA* conshdlrdata;
3512 assert( scip != NULL );
3513 assert( conshdlr != NULL );
3515 assert( infeasible != NULL );
3517 *infeasible = FALSE;
3519 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3520 assert( conshdlrdata != NULL );
3522 for (i = 0; i < nconss && !(*infeasible); ++i)
3524 consdata = SCIPconsGetData(conss[i]);
3525 assert( consdata != NULL );
3528 if ( consdata->blocksize == 1 )
3532 nvars = consdata->nvars;
3533 nnonz = consdata->nnonz;
3534 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3535 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nnonz) );
3538 for (v = 0; v < nvars; v++)
3540 assert( consdata->nvarnonz[v] <= 1 );
3542 for (j = 0; j < consdata->nvarnonz[v]; j++)
3544 assert( consdata->col[v][j] == 0 && consdata->row[v][j] == 0 );
3545 if ( ! SCIPisZero(scip, consdata->val[v][j]) )
3547 coeffs[cnt] = consdata->val[v][j];
3548 vars[cnt++] = consdata->vars[v];
3554 assert( consdata->constnnonz <= 1 );
3556 rhs = (consdata->constnnonz == 1) ? consdata->constval[0] : 0.0;
3563 snprintfreturn = SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"1x1block_%d", ++(conshdlrdata->n1x1blocks));
3564 assert( snprintfreturn < SCIP_MAXSTRLEN );
3566 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN,
"1x1block_%d", ++(conshdlrdata->n1x1blocks));
3569 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, cutname, cnt, vars, coeffs, rhs, SCIPinfinity(scip),
3570 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
3572 SCIP_CALL( SCIPaddCons(scip, cons) );
3573 #ifdef SCIP_MORE_DEBUG 3574 SCIPinfoMessage(scip, NULL,
"Added lp-constraint:\n");
3575 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
3576 SCIPinfoMessage(scip, NULL,
"\n");
3578 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3582 else if ( cnt == 1 )
3584 SCIP_Bool tightened;
3587 if ( SCIPisPositive(scip, coeffs[0]) )
3589 SCIP_CALL( SCIPtightenVarLb(scip, vars[0], rhs / coeffs[0], FALSE, infeasible, &tightened) );
3592 SCIPdebugMsg(scip,
"Tightend lower bound of <%s> to %g because of diagonal values of SDP-constraint %s!\n",
3593 SCIPvarGetName(vars[0]), SCIPvarGetLbGlobal(vars[0]), SCIPconsGetName(conss[i]));
3599 assert( SCIPisNegative(scip, coeffs[0]) );
3600 SCIP_CALL( SCIPtightenVarUb(scip, vars[0], rhs / coeffs[0], FALSE, infeasible, &tightened) );
3603 SCIPdebugMsg(scip,
"Tightend upper bound of <%s> to %g because of diagonal values of SDP-constraint %s!\n",
3604 SCIPvarGetName(vars[0]), SCIPvarGetUbGlobal(vars[0]), SCIPconsGetName(conss[i]));
3612 SCIPdebugMsg(scip,
"Detected 1x1 SDP-block without any nonzero coefficients \n");
3613 if ( SCIPisFeasGT(scip, rhs, 0.0) )
3615 SCIPdebugMsg(scip,
"Detected infeasibility in 1x1 SDP-block without any nonzero coefficients but with strictly positive rhs\n");
3621 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
3624 SCIPfreeBufferArray(scip, &coeffs);
3625 SCIPfreeBufferArray(scip, &vars);
3635 SCIP_CONSDATA* consdata,
3639 assert( scip != NULL );
3640 assert( consdata != NULL );
3641 assert( 0 <= v && v < consdata->nvars );
3643 if ( consdata->locks != NULL )
3645 assert( consdata->locks[v] == -2 || consdata->locks[v] == -1 || consdata->locks[v] == 0 || consdata->locks[v] == 1 );
3647 if ( consdata->locks[v] == 1 )
3649 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, 0, -1) );
3651 else if ( consdata->locks[v] == - 1 )
3653 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, -1, 0) );
3655 else if ( consdata->locks[v] == 0 )
3657 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, -1, -1) );
3672 SCIP_CONSDATA* consdata;
3673 SCIP_Real eigenvalue;
3678 assert( scip != NULL );
3679 assert( cons != NULL );
3681 consdata = SCIPconsGetData(cons);
3682 assert( consdata != NULL );
3683 assert( consdata->locks != NULL );
3684 assert( 0 <= v && v < consdata->nvars );
3687 if ( consdata->rankone )
3689 SCIP_CALL(
unlockVar(scip, consdata, v) );
3690 consdata->locks[v] = 0;
3691 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, 1, 1) );
3692 consdata->initallmatricespsd = FALSE;
3696 blocksize = consdata->blocksize;
3697 SCIP_CALL( SCIPallocBufferArray(scip, &Aj, blocksize * blocksize) );
3703 if ( SCIPisNegative(scip, eigenvalue) )
3706 consdata->allmatricespsd = FALSE;
3710 if ( SCIPisPositive(scip, eigenvalue) )
3714 consdata->allmatricespsd = FALSE;
3716 if ( SCIPisPositive(scip, eigenvalue) )
3725 SCIPfreeBufferArray(scip, &Aj);
3728 if ( newlock != consdata->locks[v] )
3730 SCIP_CALL(
unlockVar(scip, consdata, v) );
3733 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, 0, 1) );
3735 else if ( newlock == -1 )
3737 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, 1, 0) );
3739 else if ( newlock == 0 )
3741 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], SCIP_LOCKTYPE_MODEL, 1, 1) );
3744 assert( newlock == -2 );
3746 consdata->locks[v] = newlock;
3760 SCIP_CONSDATA* consdata;
3765 assert( scip != NULL );
3766 assert( cons != NULL );
3768 consdata = SCIPconsGetData(cons);
3769 assert( consdata != NULL );
3770 assert( consdata->locks != NULL );
3773 if ( consdata->rankone )
3775 for (v = 0; v < consdata->nvars; ++v)
3776 assert( consdata->locks[v] == 0 );
3780 blocksize = consdata->blocksize;
3781 SCIP_CALL( SCIPallocBufferArray(scip, &Aj, blocksize * blocksize) );
3783 for (v = 0; v < consdata->nvars; ++v)
3785 SCIP_Real eigenvalue;
3792 if ( SCIPisNegative(scip, eigenvalue) )
3795 if ( SCIPisPositive(scip, eigenvalue) )
3800 if ( SCIPisPositive(scip, eigenvalue) )
3809 assert( newlock == consdata->locks[v] );
3812 SCIPfreeBufferArray(scip, &Aj);
3824 SCIP_VAR** aggrvars,
3830 SCIP_Real* savedval,
3835 SCIP_CONSDATA* consdata;
3841 int aggrtargetlength;
3845 assert( scip != NULL );
3846 assert( cons != NULL );
3847 assert( scalars != NULL );
3848 assert( naggrvars > 0 );
3849 assert( savedcol != NULL );
3850 assert( savedrow != NULL );
3851 assert( savedval != NULL );
3852 assert( nfixednonz != NULL );
3854 consdata = SCIPconsGetData(cons);
3855 assert( consdata != NULL );
3856 assert( consdata->locks != NULL );
3857 assert( 0 <= v && v < consdata->nvars );
3860 SCIP_CALL(
unlockVar(scip, consdata, v) );
3863 rows = consdata->row[v];
3864 cols = consdata->col[v];
3865 vals = consdata->val[v];
3866 nvarnonz = consdata->nvarnonz[v];
3872 SCIP_CALL( SCIPreleaseVar(scip, &consdata->vars[v]) );
3873 consdata->col[v] = consdata->col[consdata->nvars - 1];
3874 consdata->row[v] = consdata->row[consdata->nvars - 1];
3875 consdata->val[v] = consdata->val[consdata->nvars - 1];
3876 consdata->nvarnonz[v] = consdata->nvarnonz[consdata->nvars - 1];
3877 consdata->vars[v] = consdata->vars[consdata->nvars - 1];
3878 consdata->locks[v] = consdata->locks[consdata->nvars - 1];
3879 (consdata->nvars)--;
3882 for (aggrind = 0; aggrind < naggrvars; aggrind++)
3884 int aggrconsind = -1;
3886 assert( ! SCIPisZero(scip, scalars[aggrind]) );
3889 for (i = 0; i < consdata->nvars; i++)
3891 if ( consdata->vars[i] == aggrvars[aggrind] )
3898 if ( aggrconsind > -1 )
3903 aggrtargetlength = consdata->nvarnonz[aggrconsind] + nvarnonz;
3904 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->row[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
3905 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->col[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
3906 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->val[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
3910 scalars[aggrind], consdata->row[aggrconsind], consdata->col[aggrconsind],
3911 consdata->val[aggrconsind], &(consdata->nvarnonz[aggrconsind]), aggrtargetlength) );
3914 assert( consdata->nvarnonz[aggrconsind] <= aggrtargetlength );
3915 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->row[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
3916 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->col[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
3917 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->val[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
3926 SCIPdebugMsg(scip,
"adding variable %s to SDP constraint %s because of (multi-)aggregation\n", SCIPvarGetName(aggrvars[aggrind]), SCIPconsGetName(cons));
3929 if ( consdata->nvars == *vararraylength )
3931 globalnvars = SCIPgetNVars(scip);
3934 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col, *vararraylength, globalnvars) );
3935 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row, *vararraylength, globalnvars) );
3936 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val, *vararraylength, globalnvars) );
3937 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nvarnonz, *vararraylength, globalnvars) );
3938 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, *vararraylength, globalnvars) );
3939 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->locks, *vararraylength, globalnvars) );
3940 *vararraylength = globalnvars;
3944 SCIP_CALL( SCIPcaptureVar(scip, aggrvars[aggrind]) );
3945 consdata->vars[consdata->nvars] = aggrvars[aggrind];
3948 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->col[consdata->nvars]), cols, nvarnonz) );
3949 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->row[consdata->nvars]), rows, nvarnonz) );
3952 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->val[consdata->nvars]), nvarnonz) );
3953 for (i = 0; i < nvarnonz; i++)
3956 if ( ! SCIPisZero(scip, scalars[aggrind] * vals[i]) )
3957 consdata->val[consdata->nvars][cnt++] = scalars[aggrind] * vals[i];
3959 consdata->nvarnonz[consdata->nvars] = cnt;
3961 consdata->locks[consdata->nvars] = -2;
3968 if ( ! SCIPisZero(scip, constant) )
3970 for (i = 0; i < nvarnonz; i++)
3972 savedcol[*nfixednonz] = cols[i];
3973 savedrow[*nfixednonz] = rows[i];
3974 savedval[*nfixednonz] = vals[i] * constant;
3980 SCIPfreeBlockMemoryArray(scip, &vals, nvarnonz);
3981 SCIPfreeBlockMemoryArray(scip, &rows, nvarnonz);
3982 SCIPfreeBlockMemoryArray(scip, &cols, nvarnonz);
4001 SCIP_CONSDATA* consdata;
4005 SCIP_Real* savedval;
4010 SCIP_VAR** aggrvars;
4022 assert( scip != NULL );
4023 assert( conss != NULL );
4024 assert( nconss >= 0 );
4026 SCIPdebugMsg(scip,
"Calling fixAndAggrVars with aggregate = %u.\n", aggregate);
4028 for (c = 0; c < nconss; ++c)
4032 assert( conss[c] != NULL );
4034 consdata = SCIPconsGetData(conss[c]);
4035 assert( consdata != NULL );
4036 assert( consdata->locks != NULL );
4037 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLR_NAME) == 0 );
4038 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
CONSHDLRRANK1_NAME) == 0 );
4041 SCIP_CALL( SCIPallocBufferArray(scip, &savedcol, consdata->nnonz) );
4042 SCIP_CALL( SCIPallocBufferArray(scip, &savedrow, consdata->nnonz) );
4043 SCIP_CALL( SCIPallocBufferArray(scip, &savedval, consdata->nnonz) );
4045 vararraylength = consdata->nvars;
4046 globalnvars = SCIPgetNVars(scip);
4048 for (v = 0; v < consdata->nvars; v++)
4050 SCIP_Bool negated = FALSE;
4053 if ( SCIPvarIsBinary(consdata->vars[v]) && SCIPvarIsNegated(consdata->vars[v]) )
4056 var = SCIPvarGetNegationVar(consdata->vars[v]);
4059 var = consdata->vars[v];
4062 if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) )
4064 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) );
4066 #ifdef SCIP_MORE_DEBUG 4067 SCIPdebugMsg(scip,
"<%s>: Treating globally fixed variable %s with value %f!\n", SCIPconsGetName(conss[c]), SCIPvarGetName(var), SCIPvarGetLbGlobal(var));
4070 if ( (! negated && ! SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0)) || (negated && SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0)) )
4075 for (i = 0; i < consdata->nvarnonz[v]; i++)
4077 savedcol[nfixednonz] = consdata->col[v][i];
4078 savedrow[nfixednonz] = consdata->row[v][i];
4082 savedval[nfixednonz] = consdata->val[v][i] * SCIPvarGetLbGlobal(var);
4084 savedval[nfixednonz] = consdata->val[v][i];
4093 consdata->nnonz -= consdata->nvarnonz[v];
4097 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->val[v]), consdata->nvarnonz[v]);
4098 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->row[v]), consdata->nvarnonz[v]);
4099 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->col[v]), consdata->nvarnonz[v]);
4102 SCIP_CALL(
unlockVar(scip, consdata, v) );
4105 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vars[v])) );
4106 if ( v < consdata->nvars -1 )
4108 consdata->col[v] = consdata->col[consdata->nvars - 1];
4109 consdata->row[v] = consdata->row[consdata->nvars - 1];
4110 consdata->val[v] = consdata->val[consdata->nvars - 1];
4111 consdata->nvarnonz[v] = consdata->nvarnonz[consdata->nvars - 1];
4112 consdata->vars[v] = consdata->vars[consdata->nvars - 1];
4113 consdata->locks[v] = consdata->locks[consdata->nvars - 1];
4118 else if ( aggregate && (SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) )
4120 SCIP_CALL( SCIPallocBufferArray(scip, &aggrvars, globalnvars) );
4121 SCIP_CALL( SCIPallocBufferArray(scip, &scalars, globalnvars) );
4126 aggrvars[0] = consdata->vars[v];
4134 aggrvars[0] = consdata->vars[v];
4141 SCIP_CALL( SCIPgetProbvarLinearSum(scip, aggrvars, scalars, &naggrvars, globalnvars, &constant, &requiredsize, TRUE) );
4142 assert( requiredsize <= globalnvars );
4146 if ( naggrvars == 0 )
4148 assert( ! negated );
4149 if ( ! SCIPisZero(scip, constant) )
4151 for (i = 0; i < consdata->nvarnonz[v]; i++)
4153 savedcol[nfixednonz] = consdata->col[v][i];
4154 savedrow[nfixednonz] = consdata->row[v][i];
4157 savedval[nfixednonz] = consdata->val[v][i] * constant;
4166 consdata->nnonz -= consdata->nvarnonz[v];
4170 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->val[v]), consdata->nvarnonz[v]);
4171 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->row[v]), consdata->nvarnonz[v]);
4172 SCIPfreeBlockMemoryArrayNull(scip, &(consdata->col[v]), consdata->nvarnonz[v]);
4175 SCIP_CALL(
unlockVar(scip, consdata, v) );
4178 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vars[v])) );
4179 if ( v < consdata->nvars -1 )
4181 consdata->col[v] = consdata->col[consdata->nvars - 1];
4182 consdata->row[v] = consdata->row[consdata->nvars - 1];
4183 consdata->val[v] = consdata->val[consdata->nvars - 1];
4184 consdata->nvarnonz[v] = consdata->nvarnonz[consdata->nvars - 1];
4185 consdata->vars[v] = consdata->vars[consdata->nvars - 1];
4186 consdata->locks[v] = consdata->locks[consdata->nvars - 1];
4195 if ( SCIPvarGetStatus(consdata->vars[v]) == SCIP_VARSTATUS_AGGREGATED )
4196 SCIPdebugMsg(scip,
"aggregating variable %s to ", SCIPvarGetName(var));
4198 SCIPdebugMsg(scip,
"multiaggregating variable %s to ", SCIPvarGetName(var));
4199 for (i = 0; i < naggrvars; i++)
4200 SCIPdebugMessagePrint(scip,
"+ %g %s ", scalars[i], SCIPvarGetName(aggrvars[i]));
4201 SCIPdebugMessagePrint(scip,
"+ %g.\n", constant);
4206 SCIP_CALL(
multiaggrVar(scip, conss[c], v, aggrvars, scalars, naggrvars, constant, savedcol, savedrow, savedval, &nfixednonz, &vararraylength) );
4210 SCIPfreeBufferArray(scip, &aggrvars);
4211 SCIPfreeBufferArray(scip, &scalars);
4213 else if ( negated && (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN) && aggregate )
4217 SCIPdebugMsg(scip,
"Changing variable %s to negation of variable <%s>!\n", SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(var));
4221 SCIP_CALL(
multiaggrVar(scip, conss[c], v, &var, &scalar, 1, 1.0, savedcol, savedrow, savedval, &nfixednonz, &vararraylength) );
4227 assert( consdata->nvars <= vararraylength );
4228 if ( consdata->nvars < vararraylength )
4230 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col, vararraylength, consdata->nvars) );
4231 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row, vararraylength, consdata->nvars) );
4232 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val, vararraylength, consdata->nvars) );
4233 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nvarnonz, vararraylength, consdata->nvars) );
4234 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, vararraylength, consdata->nvars) );
4235 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->locks, vararraylength, consdata->nvars) );
4239 arraylength = consdata->constnnonz + nfixednonz;
4240 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constcol), consdata->constnnonz, arraylength) );
4241 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constrow), consdata->constnnonz, arraylength) );
4242 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constval), consdata->constnnonz, arraylength) );
4245 SCIP_CALL(
SCIPsdpVarfixerMergeArrays(SCIPblkmem(scip), SCIPepsilon(scip), savedrow, savedcol, savedval, nfixednonz, FALSE, -1.0, consdata->constrow,
4246 consdata->constcol, consdata->constval, &(consdata->constnnonz), arraylength) );
4248 assert( consdata->constnnonz <= arraylength );
4251 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constcol), arraylength, consdata->constnnonz) );
4252 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constrow), arraylength, consdata->constnnonz) );
4253 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constval), arraylength, consdata->constnnonz) );
4256 SCIPfreeBufferArray(scip, &savedval);
4257 SCIPfreeBufferArray(scip, &savedrow);
4258 SCIPfreeBufferArray(scip, &savedcol);
4261 consdata->nnonz = 0;
4262 for (v = 0; v < consdata->nvars; v++)
4263 consdata->nnonz += consdata->nvarnonz[v];
4277 SCIP_Bool upperbound,
4281 SCIP_CONSDATA* consdata;
4284 assert( scip != NULL );
4285 assert( cons != NULL );
4287 consdata = SCIPconsGetData(cons);
4288 assert( consdata != NULL );
4290 SCIPdebugMsg(scip,
"Analyzing a conflict during propagation\n");
4293 if ( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && ! SCIPinProbing(scip)) || ! SCIPisConflictAnalysisApplicable(scip) )
4297 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
4299 assert( consdata->matrixvar != NULL );
4300 assert( consdata->matrixval != NULL );
4301 if ( consdata->matrixvar[diags] != NULL )
4303 assert( consdata->matrixval[diags] != SCIP_INVALID );
4305 if ( consdata->matrixval[diags] > 0.0 )
4306 SCIP_CALL( SCIPaddConflictUb(scip, consdata->matrixvar[diags], NULL) );
4308 SCIP_CALL( SCIPaddConflictLb(scip, consdata->matrixvar[diags], NULL) );
4311 if ( consdata->matrixvar[diagt] != NULL )
4313 assert( consdata->matrixval[diagt] != SCIP_INVALID );
4315 if ( consdata->matrixval[diagt] > 0.0 )
4316 SCIP_CALL( SCIPaddConflictUb(scip, consdata->matrixvar[diagt], NULL) );
4318 SCIP_CALL( SCIPaddConflictLb(scip, consdata->matrixvar[diagt], NULL) );
4323 assert( consdata->matrixvar[pos] != NULL);
4324 assert( consdata->matrixval[pos] != SCIP_INVALID);
4327 SCIP_CALL( SCIPaddConflictUb(scip, consdata->matrixvar[pos], NULL) );
4329 SCIP_CALL( SCIPaddConflictLb(scip, consdata->matrixvar[pos], NULL) );
4333 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, &success) );
4336 SCIPdebugMsg(scip,
"Succesfully analyzed and resolved conflict!\n");
4347 SCIP_Bool* infeasible,
4353 assert( infeasible != NULL );
4354 assert( nprop != NULL );
4356 *infeasible = FALSE;
4359 for (c = 0; c < nconss; ++c)
4361 SCIP_CONSDATA* consdata;
4365 assert( conss[c] != NULL );
4366 consdata = SCIPconsGetData(conss[c]);
4367 blocksize = consdata->blocksize;
4371 assert( consdata->matrixvar != NULL );
4372 assert( consdata->matrixval != NULL );
4373 assert( consdata->matrixconst != NULL );
4376 if ( consdata->tracebound < -1.5 )
4378 SCIP_CONSHDLR* linconshdlr;
4379 linconshdlr = SCIPfindConshdlr(scip,
"linear");
4380 if ( linconshdlr != NULL )
4382 SCIP_CONS** linconss;
4385 linconss = SCIPconshdlrGetConss(linconshdlr);
4386 nlinconss = SCIPconshdlrGetNConss(linconshdlr);
4388 for (i = 0; i < nlinconss; ++i)
4392 SCIP_Bool coefok = TRUE;
4396 nlinvars = SCIPgetNVarsLinear(scip, linconss[i]);
4399 if ( nlinvars != consdata->blocksize )
4402 linvars = SCIPgetVarsLinear(scip, linconss[i]);
4403 linvals = SCIPgetValsLinear(scip, linconss[i]);
4406 for (j = 0; j < nlinvars; ++j)
4411 if ( ! SCIPisEQ(scip, linvals[j], 1.0) )
4418 for (k = 0; k < consdata->blocksize; ++k)
4420 if ( consdata->matrixvar[k * (k + 1)/2 + k] == var )
4424 if ( k >= consdata->blocksize )
4426 SCIPdebugMsg(scip,
"Could not find variable <%s>.\n", SCIPvarGetName(linvars[j]));
4432 if ( j < nlinvars || ! coefok )
4435 consdata->tracebound = SCIPgetRhsLinear(scip, linconss[i]);
4436 SCIPdebugMsg(scip,
"Found tracebound constraint with bound = %g.\n", consdata->tracebound);
4440 if ( consdata->tracebound < -1.5 )
4441 consdata->tracebound = -1.0;
4445 if ( consdata->nsingle > 0 )
4451 for (s = 0; s < blocksize; ++s)
4454 SCIP_Real ubs = 0.0;
4457 diags = s * (s + 1)/2 + s;
4458 if ( consdata->matrixval[diags] == SCIP_INVALID )
4461 vars = consdata->matrixvar[diags];
4464 if ( consdata->matrixval[diags] > 0.0 )
4465 ubs = SCIPvarGetUbLocal(vars);
4467 ubs = SCIPvarGetLbLocal(vars);
4469 if ( SCIPisInfinity(scip, REALABS(ubs)) )
4472 ubs *= consdata->matrixval[diags];
4474 assert( consdata->matrixconst[diags] != SCIP_INVALID );
4475 assert( ! SCIPisInfinity(scip, ubs) );
4477 ubs -= consdata->matrixconst[diags];
4479 for (t = 0; t < s; ++t)
4481 SCIP_Bool tightened;
4485 SCIP_Real ubt = 0.0;
4489 pos = s * (s + 1)/2 + t;
4490 varst = consdata->matrixvar[pos];
4491 if ( varst == NULL || ! SCIPvarIsActive(varst) )
4494 diagt = t * (t + 1)/2 + t;
4495 if ( consdata->matrixval[diagt] == SCIP_INVALID )
4498 vart = consdata->matrixvar[diagt];
4501 if ( consdata->matrixval[diagt] > 0.0 )
4502 ubt = SCIPvarGetUbLocal(vart);
4504 ubt = SCIPvarGetLbLocal(vart);
4506 if ( SCIPisInfinity(scip, REALABS(ubt)) )
4509 ubt *= consdata->matrixval[diagt];
4511 assert( consdata->matrixconst[diagt] != SCIP_INVALID );
4512 assert( ! SCIPisInfinity(scip, ubt) );
4514 ubt -= consdata->matrixconst[diagt];
4516 if ( SCIPisFeasLT(scip, ubs, 0.0) || SCIPisFeasLT(scip, ubt, 0.0) )
4519 SCIP_CALL(
analyzeConflict(scip, conss[c], diags, diagt, pos, TRUE, FALSE) );
4524 if ( consdata->matrixval[pos] > 0.0 )
4525 bound = (sqrt(ubs * ubt) + consdata->matrixconst[pos]) / consdata->matrixval[pos];
4527 bound = (- sqrt(ubs * ubt) + consdata->matrixconst[pos]) / consdata->matrixval[pos];
4530 if ( consdata->tracebound > 0.0 )
4534 if ( consdata->tracebound/2.0 < bound )
4535 bound = consdata->tracebound/2.0;
4538 assert( varst != NULL );
4539 if ( SCIPisFeasLT(scip, bound, SCIPvarGetUbLocal(varst)) )
4541 SCIP_CALL( SCIPinferVarUbCons(scip, varst, bound, conss[c], s * blocksize + t, FALSE, infeasible, &tightened) );
4544 SCIPdebugMsg(scip,
"Propagation detected infeasibility, call analyzeConfilct.\n");
4545 SCIP_CALL(
analyzeConflict(scip, conss[c], diags, diagt, pos, TRUE, TRUE) );
4550 SCIPdebugMsg(scip,
"Propagation successfully tightened a bound.\n");
4556 if ( consdata->matrixval[pos] > 0.0 )
4557 bound = (- sqrt(ubs * ubt) + consdata->matrixconst[pos]) / consdata->matrixval[pos];
4559 bound = (sqrt(ubs * ubt) + consdata->matrixconst[pos]) / consdata->matrixval[pos];
4562 if ( consdata->tracebound > 0.0 )
4564 if ( -consdata->tracebound/2.0 > bound )
4565 bound = -consdata->tracebound/2.0;
4568 if ( SCIPisFeasGT(scip, bound, SCIPvarGetLbLocal(varst)) )
4570 SCIP_CALL( SCIPinferVarLbCons(scip, varst, bound, conss[c], s * blocksize + t, FALSE, infeasible, &tightened) );
4573 SCIPdebugMsg(scip,
"Propagation detected infeasibility, call analyzeConfilct.\n");
4574 SCIP_CALL(
analyzeConflict(scip, conss[c], diags, diagt, pos, FALSE, TRUE) );
4579 SCIPdebugMsg(scip,
"Propagation successfully tightened a bound.\n");
4592 #if ( SCIP_VERSION >= 800 || ( SCIP_VERSION < 800 && SCIP_APIVERSION >= 100 ) ) 4596 SCIP_DECL_NONLINCONSUPGD(consQuadConsUpgdSdp)
4598 char name[SCIP_MAXSTRLEN];
4599 SCIP_CONSHDLR* conshdlr;
4600 SCIP_CONSHDLRDATA* conshdlrdata;
4602 SCIP_VAR** linconsvars;
4603 SCIP_Real* linconsvals;
4604 SCIP_Real* linvalsterms;
4611 assert( scip != NULL );
4612 assert( cons != NULL );
4613 assert( nupgdconss != NULL );
4614 assert( upgdconss != NULL );
4619 if ( SCIPconsIsModifiable(cons) || SCIPconsIsStickingAtNode(cons) )
4623 if ( SCIPgetSubscipDepth(scip) > 0 )
4627 if ( SCIPgetNRuns(scip) > 1 )
4631 if ( upgdconsssize < 1 )
4638 if ( conshdlr == NULL )
4640 SCIPerrorMessage(
"rank 1 SDP constraint handler not found\n");
4641 return SCIP_PLUGINNOTFOUND;
4643 assert( conshdlr != NULL );
4645 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4646 assert( conshdlrdata != NULL );
4649 if ( ! conshdlrdata->sdpconshdlrdata->upgradequadconss )
4653 if ( conshdlrdata->sdpconshdlrdata->quadconsvars == NULL )
4655 SCIP_CONSHDLR* nonlinearconshdlr;
4672 SCIP_Real constval = -1.0;
4677 nvars = SCIPgetNTotalVars(scip);
4678 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars) );
4679 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars) );
4680 conshdlrdata->sdpconshdlrdata->nquadconsidx = nvars;
4681 for (j = 0; j < nvars; ++j)
4682 conshdlrdata->sdpconshdlrdata->quadconsidx[j] = -1;
4684 nonlinearconshdlr = SCIPfindConshdlr(scip,
"nonlinear");
4685 if ( nonlinearconshdlr == NULL )
4687 SCIPerrorMessage(
"Nonlinear constraint handler not found\n");
4688 return SCIP_PLUGINNOTFOUND;
4690 assert( nonlinearconshdlr != NULL );
4692 conss = SCIPconshdlrGetConss(nonlinearconshdlr);
4693 nconss = SCIPconshdlrGetNConss(nonlinearconshdlr);
4695 for (c = 0; c < nconss; ++c)
4697 SCIP_Bool isquadratic;
4699 assert( conss[c] != NULL );
4701 SCIP_CALL( SCIPcheckQuadraticNonlinear(scip, conss[c], &isquadratic) );
4702 if ( ! isquadratic )
4705 if ( ! SCIPexprAreQuadraticExprsVariables(SCIPgetExprNonlinear(conss[c])) )
4711 if ( nquadconss > conshdlrdata->sdpconshdlrdata->maxnvarsquadupgd )
4713 SCIPdebugMsg(scip,
"There are %d many quadratic constraints present in the problem, thus do not upgrade quadratic constraints to an SDPrank1 constraint.\n", nquadconss);
4714 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
4715 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
4719 #ifdef SCIP_MORE_DEBUG 4720 SCIPinfoMessage(scip, NULL,
"Found quadratic constraint to upgrade:\n");
4721 SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
4722 SCIPinfoMessage(scip, NULL,
"\n");
4725 SCIPexprGetQuadraticData(SCIPgetExprNonlinear(conss[c]), NULL, NULL, NULL, NULL, &nquadvarterms, &nbilinterms, NULL, NULL);
4726 assert( nquadvarterms + nbilinterms > 0 );
4728 for (i = 0; i < nquadvarterms; ++i)
4735 SCIPexprGetQuadraticQuadTerm(SCIPgetExprNonlinear(conss[c]), i, &expr, NULL, NULL, NULL, NULL, NULL);
4737 var = SCIPgetVarExprVar(expr);
4738 assert( var != NULL );
4739 idx = SCIPvarGetIndex(var);
4740 assert( 0 <= idx && idx < nvars );
4741 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
4743 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
4744 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
4748 for (i = 0; i < nbilinterms; ++i)
4756 SCIPexprGetQuadraticBilinTerm(SCIPgetExprNonlinear(conss[c]), i, &expr1, &expr2, NULL, NULL, NULL);
4758 var = SCIPgetVarExprVar(expr1);
4759 assert( var != NULL );
4760 idx = SCIPvarGetIndex(var);
4761 assert( 0 <= idx && idx < nvars );
4762 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
4764 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
4765 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
4768 var = SCIPgetVarExprVar(expr2);
4769 assert( var != NULL );
4770 idx = SCIPvarGetIndex(var);
4771 assert( 0 <= idx && idx < nvars );
4772 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
4774 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
4775 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
4781 if ( nsdpvars == 0 )
4783 SCIPdebugMsg(scip,
"No sdp variables have been added\n");
4784 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
4785 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
4791 if ( nsdpvars > conshdlrdata->sdpconshdlrdata->maxnvarsquadupgd )
4793 SCIPdebugMsg(scip,
"There are %d many variables present in the quadratic constraints, thus do not upgrade quadratic constraints to an SDPrank1 constraint\n", nsdpvars);
4794 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
4795 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
4800 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X, nsdpvars) );
4801 conshdlrdata->sdpconshdlrdata->nsdpvars = nsdpvars;
4803 for (i = 0; i < nsdpvars; ++i)
4809 var1 = conshdlrdata->sdpconshdlrdata->quadconsvars[i];
4810 assert( var1 != NULL );
4811 lb1 = SCIPvarGetLbGlobal(var1);
4812 ub1 = SCIPvarGetUbGlobal(var1);
4814 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X[i], nsdpvars) );
4816 for (j = 0; j <= i; ++j)
4818 SCIP_VARTYPE vartype;
4825 var2 = conshdlrdata->sdpconshdlrdata->quadconsvars[j];
4826 assert( var2 != NULL );
4827 lb2 = SCIPvarGetLbGlobal(var2);
4828 ub2 = SCIPvarGetUbGlobal(var2);
4830 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"X%d#%d", i, j);
4832 lb = MIN3(lb1 * lb2, lb1 * ub2, ub1 * lb2);
4833 lb = MIN(lb, ub1 * ub2);
4834 ub = MAX3(lb1 * lb2, lb1 * ub2, ub1 * lb2);
4835 ub = MAX(ub, ub1 * ub2);
4837 if ( SCIPvarIsBinary(var1) && SCIPvarIsBinary(var2) )
4838 vartype = SCIP_VARTYPE_BINARY;
4839 else if ( SCIPvarIsIntegral(var1) && SCIPvarIsIntegral(var2) )
4840 vartype = SCIP_VARTYPE_INTEGER;
4842 vartype = SCIP_VARTYPE_CONTINUOUS;
4844 SCIP_CALL( SCIPcreateVarBasic(scip, &(conshdlrdata->sdpconshdlrdata->X[i][j]), name, lb, ub, 0.0, vartype) );
4845 SCIP_CALL( SCIPaddVar(scip, conshdlrdata->sdpconshdlrdata->X[i][j]) );
4850 nnonz = nsdpvars + nsdpvars * (nsdpvars + 1) / 2;
4851 SCIP_CALL( SCIPallocBufferArray(scip, &cols, nnonz) );
4852 SCIP_CALL( SCIPallocBufferArray(scip, &rows, nnonz) );
4853 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nnonz) );
4854 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nnonz) );
4855 SCIP_CALL( SCIPallocBufferArray(scip, &nvarnonz, nnonz) );
4858 for (j = 0; j < nsdpvars; ++j)
4860 SCIP_CALL( SCIPallocBufferArray(scip, &cols[j], 1) );
4861 SCIP_CALL( SCIPallocBufferArray(scip, &rows[j], 1) );
4862 SCIP_CALL( SCIPallocBufferArray(scip, &vals[j], 1) );
4867 vars[j] = conshdlrdata->sdpconshdlrdata->quadconsvars[j];
4871 nvarscnt = nsdpvars;
4872 for (i = 0; i < nsdpvars; ++i)
4874 for (j = 0; j <= i; ++j)
4876 SCIP_CALL( SCIPallocBufferArray(scip, &cols[nvarscnt], 1) );
4877 SCIP_CALL( SCIPallocBufferArray(scip, &rows[nvarscnt], 1) );
4878 SCIP_CALL( SCIPallocBufferArray(scip, &vals[nvarscnt], 1) );
4879 nvarnonz[nvarscnt] = 1;
4880 cols[nvarscnt][0] = 1 + j;
4881 rows[nvarscnt][0] = 1 + i;
4882 vals[nvarscnt][0] = 1.0;
4883 vars[nvarscnt] = conshdlrdata->sdpconshdlrdata->X[i][j];
4887 assert( nvarscnt == nsdpvars + nsdpvars * (nsdpvars + 1)/2 );
4890 if ( conshdlrdata->sdpconshdlrdata->upgradekeepquad )
4892 SCIP_CALL(
SCIPcreateConsSdp(scip, &conshdlrdata->sdpconshdlrdata->sdpcons,
"QuadraticSDPcons", nvarscnt, nvarscnt, 1 + nsdpvars, nvarnonz,
4893 cols, rows, vals, vars, 1, &constcol, &constrow, &constval, FALSE) );
4894 SCIP_CALL( SCIPaddCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons) );
4898 SCIP_CALL(
SCIPcreateConsSdpRank1(scip, &conshdlrdata->sdpconshdlrdata->sdpcons,
"QuadraticSDPrank1cons", nvarscnt, nvarscnt, 1 + nsdpvars, nvarnonz,
4899 cols, rows, vals, vars, 1, &constcol, &constrow, &constval, FALSE) );
4900 SCIP_CALL( SCIPaddCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons) );
4903 #ifdef SCIP_MORE_DEBUG 4904 SCIPinfoMessage(scip, NULL,
"In upgrade of quadratic constraint the following SDPrank1 constraint has been added:\n");
4905 SCIP_CALL( SCIPprintCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons, NULL) );
4906 SCIPinfoMessage(scip, NULL,
"\n");
4910 for (j = nvarscnt - 1; j >= 0; --j)
4912 SCIPfreeBufferArray(scip, &vals[j]);
4913 SCIPfreeBufferArray(scip, &rows[j]);
4914 SCIPfreeBufferArray(scip, &cols[j]);
4916 SCIPfreeBufferArray(scip, &nvarnonz);
4917 SCIPfreeBufferArray(scip, &vars);
4918 SCIPfreeBufferArray(scip, &vals);
4919 SCIPfreeBufferArray(scip, &rows);
4920 SCIPfreeBufferArray(scip, &cols);
4924 if ( ! conshdlrdata->sdpconshdlrdata->upgradekeepquad )
4926 SCIP_EXPR** linexprs;
4931 SCIPexprGetQuadraticData(SCIPgetExprNonlinear(cons), NULL, &nlinvarterms, &linexprs, &linvalsterms, &nquadvarterms, &nbilinterms, NULL, NULL);
4935 nlinconsterms = nlinvarterms + 2 * nquadvarterms + nbilinterms;
4936 SCIP_CALL( SCIPallocBufferArray(scip, &linconsvars, nlinconsterms) );
4937 SCIP_CALL( SCIPallocBufferArray(scip, &linconsvals, nlinconsterms) );
4940 for (j = 0; j < nlinvarterms; ++j)
4942 linconsvals[cnt] = linvalsterms[j];
4944 SCIPexprGetQuadraticQuadTerm(SCIPgetExprNonlinear(cons), j, &expr, NULL, NULL, NULL, NULL, NULL);
4945 linconsvars[cnt] = SCIPgetVarExprVar(linexprs[j]);;
4946 assert( linconsvars[cnt] != NULL );
4949 assert( cnt == nlinvarterms );
4951 for (j = 0; j < nquadvarterms; ++j)
4959 SCIPexprGetQuadraticQuadTerm(SCIPgetExprNonlinear(cons), j, &expr, &lincoef, &sqrcoef, NULL, NULL, NULL);
4960 var = SCIPgetVarExprVar(expr);
4961 assert( var != NULL );
4963 idx = SCIPvarGetIndex(var);
4964 idx = conshdlrdata->sdpconshdlrdata->quadconsidx[idx];
4965 assert( 0 <= idx && idx < conshdlrdata->sdpconshdlrdata->nsdpvars );
4968 if ( ! SCIPisZero(scip, lincoef) )
4970 linconsvals[cnt] = lincoef;
4971 linconsvars[cnt] = var;
4972 assert( linconsvars[cnt] != NULL );
4977 if ( ! SCIPisZero(scip, sqrcoef) )
4979 linconsvals[cnt] = sqrcoef;
4980 linconsvars[cnt] = conshdlrdata->sdpconshdlrdata->X[idx][idx];
4981 assert( linconsvars[cnt] != NULL );
4985 SCIPdebugMsg(scip,
"New variable %s corresponds to squared original variable %s\n",
4986 SCIPvarGetName(conshdlrdata->sdpconshdlrdata->X[idx][idx]), SCIPvarGetName(var));
4988 assert( cnt <= nlinvarterms + 2 * nquadvarterms );
4990 for (j = 0; j < nbilinterms; ++j)
5001 SCIPexprGetQuadraticBilinTerm(SCIPgetExprNonlinear(cons), j, &expr1, &expr2, &coef, NULL, NULL);
5003 var1 = SCIPgetVarExprVar(expr1);
5004 assert( var1 != NULL );
5005 idx1 = SCIPvarGetIndex(var1);
5006 idx1 = conshdlrdata->sdpconshdlrdata->quadconsidx[idx1];
5007 assert( 0 <= idx1 && idx1 < conshdlrdata->sdpconshdlrdata->nsdpvars );
5009 var2 = SCIPgetVarExprVar(expr2);
5010 assert( var2 != NULL );
5011 idx2 = SCIPvarGetIndex(var2);
5012 idx2 = conshdlrdata->sdpconshdlrdata->quadconsidx[idx2];
5013 assert( 0 <= idx2 && idx2 < conshdlrdata->sdpconshdlrdata->nsdpvars );
5016 SCIPswapInts(&idx1, &idx2);
5018 linconsvals[cnt] = coef;
5019 linconsvars[cnt] = conshdlrdata->sdpconshdlrdata->X[idx1][idx2];
5020 assert( linconsvars[cnt] != NULL );
5023 SCIPdebugMsg(scip,
"New variable %s corresponds to product of original variables %s and %s\n",
5024 SCIPvarGetName(conshdlrdata->sdpconshdlrdata->X[idx1][idx2]), SCIPvarGetName(var1), SCIPvarGetName(var2));
5026 assert( cnt <= nlinvarterms + 2 * nquadvarterms + nbilinterms );
5028 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"lin_%s", SCIPconsGetName(cons));
5029 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, name, cnt, linconsvars, linconsvals, SCIPgetLhsNonlinear(cons), SCIPgetRhsNonlinear(cons),
5030 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
5031 FALSE, SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), FALSE) );
5033 #ifdef SCIP_MORE_DEBUG 5034 SCIPinfoMessage(scip, NULL,
"In upgrade of quadratic constraint the following linear constraint has been added:\n");
5035 SCIP_CALL( SCIPprintCons(scip, lincons, NULL) );
5036 SCIPinfoMessage(scip, NULL,
"\n");
5040 upgdconss[0] = lincons;
5043 SCIPfreeBufferArray(scip, &linconsvals);
5044 SCIPfreeBufferArray(scip, &linconsvars);
5053 conshdlrdata->sdpconshdlrdata->upgradequadconss = FALSE;
5068 char name[SCIP_MAXSTRLEN];
5069 SCIP_CONSHDLR* conshdlr;
5070 SCIP_CONSHDLRDATA* conshdlrdata;
5072 SCIP_VAR** linconsvars;
5073 SCIP_Real* linconsvals;
5074 SCIP_VAR** linvarsterms;
5075 SCIP_Real* linvalsterms;
5076 SCIP_QUADVARTERM* quadvarterms;
5077 SCIP_BILINTERM* bilinterms;
5084 assert( scip != NULL );
5085 assert( cons != NULL );
5086 assert( nupgdconss != NULL );
5087 assert( upgdconss != NULL );
5092 if ( SCIPconsIsModifiable(cons) || SCIPconsIsStickingAtNode(cons) )
5096 if ( SCIPgetSubscipDepth(scip) > 0 )
5100 if ( SCIPgetNRuns(scip) > 1 )
5104 if ( upgdconsssize < 1 )
5111 if ( conshdlr == NULL )
5113 SCIPerrorMessage(
"rank 1 SDP constraint handler not found\n");
5114 return SCIP_PLUGINNOTFOUND;
5116 assert( conshdlr != NULL );
5118 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5119 assert( conshdlrdata != NULL );
5122 if ( ! conshdlrdata->sdpconshdlrdata->upgradequadconss )
5126 if ( conshdlrdata->sdpconshdlrdata->quadconsvars == NULL )
5128 SCIP_CONSHDLR* quadconshdlr;
5145 SCIP_Real constval = -1.0;
5149 nvars = SCIPgetNTotalVars(scip);
5150 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars) );
5151 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars) );
5152 conshdlrdata->sdpconshdlrdata->nquadconsidx = nvars;
5153 for (j = 0; j < nvars; ++j)
5154 conshdlrdata->sdpconshdlrdata->quadconsidx[j] = -1;
5156 quadconshdlr = SCIPfindConshdlr(scip,
"quadratic");
5157 if ( quadconshdlr == NULL )
5159 SCIPerrorMessage(
"Quadratic constraint handler not found\n");
5160 return SCIP_PLUGINNOTFOUND;
5162 assert( quadconshdlr != NULL );
5164 conss = SCIPconshdlrGetConss(quadconshdlr);
5165 nconss = SCIPconshdlrGetNConss(quadconshdlr);
5168 if ( nconss > conshdlrdata->sdpconshdlrdata->maxnvarsquadupgd )
5170 SCIPdebugMsg(scip,
"There are %d many quadratic constraints present in the problem, thus do not upgrade quadratic constraints to an SDPrank1 constraint\n", nconss);
5171 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
5172 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
5176 for (c = 0; c < nconss; ++c)
5178 assert( conss[c] != NULL );
5179 #ifdef SCIP_MORE_DEBUG 5180 SCIPinfoMessage(scip, NULL,
"Found quadratic constraint to upgrade:\n");
5181 SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
5182 SCIPinfoMessage(scip, NULL,
"\n");
5184 nquadvarterms = SCIPgetNQuadVarTermsQuadratic(scip, conss[c]);
5185 quadvarterms = SCIPgetQuadVarTermsQuadratic(scip, conss[c]);
5187 for (i = 0; i < nquadvarterms; ++i)
5192 assert( quadvarterms != NULL );
5193 var = quadvarterms[i].var;
5194 idx = SCIPvarGetIndex(var);
5195 assert( 0 <= idx && idx < nvars );
5196 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
5198 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
5199 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
5203 nbilinterms = SCIPgetNBilinTermsQuadratic(scip, conss[c]);
5204 bilinterms = SCIPgetBilinTermsQuadratic(scip, conss[c]);
5206 for (i = 0; i < nbilinterms; ++i)
5211 assert( bilinterms != NULL );
5212 var = bilinterms[i].var1;
5213 idx = SCIPvarGetIndex(var);
5214 assert( 0 <= idx && idx < nvars );
5215 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
5217 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
5218 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
5221 var = bilinterms[i].var2;
5222 idx = SCIPvarGetIndex(var);
5223 assert( 0 <= idx && idx < nvars );
5224 if ( conshdlrdata->sdpconshdlrdata->quadconsidx[idx] < 0 )
5226 conshdlrdata->sdpconshdlrdata->quadconsvars[nsdpvars] = var;
5227 conshdlrdata->sdpconshdlrdata->quadconsidx[idx] = nsdpvars++;
5233 if ( nsdpvars == 0 )
5235 SCIPdebugMsg(scip,
"No sdp variables have been added\n");
5236 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
5237 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
5243 if ( nsdpvars > conshdlrdata->sdpconshdlrdata->maxnvarsquadupgd )
5245 SCIPdebugMsg(scip,
"There are %d many variables present in the quadratic constraints, thus do not upgrade quadratic constraints to an SDPrank1 constraint\n", nsdpvars);
5246 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, nvars);
5247 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, nvars);
5252 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X, nsdpvars) );
5253 conshdlrdata->sdpconshdlrdata->nsdpvars = nsdpvars;
5255 for (i = 0; i < nsdpvars; ++i)
5261 var1 = conshdlrdata->sdpconshdlrdata->quadconsvars[i];
5262 assert( var1 != NULL );
5263 lb1 = SCIPvarGetLbGlobal(var1);
5264 ub1 = SCIPvarGetUbGlobal(var1);
5266 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X[i], nsdpvars) );
5268 for (j = 0; j <= i; ++j)
5270 SCIP_VARTYPE vartype;
5277 var2 = conshdlrdata->sdpconshdlrdata->quadconsvars[j];
5278 assert( var2 != NULL );
5279 lb2 = SCIPvarGetLbGlobal(var2);
5280 ub2 = SCIPvarGetUbGlobal(var2);
5282 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"X%d#%d", i, j);
5284 lb = MIN3(lb1 * lb2, lb1 * ub2, ub1 * lb2);
5285 lb = MIN(lb, ub1 * ub2);
5286 ub = MAX3(lb1 * lb2, lb1 * ub2, ub1 * lb2);
5287 ub = MAX(ub, ub1 * ub2);
5289 if ( SCIPvarIsBinary(var1) && SCIPvarIsBinary(var2) )
5290 vartype = SCIP_VARTYPE_BINARY;
5291 else if ( SCIPvarIsIntegral(var1) && SCIPvarIsIntegral(var2) )
5292 vartype = SCIP_VARTYPE_INTEGER;
5294 vartype = SCIP_VARTYPE_CONTINUOUS;
5296 SCIP_CALL( SCIPcreateVarBasic(scip, &(conshdlrdata->sdpconshdlrdata->X[i][j]), name, lb, ub, 0.0, vartype) );
5297 SCIP_CALL( SCIPaddVar(scip, conshdlrdata->sdpconshdlrdata->X[i][j]) );
5302 nnonz = nsdpvars + nsdpvars * (nsdpvars + 1) / 2;
5303 SCIP_CALL( SCIPallocBufferArray(scip, &cols, nnonz) );
5304 SCIP_CALL( SCIPallocBufferArray(scip, &rows, nnonz) );
5305 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nnonz) );
5306 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nnonz) );
5307 SCIP_CALL( SCIPallocBufferArray(scip, &nvarnonz, nnonz) );
5310 for (j = 0; j < nsdpvars; ++j)
5312 SCIP_CALL( SCIPallocBufferArray(scip, &cols[j], 1) );
5313 SCIP_CALL( SCIPallocBufferArray(scip, &rows[j], 1) );
5314 SCIP_CALL( SCIPallocBufferArray(scip, &vals[j], 1) );
5319 vars[j] = conshdlrdata->sdpconshdlrdata->quadconsvars[j];
5323 nvarscnt = nsdpvars;
5324 for (i = 0; i < nsdpvars; ++i)
5326 for (j = 0; j <= i; ++j)
5328 SCIP_CALL( SCIPallocBufferArray(scip, &cols[nvarscnt], 1) );
5329 SCIP_CALL( SCIPallocBufferArray(scip, &rows[nvarscnt], 1) );
5330 SCIP_CALL( SCIPallocBufferArray(scip, &vals[nvarscnt], 1) );
5331 nvarnonz[nvarscnt] = 1;
5332 cols[nvarscnt][0] = 1 + j;
5333 rows[nvarscnt][0] = 1 + i;
5334 vals[nvarscnt][0] = 1.0;
5335 vars[nvarscnt] = conshdlrdata->sdpconshdlrdata->X[i][j];
5339 assert( nvarscnt == nsdpvars + nsdpvars * (nsdpvars + 1)/2 );
5342 if ( conshdlrdata->sdpconshdlrdata->upgradekeepquad )
5344 SCIP_CALL(
SCIPcreateConsSdp(scip, &conshdlrdata->sdpconshdlrdata->sdpcons,
"QuadraticSDPcons", nvarscnt, nvarscnt, 1 + nsdpvars, nvarnonz,
5345 cols, rows, vals, vars, 1, &constcol, &constrow, &constval, FALSE) );
5346 SCIP_CALL( SCIPaddCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons) );
5350 SCIP_CALL(
SCIPcreateConsSdpRank1(scip, &conshdlrdata->sdpconshdlrdata->sdpcons,
"QuadraticSDPrank1cons", nvarscnt, nvarscnt, 1 + nsdpvars, nvarnonz,
5351 cols, rows, vals, vars, 1, &constcol, &constrow, &constval, FALSE) );
5352 SCIP_CALL( SCIPaddCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons) );
5355 #ifdef SCIP_MORE_DEBUG 5356 SCIPinfoMessage(scip, NULL,
"In upgrade of quadratic constraint the following SDPrank1 constraint has been added:\n");
5357 SCIP_CALL( SCIPprintCons(scip, conshdlrdata->sdpconshdlrdata->sdpcons, NULL) );
5358 SCIPinfoMessage(scip, NULL,
"\n");
5362 for (j = nvarscnt - 1; j >= 0; --j)
5364 SCIPfreeBufferArray(scip, &vals[j]);
5365 SCIPfreeBufferArray(scip, &rows[j]);
5366 SCIPfreeBufferArray(scip, &cols[j]);
5368 SCIPfreeBufferArray(scip, &nvarnonz);
5369 SCIPfreeBufferArray(scip, &vars);
5370 SCIPfreeBufferArray(scip, &vals);
5371 SCIPfreeBufferArray(scip, &rows);
5372 SCIPfreeBufferArray(scip, &cols);
5375 if ( ! conshdlrdata->sdpconshdlrdata->upgradekeepquad )
5380 nlinvarterms = SCIPgetNLinearVarsQuadratic(scip, cons);
5381 linvarsterms = SCIPgetLinearVarsQuadratic(scip, cons);
5382 linvalsterms = SCIPgetCoefsLinearVarsQuadratic(scip, cons);
5383 nquadvarterms = SCIPgetNQuadVarTermsQuadratic(scip, cons);
5384 quadvarterms = SCIPgetQuadVarTermsQuadratic(scip, cons);
5385 nbilinterms = SCIPgetNBilinTermsQuadratic(scip, cons);
5386 bilinterms = SCIPgetBilinTermsQuadratic(scip, cons);
5390 nlinconsterms = nlinvarterms + 2 * nquadvarterms + nbilinterms;
5391 SCIP_CALL( SCIPallocBufferArray(scip, &linconsvars, nlinconsterms) );
5392 SCIP_CALL( SCIPallocBufferArray(scip, &linconsvals, nlinconsterms) );
5395 for (j = 0; j < nlinvarterms; ++j)
5397 linconsvals[cnt] = linvalsterms[j];
5398 linconsvars[cnt] = linvarsterms[j];
5399 assert( linconsvars[cnt] != NULL );
5402 assert( cnt == nlinvarterms );
5403 for (j = 0; j < nquadvarterms; ++j)
5407 idx = SCIPvarGetIndex(quadvarterms[j].var);
5408 idx = conshdlrdata->sdpconshdlrdata->quadconsidx[idx];
5409 assert( 0 <= idx && idx < conshdlrdata->sdpconshdlrdata->nsdpvars );
5412 if ( ! SCIPisZero(scip, quadvarterms[j].lincoef) )
5414 linconsvals[cnt] = quadvarterms[j].lincoef;
5415 linconsvars[cnt] = quadvarterms[j].var;
5416 assert( linconsvars[cnt] != NULL );
5421 if ( ! SCIPisZero(scip, quadvarterms[j].sqrcoef) )
5423 linconsvals[cnt] = quadvarterms[j].sqrcoef;
5424 linconsvars[cnt] = conshdlrdata->sdpconshdlrdata->X[idx][idx];
5425 assert( linconsvars[cnt] != NULL );
5429 SCIPdebugMsg(scip,
"New variable %s corresponds to squared original variable %s\n",
5430 SCIPvarGetName(conshdlrdata->sdpconshdlrdata->X[idx][idx]), SCIPvarGetName(quadvarterms[j].var));
5432 assert( cnt <= nlinvarterms + 2 * nquadvarterms );
5434 for (j = 0; j < nbilinterms; ++j)
5439 idx1 = SCIPvarGetIndex(bilinterms[j].var1);
5440 idx1 = conshdlrdata->sdpconshdlrdata->quadconsidx[idx1];
5441 assert( 0 <= idx1 && idx1 < conshdlrdata->sdpconshdlrdata->nsdpvars );
5443 idx2 = SCIPvarGetIndex(bilinterms[j].var2);
5444 idx2 = conshdlrdata->sdpconshdlrdata->quadconsidx[idx2];
5445 assert( 0 <= idx2 && idx2 < conshdlrdata->sdpconshdlrdata->nsdpvars );
5448 SCIPswapInts(&idx1, &idx2);
5450 linconsvals[cnt] = bilinterms[j].coef;
5451 linconsvars[cnt] = conshdlrdata->sdpconshdlrdata->X[idx1][idx2];
5452 assert( linconsvars[cnt] != NULL );
5455 SCIPdebugMsg(scip,
"New variable %s corresponds to product of original variables %s and %s\n",
5456 SCIPvarGetName(conshdlrdata->sdpconshdlrdata->X[idx1][idx2]), SCIPvarGetName(bilinterms[j].var1), SCIPvarGetName(bilinterms[j].var2));
5458 assert( cnt <= nlinvarterms + 2 * nquadvarterms + nbilinterms );
5460 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN,
"lin_%s", SCIPconsGetName(cons));
5461 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, name, cnt, linconsvars, linconsvals, SCIPgetLhsQuadratic(scip, cons), SCIPgetRhsQuadratic(scip, cons),
5462 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
5463 FALSE, SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), FALSE) );
5465 #ifdef SCIP_MORE_DEBUG 5466 SCIPinfoMessage(scip, NULL,
"In upgrade of quadratic constraint the following linear constraint has been added:\n");
5467 SCIP_CALL( SCIPprintCons(scip, lincons, NULL) );
5468 SCIPinfoMessage(scip, NULL,
"\n");
5472 upgdconss[0] = lincons;
5475 SCIPfreeBufferArray(scip, &linconsvals);
5476 SCIPfreeBufferArray(scip, &linconsvars);
5485 conshdlrdata->sdpconshdlrdata->upgradequadconss = FALSE;
5502 SCIP_CONSHDLRDATA* conshdlrdata;
5504 assert( conshdlr != NULL );
5506 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5507 assert( conshdlrdata != NULL );
5509 conshdlrdata->neigveccuts = 0;
5510 conshdlrdata->ndiaggezerocuts = 0;
5511 conshdlrdata->n1x1blocks = 0;
5521 SCIP_CONSDATA* consdata;
5525 consdata = SCIPconsGetData(cons);
5526 assert( consdata != NULL );
5527 nvars = consdata->nvars;
5529 SCIPdebugMsg(scip,
"locking method of <%s>.\n", SCIPconsGetName(cons));
5532 if ( consdata->rankone )
5534 if ( consdata->locks == NULL )
5535 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->locks, nvars) );
5537 for (v = 0; v < consdata->nvars; ++v)
5539 consdata->locks[v] = 0;
5540 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5546 if ( consdata->locks == NULL )
5548 SCIP_Real mineigenvalue = SCIP_REAL_MAX;
5549 SCIP_Real eigenvalue;
5552 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->locks, nvars) );
5554 blocksize = consdata->blocksize;
5556 SCIP_CALL( SCIPallocBufferArray(scip, &Aj, blocksize * blocksize) );
5558 for (v = 0; v < nvars; v++)
5561 consdata->locks[v] = -2;
5565 if ( SCIPisNegative(scip, eigenvalue) )
5569 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlocksneg, nlockspos) );
5570 consdata->locks[v] = 1;
5572 if ( eigenvalue < mineigenvalue )
5573 mineigenvalue = eigenvalue;
5576 if ( SCIPisPositive(scip, eigenvalue) )
5580 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlockspos, nlocksneg) );
5581 consdata->locks[v] = -1;
5587 if ( SCIPisPositive(scip, eigenvalue) )
5591 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlockspos, nlocksneg) );
5592 if ( consdata->locks[v] == 1 )
5594 consdata->locks[v] = 0;
5597 consdata->locks[v] = -1;
5602 if ( SCIPisFeasGE(scip, mineigenvalue, 0.0) )
5604 consdata->allmatricespsd = TRUE;
5605 if ( SCIPgetSubscipDepth(scip) == 0 )
5606 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"All matrices are positive semidefinite (minimial eigenvalue: %g).\n", mineigenvalue);
5608 consdata->initallmatricespsd = TRUE;
5610 SCIPfreeBufferArray(scip, &Aj);
5617 for (v = 0; v < nvars; v++)
5619 if ( consdata->locks[v] == 1 )
5621 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlocksneg, nlockspos) );
5623 else if ( consdata->locks[v] == -1 )
5625 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlockspos, nlocksneg) );
5627 else if ( consdata->locks[v] == 0 )
5629 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[v], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5632 assert( consdata->locks[v] == -2 );
5646 SCIP_CONSHDLRDATA* conshdlrdata;
5648 assert(scip != NULL);
5650 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5651 assert(conshdlrdata != NULL);
5654 conshdlrdata->sdpconshdlrdata->triedlinearconss = FALSE;
5655 conshdlrdata->sdpconshdlrdata->triedvarbounds = FALSE;
5664 SCIP_CONSHDLRDATA* conshdlrdata;
5668 assert( scip != NULL );
5669 assert( conshdlr != NULL );
5671 if ( conss == NULL )
5674 SCIPdebugMsg(scip,
"Exitpre method of conshdlr <%s>.\n", SCIPconshdlrGetName(conshdlr));
5676 if ( SCIPgetStatus(scip) != SCIP_STATUS_OPTIMAL && SCIPgetStatus(scip) != SCIP_STATUS_INFEASIBLE )
5681 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5682 assert( conshdlrdata != NULL );
5684 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->sdpconshdlrdata->quadconsidx, conshdlrdata->sdpconshdlrdata->nquadconsidx);
5685 SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->sdpconshdlrdata->quadconsvars, conshdlrdata->sdpconshdlrdata->nquadconsidx);
5686 if ( conshdlrdata->sdpconshdlrdata->X != NULL )
5688 SCIPdebugMsg(scip,
"Releasing additional variables from upgrading method\n");
5689 for (i = 0; i < conshdlrdata->sdpconshdlrdata->nsdpvars; ++i)
5691 for (j = 0; j <= i; ++j)
5693 SCIP_CALL( SCIPreleaseVar(scip, &(conshdlrdata->sdpconshdlrdata->X[i][j])) );
5695 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X[i], conshdlrdata->sdpconshdlrdata->nsdpvars);
5697 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->sdpconshdlrdata->X, conshdlrdata->sdpconshdlrdata->nsdpvars);
5700 if ( conshdlrdata->sdpconshdlrdata->sdpcons != NULL )
5702 SCIPdebugMsg(scip,
"Releasing constraint %s from upgrading method\n", SCIPconsGetName(conshdlrdata->sdpconshdlrdata->sdpcons) );
5703 SCIP_CALL( SCIPreleaseCons(scip, &conshdlrdata->sdpconshdlrdata->sdpcons) );
5718 SCIP_CONSHDLRDATA* conshdlrdata;
5720 assert( scip != NULL );
5721 assert( conshdlr != NULL );
5723 if ( conss == NULL )
5726 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5727 assert( conshdlrdata != NULL );
5729 if ( (conshdlrdata->sdpconshdlrdata->sparsifycut || conshdlrdata->sdpconshdlrdata->multiplesparsecuts) && conshdlrdata->randnumgen == NULL )
5731 SCIP_CALL( SCIPcreateRandom(scip, &conshdlrdata->randnumgen, 64293, FALSE) );
5734 conshdlrdata->relaxsdp = SCIPfindRelax(scip,
"SDP");
5737 if ( SCIPgetSubscipDepth(scip) == 0 && conshdlrdata->sdpconshdlrdata->quadconsrank1 )
5741 SCIPdebugMsg(scip,
"Added %d quadratic constraints for rank 1 constraints.\n", naddconss);
5744 conshdlrdata->sdpconshdlrdata->upgradequadconss = FALSE;
5754 SCIP_CONSHDLRDATA* conshdlrdata;
5755 SCIP_Bool infeasible;
5758 assert( conshdlr != NULL );
5759 assert( result != NULL );
5761 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5762 assert( conshdlrdata != NULL );
5764 *result = SCIP_DIDNOTRUN;
5767 if ( conshdlrdata->sdpconshdlrdata->propupperbounds )
5769 *result = SCIP_DIDNOTFIND;
5771 SCIPdebugMsg(scip,
"Propagate upper bounds of conshdlr <%s> ...\n", SCIPconshdlrGetName(conshdlr));
5777 SCIPdebugMsg(scip,
"Propagation detected cutoff.\n");
5778 *result = SCIP_CUTOFF;
5784 SCIPdebugMsg(scip,
"Propagation tightened %d bounds.\n", nprop);
5785 *result = SCIP_REDUCEDDOM;
5791 if ( conshdlrdata->sdpconshdlrdata->proptightenbounds )
5794 if ( conshdlrdata->sdpconshdlrdata->proptbprobing || ! SCIPinProbing(scip) )
5796 if ( *result == SCIP_DIDNOTRUN )
5797 *result = SCIP_DIDNOTFIND;
5799 SCIPdebugMsg(scip,
"Propagate tighten bounds of conshdlr <%s> ...\n", SCIPconshdlrGetName(conshdlr));
5802 SCIP_CALL(
tightenBounds(scip, conss, nconss, conshdlrdata->sdpconshdlrdata->tightenboundscont, &nprop, &infeasible) );
5806 SCIPdebugMsg(scip,
"Propagation detected cutoff.\n");
5807 *result = SCIP_CUTOFF;
5813 SCIPdebugMsg(scip,
"Propagation tightened %d bounds.\n", nprop);
5814 *result = SCIP_REDUCEDDOM;
5827 SCIP_CONSDATA* consdata;
5833 assert( conshdlr != NULL );
5834 assert( cons != NULL );
5835 assert( infervar != NULL );
5836 assert( result != NULL );
5838 consdata = SCIPconsGetData(cons);
5839 assert( consdata != NULL );
5840 assert( consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLR_NAME) == 0 );
5841 assert( ! consdata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLRRANK1_NAME) == 0 );
5843 SCIPdebugMsg(scip,
"Executing conflict resolving method of <%s> constraint handler.\n", SCIPconshdlrGetName(conshdlr));
5846 if ( inferinfo >= 0 )
5848 s = inferinfo / consdata->blocksize;
5849 t = inferinfo % consdata->blocksize;
5850 assert( 0 <= s && s < consdata->blocksize );
5851 assert( 0 <= t && t < consdata->blocksize );
5852 assert( consdata->matrixvar[s * (s + 1)/2 + t] == infervar );
5854 diags = s * (s + 1)/2 + s;
5855 diagt = t * (t + 1)/2 + t;
5857 assert( consdata->matrixvar[diags] != NULL );
5858 assert( consdata->matrixvar[diagt] != NULL );
5859 assert( consdata->matrixval[diags] != SCIP_INVALID );
5860 assert( consdata->matrixval[diagt] != SCIP_INVALID );
5862 if ( consdata->matrixval[diags] > 0.0 )
5863 SCIP_CALL( SCIPaddConflictUb(scip, consdata->matrixvar[diags], bdchgidx) );
5865 SCIP_CALL( SCIPaddConflictLb(scip, consdata->matrixvar[diags], bdchgidx) );
5867 if ( consdata->matrixval[diagt] > 0.0 )
5868 SCIP_CALL( SCIPaddConflictUb(scip, consdata->matrixvar[diagt], bdchgidx) );
5870 SCIP_CALL( SCIPaddConflictLb(scip, consdata->matrixvar[diagt], bdchgidx) );
5872 *result = SCIP_SUCCESS;
5881 assert( 0 <= i && i < consdata->nvars );
5884 for (k = 0; k < consdata->nvars; ++k)
5889 SCIP_CALL( SCIPaddConflictUb(scip, consdata->vars[k], bdchgidx) );
5891 *result = SCIP_SUCCESS;
5901 SCIP_CONSHDLRDATA* conshdlrdata;
5902 SCIP_Bool infeasible;
5906 assert( conshdlr != NULL );
5907 assert( result != NULL );
5909 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5910 assert( conshdlrdata != NULL );
5912 *result = SCIP_DIDNOTRUN;
5915 if ( nnewfixedvars + nnewaggrvars > 0 )
5922 for (c = 0; c < nconss && *result != SCIP_CUTOFF; ++c)
5924 SCIP_CONSDATA* consdata;
5926 assert( conss[c] != NULL );
5927 consdata = SCIPconsGetData(conss[c]);
5928 assert( consdata != NULL );
5931 if ( consdata->nvars <= 0 )
5933 SCIP_Real* constmatrix;
5934 SCIP_Real eigenvalue;
5937 blocksize = consdata->blocksize;
5938 SCIP_CALL( SCIPallocBufferArray(scip, &constmatrix, blocksize * blocksize) );
5943 if ( SCIPisFeasPositive(scip, eigenvalue) )
5945 SCIPdebugMsg(scip,
"Infeasible constraint <%s> containts no variable.\n", SCIPconsGetName(conss[c]));
5946 *result = SCIP_CUTOFF;
5950 SCIPdebugMsg(scip,
"Feasible constraint <%s> containts no variable, removing.\n", SCIPconsGetName(conss[c]));
5951 SCIP_CALL( SCIPdelConsLocal(scip, conss[c]) );
5953 *result = SCIP_SUCCESS;
5955 SCIPfreeBufferArray(scip, &constmatrix);
5957 else if ( *result == SCIP_DIDNOTRUN )
5958 *result = SCIP_DIDNOTFIND;
5961 if ( *result == SCIP_CUTOFF )
5965 if ( conshdlrdata->sdpconshdlrdata->propubpresol )
5967 SCIPdebugMsg(scip,
"Propagate upper bounds of conshdlr <%s> ...\n", SCIPconshdlrGetName(conshdlr));
5973 SCIPdebugMsg(scip,
"Presolving detected cutoff.\n");
5974 *result = SCIP_CUTOFF;
5979 SCIPdebugMsg(scip,
"Presolving upper bounds: %d.\n", nprop);
5983 *result = SCIP_SUCCESS;
5989 if ( SCIPconshdlrGetNPresolCalls(conshdlr) == 0 )
5996 if ( *result == SCIP_DIDNOTRUN )
5997 *result = SCIP_DIDNOTFIND;
5999 noldaddconss = *naddconss;
6000 nolddelconss = *ndelconss;
6001 noldchgbds = *nchgbds;
6002 noldchgcoefs = *nchgcoefs;
6004 SCIP_CALL(
move_1x1_blocks_to_lp(scip, conshdlr, conss, nconss, naddconss, ndelconss, nchgbds, &infeasible) );
6007 *result = SCIP_CUTOFF;
6010 if ( noldaddconss != *naddconss || nolddelconss != *ndelconss || noldchgbds != *nchgbds )
6011 *result = SCIP_SUCCESS;
6014 if ( conshdlrdata->sdpconshdlrdata->tightenmatrices )
6017 if ( noldchgcoefs != *nchgcoefs )
6019 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Tightened %d SDP coefficient matrices.\n", *nchgcoefs - noldchgcoefs);
6020 *result = SCIP_SUCCESS;
6025 if ( conshdlrdata->sdpconshdlrdata->tightenbounds )
6027 SCIP_CALL(
tightenBounds(scip, conss, nconss, conshdlrdata->sdpconshdlrdata->tightenboundscont, nchgbds, &infeasible) );
6030 *result = SCIP_CUTOFF;
6034 if ( noldchgbds != *nchgbds )
6036 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Tightened %d bounds using SDP constraints.\n", *nchgbds - noldchgbds);
6037 *result = SCIP_SUCCESS;
6047 if ( SCIPgetSubscipDepth(scip) == 0 && ! conshdlrdata->sdpconshdlrdata->triedlinearconss )
6050 SCIP_Bool solvesdps;
6052 SCIP_CALL( SCIPgetIntParam(scip,
"misc/solvesdps", &solvesdpsparam) );
6054 if ( solvesdpsparam == 1 )
6059 conshdlrdata->sdpconshdlrdata->triedlinearconss = TRUE;
6060 if ( conshdlrdata->sdpconshdlrdata->diaggezerocuts )
6062 noldaddconss = *naddconss;
6063 noldchgbds = *nchgbds;
6064 SCIP_CALL(
diagGEzero(scip, conshdlr, conss, nconss, solvesdps, naddconss, nchgbds, &infeasible) );
6065 SCIPdebugMsg(scip,
"Diagonal entries: added %d constraints and changed %d bounds.\n", *naddconss - noldaddconss, *nchgbds - noldchgbds);
6069 *result = SCIP_CUTOFF;
6073 if ( noldaddconss != *naddconss || noldchgbds != *nchgbds )
6075 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Added %d constraints for SDP diagonals to be nonnegative and changed %d bounds.\n", *naddconss - noldaddconss, *nchgbds - noldchgbds);
6076 *result = SCIP_SUCCESS;
6080 if ( *result != SCIP_CUTOFF && conshdlrdata->sdpconshdlrdata->diagzeroimplcuts )
6082 noldaddconss = *naddconss;
6083 SCIP_CALL(
diagZeroImpl(scip, conss, nconss, naddconss) );
6084 SCIPdebugMsg(scip,
"Added %d constraints for implication from 0 diagonal.\n", *naddconss - noldaddconss);
6085 if ( noldaddconss != *naddconss )
6087 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Added %d constraints for implications on SDP diagonals.\n", *naddconss - noldaddconss);
6088 *result = SCIP_SUCCESS;
6092 if ( *result != SCIP_CUTOFF && conshdlrdata->sdpconshdlrdata->twominorlinconss )
6094 noldaddconss = *naddconss;
6096 SCIPdebugMsg(scip,
"Added %d linear constraints for 2 by 2 minors.\n", *naddconss - noldaddconss);
6097 if ( noldaddconss != *naddconss )
6099 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Added %d linear constraints based on 2 x 2 SDP-minors.\n", *naddconss - noldaddconss);
6100 *result = SCIP_SUCCESS;
6104 if ( *result != SCIP_CUTOFF && conshdlrdata->sdpconshdlrdata->twominorprodconss )
6106 noldaddconss = *naddconss;
6108 SCIPdebugMsg(scip,
"Added %d linear constraints for products of 2 by 2 minors.\n", *naddconss - noldaddconss);
6109 if ( noldaddconss != *naddconss )
6111 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Added %d linear constraints based on products of 2 x 2 SDP-minors.\n", *naddconss - noldaddconss);
6112 *result = SCIP_SUCCESS;
6117 if ( *result != SCIP_CUTOFF && conshdlrdata->sdpconshdlrdata->addsocrelax )
6119 noldaddconss = *naddconss;
6121 SCIPdebugMsg(scip,
"Added %d SOC constraints for 2 by 2 minors.\n", *naddconss - noldaddconss);
6122 if ( noldaddconss != *naddconss )
6123 *result = SCIP_SUCCESS;
6127 if ( SCIPgetSubscipDepth(scip) == 0 && *result != SCIP_CUTOFF && conshdlrdata->sdpconshdlrdata->quadconsrank1 )
6129 noldaddconss = *naddconss;
6131 SCIPdebugMsg(scip,
"Added %d quadratic constraints for rank 1 constraints.\n", *naddconss - noldaddconss);
6132 if ( noldaddconss != *naddconss )
6133 *result = SCIP_SUCCESS;
6136 conshdlrdata->sdpconshdlrdata->upgradequadconss = FALSE;
6141 if ( SCIPisPresolveFinished(scip) && conshdlrdata->sdpconshdlrdata->twominorvarbounds && ! conshdlrdata->sdpconshdlrdata->triedvarbounds )
6143 if ( SCIPgetSubscipDepth(scip) == 0 && *result != SCIP_CUTOFF )
6147 SCIP_Bool solvesdps;
6149 SCIP_CALL( SCIPgetIntParam(scip,
"misc/solvesdps", &solvesdpsparam) );
6151 if ( solvesdpsparam == 1 )
6156 noldaddconss = *naddconss;
6158 SCIPdebugMsg(scip,
"Added %d linear constraints for variables bounds from 2 by 2 minors.\n", *naddconss - noldaddconss);
6159 if ( noldaddconss != *naddconss )
6161 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
"Added %d linear constraints based on variable bounds from 2 x 2 SDP-minors.\n", *naddconss - noldaddconss);
6162 *result = SCIP_SUCCESS;
6164 conshdlrdata->sdpconshdlrdata->triedvarbounds = TRUE;
6175 SCIP_CONSDATA* sourcedata;
6176 SCIP_CONSDATA* targetdata;
6177 SCIP_CONSHDLRDATA* conshdlrdata;
6182 char transname[SCIP_MAXSTRLEN];
6184 sourcedata = SCIPconsGetData(sourcecons);
6185 assert( sourcedata != NULL );
6187 SCIPdebugMsg(scip,
"Transforming constraint <%s>\n", SCIPconsGetName(sourcecons));
6189 conshdlrdata = SCIPconshdlrGetData(conshdlr);
6192 SCIPdebugMsg(scip,
"Setting number of threads to %d via OpenMP in Openblas.\n", conshdlrdata->sdpconshdlrdata->nthreads);
6193 omp_set_num_threads(conshdlrdata->sdpconshdlrdata->nthreads);
6196 SCIP_CALL( SCIPallocBlockMemory(scip, &targetdata) );
6199 targetdata->nvars = sourcedata->nvars;
6200 targetdata->nnonz = sourcedata->nnonz;
6201 targetdata->blocksize = sourcedata->blocksize;
6202 targetdata->matrixvar = NULL;
6203 targetdata->matrixval = NULL;
6204 targetdata->matrixconst = NULL;
6205 targetdata->nsingle = 0;
6206 targetdata->tracebound = -2.0;
6207 targetdata->allmatricespsd = sourcedata->allmatricespsd;
6208 targetdata->initallmatricespsd = sourcedata->initallmatricespsd;
6210 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->nvarnonz), sourcedata->nvarnonz, sourcedata->nvars) );
6213 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->col), sourcedata->nvars) );
6214 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->row), sourcedata->nvars) );
6215 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->val), sourcedata->nvars) );
6217 for (i = 0; i < sourcedata->nvars; i++)
6219 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->col[i]), sourcedata->col[i], sourcedata->nvarnonz[i]) );
6220 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->row[i]), sourcedata->row[i], sourcedata->nvarnonz[i]) );
6221 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->val[i]), sourcedata->val[i], sourcedata->nvarnonz[i]) );
6223 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->vars), sourcedata->nvars) );
6224 if ( sourcedata->locks != NULL )
6226 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->locks), sourcedata->locks, sourcedata->nvars) );
6229 targetdata->locks = NULL;
6232 for (i = 0; i < sourcedata->nvars; i++)
6234 targetdata->vars[i] = SCIPvarGetTransVar(sourcedata->vars[i]);
6235 SCIP_CALL( SCIPcaptureVar(scip, targetdata->vars[i]) );
6239 targetdata->constnnonz = sourcedata->constnnonz;
6241 if ( sourcedata->constnnonz > 0 )
6243 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constcol), sourcedata->constcol, sourcedata->constnnonz));
6244 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constrow), sourcedata->constrow, sourcedata->constnnonz));
6245 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constval), sourcedata->constval, sourcedata->constnnonz));
6249 targetdata->constcol = NULL;
6250 targetdata->constrow = NULL;
6251 targetdata->constval = NULL;
6255 targetdata->maxrhsentry = sourcedata->maxrhsentry;
6258 targetdata->rankone = sourcedata->rankone;
6261 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->maxevsubmat), sourcedata->maxevsubmat, 2) );
6264 targetdata->addedquadcons = sourcedata->addedquadcons;
6268 snprintfreturn = SCIPsnprintf(transname, SCIP_MAXSTRLEN,
"t_%s", SCIPconsGetName(sourcecons));
6269 assert( snprintfreturn < SCIP_MAXSTRLEN );
6271 (void) SCIPsnprintf(transname, SCIP_MAXSTRLEN,
"t_%s", SCIPconsGetName(sourcecons));
6275 SCIP_CALL( SCIPcreateCons(scip, targetcons, transname, conshdlr, targetdata,
6276 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
6277 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
6278 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
6279 SCIPconsIsStickingAtNode(sourcecons)) );
6282 if ( conshdlrdata->sdpconshdlrdata->usedimacsfeastol )
6285 SCIP_Real sum = 0.0;
6289 nvars = SCIPgetNOrigVars(scip);
6290 vars = SCIPgetOrigVars(scip);
6291 for ( v = 0; v < nvars; v++ )
6292 sum += REALABS( SCIPvarGetObj(vars[v]) );
6293 conshdlrdata->dimacsfeastol = 1e-5 * (1 + sum);
6303 SCIP_CONS* violcons;
6304 SCIP_CONSDATA* consdata;
6305 SCIP_CONSHDLRDATA* conshdlrdata;
6308 SCIP_SOL* bestrank1approx;
6309 SCIP_Real* fullmatrix;
6310 SCIP_Real* eigenvalues;
6311 SCIP_Real* eigenvectors;
6312 SCIP_Real* scaledeigenvectors;
6314 SCIP_Real* matrixAj;
6315 SCIP_Real* linmatrix;
6316 SCIP_Real* rhsmatrix;
6319 SCIP_Real* colmatrix;
6320 SCIP_Bool rank1result;
6328 #ifdef PRINTMATRICES 6342 int* indviolrank1conss;
6343 SCIP_VAR** rank1consvars;
6345 assert( scip != NULL );
6346 assert( result != NULL );
6347 assert( conss != NULL );
6349 conshdlrdata = SCIPconshdlrGetData(conshdlr);
6350 assert( conshdlrdata != NULL );
6352 *result = SCIP_FEASIBLE;
6354 #ifdef PRINTMATRICES 6355 SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
6359 for (i = 0; i < nconss; ++i)
6362 #ifdef PRINTMATRICES 6363 SCIPinfoMessage(scip, NULL,
"Solution is %d for constraint %s.\n", *result, SCIPconsGetName(conss[i]) );
6365 if ( *result == SCIP_INFEASIBLE )
6370 if ( ! conshdlrdata->sdpconshdlrdata->rank1approxheur )
6376 if ( SCIPgetSubscipDepth(scip) > 0 )
6379 SCIP_CALL( SCIPallocBufferArray(scip, &indviolrank1conss, nconss) );
6382 SCIPdebugMsg(scip,
"Check rank-1 constraints if there are any.\n");
6383 for (i = 0; i < nconss; ++i)
6385 consdata = SCIPconsGetData(conss[i]);
6386 assert( consdata != NULL );
6388 if ( consdata->rankone )
6390 SCIP_CALL(
isMatrixRankOne(scip, conshdlrdata, conss[i], sol, &rank1result) );
6391 if ( ! rank1result )
6394 indviolrank1conss[nviolrank1] = i;
6403 if ( nviolrank1 == 0 )
6405 SCIPdebugMsg(scip,
"Found no violated rank-1 constraints.\n");
6406 SCIPfreeBufferArray(scip, &indviolrank1conss);
6410 SCIPdebugMsg(scip,
"Found %d violated rank-1 constraints, thus apply rank-1 approximation heuristic!\n", nviolrank1);
6413 nvars = SCIPgetNVars(scip);
6414 SCIP_CALL( SCIPallocBufferArray(scip, &rank1considx, nvars) );
6415 SCIP_CALL( SCIPallocBufferArray(scip, &rank1consvars, nvars) );
6417 for (j = 0; j < nvars; ++j)
6418 rank1considx[j] = -1;
6420 for (c = 0; c < nviolrank1; ++c)
6422 assert( conss[indviolrank1conss[c]] != NULL );
6425 consdata = SCIPconsGetData(conss[indviolrank1conss[c]]);
6426 assert( consdata != NULL );
6428 nsdpvars = consdata->nvars;
6429 linrows += consdata->blocksize * (consdata->blocksize + 1) / 2;
6431 for (i = 0; i < nsdpvars; ++i)
6433 var = consdata->vars[i];
6434 idx = SCIPvarGetProbindex(var);
6435 assert( 0 <= idx && idx < nvars );
6436 if ( rank1considx[idx] < 0 )
6438 rank1consvars[nrank1vars] = var;
6439 rank1considx[idx] = nrank1vars++;
6445 SCIP_CALL( SCIPallocClearBufferArray(scip, &linmatrix, linrows * nrank1vars) );
6446 SCIP_CALL( SCIPallocClearBufferArray(scip, &rhsmatrix, MAX(linrows,nrank1vars)) );
6448 for (i = 0; i < nviolrank1; ++i)
6451 violcons = conss[indviolrank1conss[i]];
6452 consdata = SCIPconsGetData(violcons);
6454 assert( consdata != NULL );
6456 blocksize = consdata->blocksize;
6458 SCIPdebugMsg(scip,
"\n Start with violated rank-1 constraint %s, is %d out of %d violated rank-1 constraints.\n\n", SCIPconsGetName(violcons), i + 1, nviolrank1);
6461 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize ) );
6462 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvalues, blocksize) );
6463 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvectors, blocksize * blocksize) );
6464 SCIP_CALL( SCIPallocBufferArray(scip, &matrixC, blocksize * blocksize) );
6465 SCIP_CALL( SCIPallocBufferArray(scip, &matrixAj, blocksize * blocksize) );
6466 SCIP_CALL( SCIPallocBufferArray(scip, &linvars, consdata->nvars) );
6467 SCIP_CALL( SCIPallocBufferArray(scip, &linvals, consdata->nvars) );
6472 #ifdef PRINTMATRICES 6474 printf(
"Full SDP-constraint matrix Z: \n");
6475 for (j = 0; j < blocksize; ++j)
6477 for (k = 0; k < blocksize; ++k)
6478 printf(
"%.5f ", fullmatrix[j*blocksize + k]);
6483 printf(
"Full SDP-constraint matrix Z in row-first format: \n");
6484 for (j = 0; j < blocksize * blocksize; ++j)
6485 printf(
"%.5f ", fullmatrix[j]);
6492 #ifdef PRINTMATRICES 6494 printf(
"Eigenvectors of Z: \n");
6495 for (j = 0; j < blocksize; ++j)
6497 for (k = 0; k < blocksize; ++k)
6498 printf(
"%.5f ", eigenvectors[k*blocksize + j]);
6503 printf(
"Eigenvectors of Z in column-first format: \n");
6504 for (j = 0; j < blocksize * blocksize; ++j)
6505 printf(
"%.5f ", eigenvectors[j]);
6508 printf(
"Eigenvalues of Z: \n");
6509 for (j = 0; j < blocksize; ++j)
6510 printf(
"%.5f ", eigenvalues[j]);
6515 SCIP_CALL( SCIPduplicateBufferArray(scip, &scaledeigenvectors, eigenvectors, blocksize*blocksize) );
6519 for (j = 0; j < blocksize-1; ++j)
6521 assert( ! SCIPisFeasNegative(scip, eigenvalues[j]) );
6522 eigenvalues[j] = 0.0;
6528 SCIP_CALL(
scaleRowsMatrix(blocksize, scaledeigenvectors, eigenvalues) );
6530 #ifdef PRINTMATRICES 6531 printf(
"Scaled eigenvectors of Z (only keep largest eigenvalue and corresponding eigenvector) : \n");
6532 for (j = 0; j < blocksize; ++j)
6534 for (k = 0; k < blocksize; ++k)
6536 printf(
"%.5f ", scaledeigenvectors[j*blocksize + k]);
6542 printf(
"Scaled eigenvectors of Z in row-first format: \n");
6543 for (j = 0; j < blocksize * blocksize; ++j)
6544 printf(
"%.5f ", scaledeigenvectors[j]);
6553 TRUE, fullmatrix) );
6555 #ifdef PRINTMATRICES 6556 printf(
"Best rank-1 approximation of Z: \n");
6557 for (j = 0; j < blocksize; ++j)
6559 for (k = 0; k < blocksize; ++k)
6560 printf(
"%.5f ", fullmatrix[j*blocksize + k]);
6565 printf(
"Best rank-1 approximation of Z in row-first format: \n");
6566 for (j = 0; j < blocksize * blocksize; ++j)
6567 printf(
"%.5f ", fullmatrix[j]);
6576 #ifdef PRINTMATRICES 6577 printf(
"Constant matrix A_0 of SDP-constraint: \n");
6578 for (j = 0; j < blocksize; ++j)
6580 for (k = 0; k < blocksize; ++k)
6581 printf(
"%.5f ", matrixC[j*blocksize + k]);
6586 printf(
"Constant matrix A_0 of SDP-constraint in row-first format: \n");
6587 for (j = 0; j < blocksize * blocksize; ++j)
6588 printf(
"%.5f ", matrixC[j]);
6592 for (j = 0; j < blocksize; ++j)
6594 for (k = 0; k <= j; ++k)
6596 for (l = 0; l < consdata->nvars; ++l)
6601 #ifdef PRINTMATRICES 6602 printf(
"Coefficient matrix A_%d of SDP-constraint: \n", l+1);
6603 for (r = 0; r < blocksize; ++r)
6605 for (s = 0; s < blocksize; ++s)
6606 printf(
"%.5f ", matrixAj[r*blocksize + s]);
6611 printf(
"Constant matrix A_0 of SDP-constraint in row-first format: \n");
6612 for (r = 0; r < blocksize * blocksize; ++r)
6613 printf(
"%.5f ", matrixAj[r]);
6617 idx = SCIPvarGetProbindex(consdata->vars[l]);
6618 idx = rank1considx[idx];
6619 assert( 0 <= idx && idx < nrank1vars );
6620 assert( lincnt <= linrows );
6621 linmatrix[lincnt * nrank1vars + idx] = matrixAj[j * blocksize + k];
6623 rhsmatrix[lincnt] = matrixC[j * blocksize + k] + fullmatrix[j * blocksize + k];
6629 SCIPfreeBufferArray(scip, &linvals);
6630 SCIPfreeBufferArray(scip, &linvars);
6631 SCIPfreeBufferArray(scip, &matrixAj);
6632 SCIPfreeBufferArray(scip, &matrixC);
6633 SCIPfreeBufferArray(scip, &scaledeigenvectors);
6634 SCIPfreeBufferArray(scip, &eigenvectors);
6635 SCIPfreeBufferArray(scip, &eigenvalues);
6636 SCIPfreeBufferArray(scip, &fullmatrix);
6639 assert( lincnt == linrows );
6641 #ifdef PRINTMATRICES 6642 printf(
"Matrix for linear equation system, in row-first format:\n");
6643 for (j = 0; j < linrows; ++j)
6645 for (k = 0; k < nrank1vars; ++k)
6647 printf(
"%.5f ", linmatrix[j * nrank1vars + k]);
6653 printf(
"Matrix for linear equation system in row-first format: \n");
6654 for (r = 0; r < linrows * nrank1vars; ++r)
6655 printf(
"%.5f ", linmatrix[r]);
6658 printf(
"Right-hand for linear equation system:\n");
6659 for (j = 0; j < nrank1vars; ++j)
6661 printf(
"%.5f ", rhsmatrix[j]);
6667 SCIP_CALL( SCIPallocBufferArray(scip, &lssolu, nrank1vars) );
6670 SCIP_CALL( SCIPallocBufferArray(scip, &colmatrix, linrows * nrank1vars ) );
6674 #ifdef PRINTMATRICES 6675 printf(
"Matrix for linear equation system, in col-first format:\n");
6676 for (j = 0; j < linrows; ++j)
6678 for (l = 0; l < nrank1vars; ++l)
6680 printf(
"%.5f ", colmatrix[l * linrows + j]);
6686 printf(
"Matrix for linear equation system in col-first format: \n");
6687 for (r = 0; r < linrows * nrank1vars; ++r)
6688 printf(
"%.5f ", colmatrix[r]);
6692 SCIP_CALL(
SCIPlapackLinearSolve( SCIPbuffer(scip), linrows, nrank1vars, colmatrix, rhsmatrix, lssolu) );
6695 SCIP_CALL( SCIPcreateSolCopy(scip, &bestrank1approx, sol) );
6698 for (i = 0; i < nrank1vars; ++i)
6700 var = rank1consvars[i];
6701 SCIP_CALL( SCIPsetSolVal(scip, bestrank1approx, var, lssolu[i]) );
6704 SCIP_CALL( SCIPtrySolFree(scip, &bestrank1approx, FALSE, TRUE, TRUE, TRUE, TRUE, &stored) );
6706 SCIPdebugMsg(scip,
"Best Rank-1 Approximation Heuristic found feasible primal solution\n");
6708 SCIPdebugMsg(scip,
"Primal solution found by Best Rank-1 Approximation Heuristic is not feasible!\n");
6710 SCIPfreeBufferArray(scip, &colmatrix);
6711 SCIPfreeBufferArray(scip, &lssolu);
6712 SCIPfreeBufferArray(scip, &rhsmatrix);
6713 SCIPfreeBufferArray(scip, &linmatrix);
6714 SCIPfreeBufferArray(scip, &rank1consvars);
6715 SCIPfreeBufferArray(scip, &rank1considx);
6716 SCIPfreeBufferArray(scip, &indviolrank1conss);
6728 SCIP_CONSHDLRDATA* conshdlrdata;
6731 conshdlrdata = SCIPconshdlrGetData(conshdlr);
6732 assert( conshdlrdata != NULL );
6734 assert( scip != NULL );
6735 assert( result != NULL );
6736 assert( conss != NULL );
6738 *result = SCIP_DIDNOTRUN;
6740 if ( objinfeasible )
6742 SCIPdebugMsg(scip,
"-> pseudo solution is objective infeasible, return.\n");
6746 for (i = 0; i < nconss; ++i)
6750 if (*result == SCIP_INFEASIBLE)
6753 SCIPdebugMsg(scip,
"-> pseudo solution infeasible for SDP-constraint %s, return.\n", SCIPconsGetName(conss[i]));
6758 *result = SCIP_FEASIBLE;
6760 SCIPdebugMsg(scip,
"-> pseudo solution feasible for all SDP-constraints.\n");
6771 SCIP_CONSHDLRDATA* conshdlrdata;
6774 assert( scip != NULL );
6775 assert( conshdlr != NULL );
6776 assert( conss != NULL );
6777 assert( result != NULL );
6779 conshdlrdata = SCIPconshdlrGetData(conshdlr);
6780 assert( conshdlrdata != NULL );
6782 *result = SCIP_FEASIBLE;
6785 if ( solinfeasible )
6789 for (c = 0; c < nconss && *result != SCIP_CUTOFF; ++c)
6791 SCIP_RESULT separesult = SCIP_FEASIBLE;
6793 SCIP_CALL(
separateSol(scip, conshdlr, conss[c], NULL, TRUE, &separesult) );
6794 assert( separesult == SCIP_FEASIBLE || separesult == SCIP_CUTOFF || separesult == SCIP_SEPARATED || separesult == SCIP_CONSADDED );
6796 if ( separesult == SCIP_CUTOFF )
6797 *result = SCIP_CUTOFF;
6798 else if ( separesult == SCIP_CONSADDED )
6799 *result = SCIP_CONSADDED;
6800 else if ( separesult == SCIP_SEPARATED )
6801 *result = SCIP_SEPARATED;
6806 if ( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY || conshdlrdata->relaxsdp == NULL || *result == SCIP_CUTOFF )
6810 if ( conshdlrdata->sdpconshdlrdata->enforcesdp && (*result == SCIP_SEPARATED || *result == SCIP_CONSADDED) )
6819 vars = SCIPgetVars(scip);
6820 nintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
6823 for (v = 0; v < nintvars; ++v)
6828 assert( SCIPvarIsIntegral(var) );
6830 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, var)) );
6831 assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(var)) );
6832 assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(var)) );
6834 if ( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
6839 if ( ! conshdlrdata->sdpconshdlrdata->onlyfixedintssdp || nfixed == nintvars )
6842 SCIP_CALL( SCIPstartProbing(scip) );
6845 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
6850 SCIPdebugMsg(scip,
"Solving relaxation because all integer variable have integral values.\n");
6853 freq = SCIPrelaxGetFreq(conshdlrdata->relaxsdp);
6854 SCIP_CALL( SCIPsetIntParam(scip,
"relaxing/SDP/freq", 1) );
6857 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
6860 SCIP_CALL( SCIPsetIntParam(scip,
"relaxing/SDP/freq", freq) );
6868 SCIPdebugMsg(scip,
"Cut off node in enforcing, because remaining SDP was infeasible.\n");
6869 *result = SCIP_CUTOFF;
6877 SCIP_CALL( SCIPcreateSol(scip, &enfosol, NULL) );
6878 SCIP_CALL( SCIPlinkRelaxSol(scip, enfosol) );
6882 SCIP_CALL( SCIPcheckSol(scip, enfosol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
6889 SCIP_CALL( SCIPaddSol(scip, enfosol, &stored) );
6892 if ( stored && nintvars == nfixed )
6893 *result = SCIP_CUTOFF;
6895 else if ( nfixed < nintvars )
6898 assert( *result != SCIP_CUTOFF );
6900 for (v = 0; v < nintvars; ++v)
6906 assert( SCIPvarIsIntegral(var) );
6909 if ( SCIPvarGetLbLocal(var) + 0.5 < SCIPvarGetUbLocal(var) )
6912 val = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var) + 0.5);
6914 if ( ! SCIPisEQ(scip, val, SCIPvarGetUbLocal(var)) )
6916 SCIP_CALL( SCIPchgVarUbProbing(scip, var, val) );
6919 if ( ! SCIPisEQ(scip, val, SCIPvarGetLbLocal(var)) )
6921 SCIP_CALL( SCIPchgVarLbProbing(scip, var, val) );
6927 SCIP_CALL( SCIPsetIntParam(scip,
"relaxing/SDP/freq", 1) );
6928 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
6929 SCIP_CALL( SCIPsetIntParam(scip,
"relaxing/SDP/freq", freq) );
6937 assert( enfosol != NULL );
6938 SCIP_CALL( SCIPlinkRelaxSol(scip, enfosol) );
6942 SCIP_CALL( SCIPtrySol(scip, enfosol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
6948 SCIP_CALL( SCIPmarkRelaxSolInvalid(scip) );
6949 SCIP_CALL( SCIPfreeSol(scip, &enfosol) );
6955 SCIP_CALL( SCIPendProbing(scip) );
6968 assert( scip != NULL );
6969 assert( conshdlr != NULL );
6970 assert( conss != NULL );
6971 assert( result != NULL );
6973 *result = SCIP_FEASIBLE;
6975 if ( solinfeasible )
6980 for (c = 0; c < nconss && *result != SCIP_CUTOFF; ++c)
6982 SCIP_RESULT separesult = SCIP_FEASIBLE;
6984 SCIP_CALL(
separateSol(scip, conshdlr, conss[c], sol, TRUE, &separesult) );
6985 assert( separesult == SCIP_FEASIBLE || separesult == SCIP_CUTOFF || separesult == SCIP_SEPARATED || separesult == SCIP_CONSADDED );
6987 if ( separesult == SCIP_CUTOFF )
6988 *result = SCIP_CUTOFF;
6989 else if ( separesult == SCIP_CONSADDED )
6990 *result = SCIP_CONSADDED;
6991 else if ( separesult == SCIP_SEPARATED )
6992 *result = SCIP_SEPARATED;
7004 assert( result != NULL );
7005 *result = SCIP_DIDNOTFIND;
7007 for (i = 0; i < nusefulconss && *result != SCIP_CUTOFF; ++i)
7009 SCIP_RESULT separesult = SCIP_DIDNOTFIND;
7011 SCIP_CALL(
separateSol(scip, conshdlr, conss[i], sol, FALSE, &separesult) );
7012 assert( separesult == SCIP_DIDNOTFIND || separesult == SCIP_CUTOFF || separesult == SCIP_SEPARATED || separesult == SCIP_CONSADDED );
7014 if ( separesult == SCIP_CUTOFF )
7015 *result = SCIP_CUTOFF;
7016 else if ( separesult == SCIP_CONSADDED )
7017 *result = SCIP_CONSADDED;
7018 else if ( separesult == SCIP_SEPARATED )
7019 *result = SCIP_SEPARATED;
7031 assert( result != NULL );
7032 *result = SCIP_DIDNOTFIND;
7034 for (i = 0; i < nusefulconss && *result != SCIP_CUTOFF; ++i)
7036 SCIP_RESULT separesult = SCIP_DIDNOTFIND;
7038 SCIP_CALL(
separateSol(scip, conshdlr, conss[i], NULL, FALSE, &separesult) );
7040 assert( separesult == SCIP_DIDNOTFIND || separesult == SCIP_CUTOFF || separesult == SCIP_SEPARATED || separesult == SCIP_CONSADDED );
7042 if ( separesult == SCIP_CUTOFF )
7043 *result = SCIP_CUTOFF;
7044 else if ( separesult == SCIP_CONSADDED )
7045 *result = SCIP_CONSADDED;
7046 else if ( separesult == SCIP_SEPARATED )
7047 *result = SCIP_SEPARATED;
7059 assert( cons != NULL );
7060 assert( consdata != NULL );
7062 SCIPdebugMsg(scip,
"deleting SDP constraint <%s>.\n", SCIPconsGetName(cons));
7065 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->maxevsubmat, 2);
7067 for (i = 0; i < (*consdata)->nvars; i++)
7069 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->val[i], (*consdata)->nvarnonz[i]);
7070 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->row[i], (*consdata)->nvarnonz[i]);
7071 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->col[i], (*consdata)->nvarnonz[i]);
7075 for (i = 0; i < (*consdata)->nvars; i++)
7077 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[i])) );
7080 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->nvars);
7081 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->locks, (*consdata)->nvars);
7082 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constval, (*consdata)->constnnonz);
7083 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constrow, (*consdata)->constnnonz);
7084 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constcol, (*consdata)->constnnonz);
7085 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->val, (*consdata)->nvars);
7086 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->row, (*consdata)->nvars);
7087 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->col, (*consdata)->nvars);
7088 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->nvarnonz, (*consdata)->nvars);
7089 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->matrixval, (*consdata)->blocksize * ((*consdata)->blocksize + 1) / 2);
7090 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->matrixvar, (*consdata)->blocksize * ((*consdata)->blocksize + 1) / 2);
7091 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->matrixconst, (*consdata)->blocksize * ((*consdata)->blocksize + 1) / 2);
7092 SCIPfreeBlockMemory(scip, consdata);
7101 SCIP_CONSHDLRDATA* conshdlrdata;
7103 SCIPdebugMsg(scip,
"Freeing constraint handler <%s>.\n", SCIPconshdlrGetName(conshdlr));
7105 conshdlrdata = SCIPconshdlrGetData(conshdlr);
7106 assert( conshdlrdata != NULL );
7108 if ( conshdlrdata->randnumgen != NULL )
7110 SCIPfreeRandom(scip, &conshdlrdata->randnumgen);
7113 SCIPfreeMemory(scip, &conshdlrdata);
7114 SCIPconshdlrSetData(conshdlr, NULL);
7123 assert(scip != NULL);
7124 assert(conshdlr != NULL);
7125 assert(strcmp(SCIPconshdlrGetName(conshdlr),
CONSHDLR_NAME) == 0);
7138 assert(scip != NULL);
7139 assert(conshdlr != NULL);
7153 char copyname[SCIP_MAXSTRLEN];
7154 SCIP_CONSDATA* sourcedata;
7156 SCIP_VAR** targetvars;
7163 assert( scip != NULL );
7164 assert( sourcescip != NULL );
7165 assert( sourcecons != NULL );
7166 assert( valid != NULL );
7168 SCIPdebugMsg(scip,
"Copying SDP constraint <%s>\n", SCIPconsGetName(sourcecons));
7175 if ( SCIPgetStage(sourcescip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(sourcescip) <= SCIP_STAGE_EXITPRESOLVE )
7180 sourcedata = SCIPconsGetData(sourcecons);
7181 assert( sourcedata != NULL );
7182 assert( sourcedata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)),
CONSHDLR_NAME) == 0 );
7183 assert( ! sourcedata->rankone || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)),
CONSHDLRRANK1_NAME) == 0 );
7185 SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, sourcedata->nvars) );
7188 for (i = 0; i < sourcedata->nvars; i++)
7190 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->vars[i], &var, varmap, consmap, global, &success) );
7192 targetvars[i] = var;
7199 snprintfreturn = SCIPsnprintf(copyname, SCIP_MAXSTRLEN,
"c_%s", name == NULL ? SCIPconsGetName(sourcecons) : name);
7200 assert( snprintfreturn < SCIP_MAXSTRLEN );
7202 (void) SCIPsnprintf(copyname, SCIP_MAXSTRLEN,
"c_%s", name == NULL ? SCIPconsGetName(sourcecons) : name);
7206 if ( ! sourcedata->rankone )
7208 SCIP_CALL(
SCIPcreateConsSdp(scip, cons, copyname, sourcedata->nvars, sourcedata->nnonz, sourcedata->blocksize, sourcedata->nvarnonz,
7209 sourcedata->col, sourcedata->row, sourcedata->val, targetvars, sourcedata->constnnonz,
7210 sourcedata->constcol, sourcedata->constrow, sourcedata->constval, FALSE) );
7214 SCIP_CALL(
SCIPcreateConsSdpRank1(scip, cons, copyname, sourcedata->nvars, sourcedata->nnonz, sourcedata->blocksize, sourcedata->nvarnonz,
7215 sourcedata->col, sourcedata->row, sourcedata->val, targetvars, sourcedata->constnnonz,
7216 sourcedata->constcol, sourcedata->constrow, sourcedata->constval, FALSE) );
7220 if ( sourcedata->locks != NULL )
7222 SCIP_CONSDATA* targetdata;
7224 targetdata = SCIPconsGetData(*cons);
7225 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->locks), sourcedata->locks, sourcedata->nvars) );
7226 targetdata->allmatricespsd = sourcedata->allmatricespsd;
7227 targetdata->initallmatricespsd = sourcedata->initallmatricespsd;
7230 SCIPfreeBufferArray(scip, &targetvars);
7239 #ifdef PRINT_HUMAN_READABLE 7240 SCIP_CONSDATA* consdata;
7241 SCIP_Real* fullmatrix;
7246 assert( scip != NULL );
7247 assert( cons != NULL );
7249 consdata = SCIPconsGetData(cons);
7250 assert( consdata != NULL );
7252 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, consdata->blocksize * consdata->blocksize) );
7255 SCIPinfoMessage(scip, file,
"rank-1? %d\n", consdata->rankone);
7258 for (v = 0; v < consdata->nvars; v++)
7263 for (i = 0; i < consdata->blocksize; i++)
7265 for (j = 0; j < consdata->blocksize; j++)
7266 fullmatrix[i * consdata->blocksize + j] = 0.0;
7270 for (i = 0; i < consdata->nvarnonz[v]; i++)
7272 fullmatrix[consdata->row[v][i] * consdata->blocksize + consdata->col[v][i]] = consdata->val[v][i];
7273 fullmatrix[consdata->col[v][i] * consdata->blocksize + consdata->row[v][i]] = consdata->val[v][i];
7277 SCIPinfoMessage(scip, file,
"+\n");
7278 for (i = 0; i < consdata->blocksize; i++)
7280 SCIPinfoMessage(scip, file,
"( ");
7281 for (j = 0; j < consdata->blocksize; j++)
7282 SCIPinfoMessage(scip, file,
"%g ", fullmatrix[i * consdata->blocksize + j]);
7283 SCIPinfoMessage(scip, file,
")\n");
7285 SCIPinfoMessage(scip, file,
"* %s\n", SCIPvarGetName(consdata->vars[v]));
7293 for (i = 0; i < consdata->blocksize; i++)
7295 for (j = 0; j < consdata->blocksize; j++)
7296 fullmatrix[i * consdata->blocksize + j] = 0.0;
7300 for (i = 0; i < consdata->constnnonz; i++)
7302 fullmatrix[consdata->constrow[i] * consdata->blocksize + consdata->constcol[i]] = consdata->constval[i];
7303 fullmatrix[consdata->constcol[i] * consdata->blocksize + consdata->constrow[i]] = consdata->constval[i];
7307 SCIPinfoMessage(scip, file,
"-\n");
7308 for (i = 0; i < consdata->blocksize; i++)
7310 SCIPinfoMessage(scip, file,
"( ");
7311 for (j = 0; j < consdata->blocksize; j++)
7312 SCIPinfoMessage(scip, file,
"%g ", fullmatrix[i * consdata->blocksize + j]);
7313 SCIPinfoMessage(scip, file,
")\n");
7315 SCIPinfoMessage(scip, file,
">= 0\n");
7318 SCIPinfoMessage(scip, file,
"rank-1? %d\n", consdata->rankone);
7320 SCIPfreeBufferArray(scip, &fullmatrix);
7324 SCIP_CONSDATA* consdata;
7328 assert( scip != NULL );
7329 assert( cons != NULL );
7331 consdata = SCIPconsGetData(cons);
7334 SCIPinfoMessage(scip, file,
"%d\n", consdata->blocksize);
7337 SCIPinfoMessage(scip, file,
" rank-1? %u\n", consdata->rankone);
7340 if ( consdata->constnnonz > 0 )
7342 SCIPinfoMessage(scip, file,
" A_0: ");
7344 for (i = 0; i < consdata->constnnonz; i++)
7346 if ( i < consdata->constnnonz - 1 )
7347 SCIPinfoMessage(scip, file,
"(%d,%d):%.15g, ", consdata->constrow[i], consdata->constcol[i], consdata->constval[i]);
7349 SCIPinfoMessage(scip, file,
"(%d,%d):%.15g", consdata->constrow[i], consdata->constcol[i], consdata->constval[i]);
7351 SCIPinfoMessage(scip, file,
"\n");
7355 for (v = 0; v < consdata->nvars; v++)
7357 SCIPinfoMessage(scip, file,
" <%s>: ", SCIPvarGetName(consdata->vars[v]));
7358 for (i = 0; i < consdata->nvarnonz[v]; i++)
7360 if ( i < consdata->nvarnonz[v] - 1 || v < consdata->nvars - 1 )
7361 SCIPinfoMessage(scip, file,
"(%d,%d):%.15g, ", consdata->row[v][i], consdata->col[v][i], consdata->val[v][i]);
7363 SCIPinfoMessage(scip, file,
"(%d,%d):%.15g", consdata->row[v][i], consdata->col[v][i], consdata->val[v][i]);
7366 if (v < consdata->nvars - 1)
7368 SCIPinfoMessage(scip, file,
"\n");
7380 SCIP_Bool parsesuccess;
7381 SCIP_CONSDATA* consdata = NULL;
7389 assert( scip != NULL );
7390 assert( str != NULL );
7392 nvars = SCIPgetNVars(scip);
7394 assert( success != NULL );
7398 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
7399 consdata->nvars = 0;
7400 consdata->nnonz = 0;
7401 consdata->constnnonz = 0;
7402 consdata->rankone = 0;
7403 consdata->addedquadcons = FALSE;
7404 consdata->locks = NULL;
7405 consdata->matrixvar = NULL;
7406 consdata->matrixval = NULL;
7407 consdata->matrixconst = NULL;
7408 consdata->nsingle = 0;
7409 consdata->tracebound = -2.0;
7410 consdata->allmatricespsd = FALSE;
7411 consdata->initallmatricespsd = FALSE;
7413 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->nvarnonz, nvars) );
7414 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col, nvars) );
7415 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row, nvars) );
7416 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val, nvars) );
7417 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars));
7419 consdata->constcol = NULL;
7420 consdata->constrow = NULL;
7421 consdata->constval = NULL;
7424 parsesuccess = SCIPstrToIntValue(str, &(consdata->blocksize), &pos);
7425 *success = *success && parsesuccess;
7428 while ( isspace((
unsigned char)*pos) )
7432 if ( pos[0] ==
'r' && pos[1] ==
'a' && pos[2] ==
'n' && pos[3] ==
'k' && pos[4] ==
'-' && pos[5] ==
'1' && pos[6] ==
'?' )
7435 parsesuccess = SCIPstrToIntValue(pos, &rankoneint, &pos);
7436 consdata->rankone = (SCIP_Bool) rankoneint;
7437 *success = *success && parsesuccess;
7441 while( isspace((
unsigned char)*pos) )
7445 if ( pos[0] ==
'A' && pos[1] ==
'_' && pos[2] ==
'0' )
7449 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constcol,
PARSE_STARTSIZE) );
7450 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constrow,
PARSE_STARTSIZE) );
7451 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constval,
PARSE_STARTSIZE) );
7456 while (pos[0] ==
'(')
7461 if ( consdata->constnnonz == currentsize )
7463 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constcol, currentsize,
PARSE_SIZEFACTOR * currentsize) );
7464 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constrow, currentsize,
PARSE_SIZEFACTOR * currentsize) );
7465 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constval, currentsize,
PARSE_SIZEFACTOR * currentsize) );
7469 parsesuccess = SCIPstrToIntValue(pos, &(consdata->constrow[consdata->constnnonz]), &pos);
7470 *success = *success && parsesuccess;
7471 assert( consdata->constrow[consdata->constnnonz] < consdata->blocksize );
7473 parsesuccess = SCIPstrToIntValue(pos, &(consdata->constcol[consdata->constnnonz]), &pos);
7474 *success = *success && parsesuccess;
7475 assert( consdata->constcol[consdata->constnnonz] < consdata->blocksize );
7477 parsesuccess = SCIPstrToRealValue(pos, &(consdata->constval[consdata->constnnonz]), &pos);
7478 *success = *success && parsesuccess;
7482 if ( consdata->constcol[consdata->constnnonz] > consdata->constrow[consdata->constnnonz] )
7484 i = consdata->constcol[consdata->constnnonz];
7485 consdata->constcol[consdata->constnnonz] = consdata->constrow[consdata->constnnonz];
7486 consdata->constrow[consdata->constnnonz] = i;
7489 consdata->constnnonz++;
7492 while( isspace((
unsigned char)*pos) )
7497 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constcol, currentsize, consdata->constnnonz) );
7498 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constrow, currentsize, consdata->constnnonz) );
7499 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constval, currentsize, consdata->constnnonz) );
7503 while( isspace((
unsigned char)*pos) )
7509 while ( pos[0] ==
'<' )
7512 SCIP_CALL( SCIPparseVarName(scip, pos, &(consdata->vars[consdata->nvars]), &pos) );
7513 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[consdata->nvars]) );
7515 consdata->nvarnonz[consdata->nvars] = 0;
7516 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->col[consdata->nvars]),
PARSE_STARTSIZE));
7517 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->row[consdata->nvars]),
PARSE_STARTSIZE));
7518 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->val[consdata->nvars]),
PARSE_STARTSIZE));
7525 while (pos[0] ==
'(')
7530 if ( consdata->nvarnonz[consdata->nvars - 1] == currentsize )
7532 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col[consdata->nvars - 1], currentsize,
PARSE_SIZEFACTOR * currentsize) );
7533 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row[consdata->nvars - 1], currentsize,
PARSE_SIZEFACTOR * currentsize) );
7534 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val[consdata->nvars - 1], currentsize,
PARSE_SIZEFACTOR * currentsize) );
7538 parsesuccess = SCIPstrToIntValue(pos, &(consdata->row[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]]), &pos);
7539 *success = *success && parsesuccess;
7540 assert( consdata->row[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] < consdata->blocksize );
7542 parsesuccess = SCIPstrToIntValue(pos, &(consdata->col[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]]), &pos);
7543 *success = *success && parsesuccess;
7544 assert( consdata->col[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] < consdata->blocksize );
7546 parsesuccess = SCIPstrToRealValue(pos, &(consdata->val[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]]), &pos);
7547 *success = *success && parsesuccess;
7552 if ( consdata->col[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] >
7553 consdata->row[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] )
7555 i = consdata->col[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]];
7556 consdata->col[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] =
7557 consdata->row[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]];
7558 consdata->row[consdata->nvars - 1][consdata->nvarnonz[consdata->nvars - 1]] = i;
7561 consdata->nvarnonz[consdata->nvars - 1]++;
7564 while( isspace((
unsigned char)*pos) )
7569 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col[consdata->nvars - 1], currentsize, consdata->nvarnonz[consdata->nvars - 1]) );
7570 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row[consdata->nvars - 1], currentsize, consdata->nvarnonz[consdata->nvars - 1]) );
7571 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val[consdata->nvars - 1], currentsize, consdata->nvarnonz[consdata->nvars - 1]) );
7574 while ( isspace((
unsigned char)*pos) )
7579 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nvarnonz, nvars, consdata->nvars) );
7580 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col, nvars, consdata->nvars) );
7581 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row, nvars, consdata->nvars) );
7582 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val, nvars, consdata->nvars) );
7583 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, nvars, consdata->nvars));
7586 for (v = 0; v < consdata->nvars; v++)
7587 consdata->nnonz += consdata->nvarnonz[v];
7590 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->maxevsubmat, 2) );
7591 consdata->maxevsubmat[0] = -1;
7592 consdata->maxevsubmat[1] = -1;
7595 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, local, modifiable,
7596 dynamic, removable, stickingatnode) );
7601 #ifdef SCIP_MORE_DEBUG 7602 SCIP_CALL( SCIPprintCons(scip, *cons, NULL) );
7612 SCIP_CONSDATA* consdata;
7616 assert( scip != NULL );
7617 assert( cons != NULL );
7618 assert( vars != NULL );
7619 assert( success != NULL );
7620 assert( varssize >= 0 );
7622 consdata = SCIPconsGetData(cons);
7623 assert( consdata != NULL );
7625 nvars = consdata->nvars;
7627 if ( nvars > varssize )
7629 SCIPdebugMsg(scip,
"consGetVarsIndicator called for array of size %d, needed size %d.\n", varssize, nvars);
7634 for (i = 0; i < nvars; i++)
7635 vars[i] = consdata->vars[i];
7646 SCIP_CONSDATA* consdata;
7648 assert( scip != NULL );
7649 assert( cons != NULL );
7650 assert( nvars != NULL );
7651 assert( success != NULL );
7653 consdata = SCIPconsGetData(cons);
7654 assert( consdata != NULL );
7656 *nvars = consdata->nvars;
7667 SCIP_CONSHDLR* conshdlr = NULL;
7668 SCIP_CONSHDLRDATA* conshdlrdata = NULL;
7670 assert( scip != NULL );
7673 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
7674 conshdlrdata->quadconsidx = NULL;
7675 conshdlrdata->quadconsvars = NULL;
7676 conshdlrdata->nquadconsidx = 0;
7677 conshdlrdata->X = NULL;
7678 conshdlrdata->nsdpvars = 0;
7679 conshdlrdata->sdpcons = NULL;
7680 conshdlrdata->triedlinearconss = FALSE;
7681 conshdlrdata->triedvarbounds = FALSE;
7682 conshdlrdata->randnumgen = NULL;
7683 conshdlrdata->relaxsdp = NULL;
7684 conshdlrdata->sdpconshdlrdata = conshdlrdata;
7685 conshdlrdata->dimacsfeastol = SCIP_INVALID;
7690 consEnfolpSdp, consEnfopsSdp, consCheckSdp, consLockSdp, conshdlrdata) );
7692 assert( conshdlr != NULL );
7695 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSdp) );
7696 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSdp) );
7697 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySdp, consCopySdp) );
7698 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr,consInitpreSdp) );
7699 SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitSdp) );
7700 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreSdp) );
7701 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSdp) );
7704 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSdp) );
7705 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSdp, consSepasolSdp,
CONSHDLR_SEPAFREQ,
7707 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSdp) );
7708 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSdp) );
7709 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSdp) );
7710 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSdp) );
7711 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSdp) );
7712 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSdp) );
7716 SCIP_CALL( SCIPaddIntParam(scip,
"constraints/SDP/threads",
"number of threads used for OpenBLAS",
7717 &(conshdlrdata->nthreads), TRUE, DEFAULT_NTHREADS, 1, INT_MAX, NULL, NULL) );
7720 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/propupperbounds",
7721 "Should upper bounds be propagated?",
7724 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/propubpresol",
7725 "Should upper bounds be propagated in presolving?",
7728 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/proptightenbounds",
7729 "Should tighten bounds be propagated?",
7732 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/proptbprobing",
7733 "Should tighten bounds be propagated in probing?",
7736 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/tightenboundscont",
7737 "Should only bounds be tightend for continuous variables?",
7740 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/tightenmatrices",
7741 "If all matrices are psd, should the matrices be tightened if possible?",
7744 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/tightenbounds",
7745 "If all matrices are psd, should the bounds be tightened if possible?",
7748 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/diaggezerocuts",
7749 "Should linear cuts enforcing the non-negativity of diagonal entries of SDP-matrices be added?",
7752 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/diagzeroimplcuts",
7753 "Should linear cuts enforcing the implications of diagonal entries of zero in SDP-matrices be added?",
7756 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/twominorlinconss",
7757 "Should linear cuts corresponding to 2 by 2 minors be added?",
7760 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/twominorprodconss",
7761 "Should linear cuts corresponding to products of 2 by 2 minors be added?",
7764 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/twominorvarbounds",
7765 "Should linear cuts corresponding to variable bounds for 2 by 2 minors be added?",
7768 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/quadconsrank1",
7769 "Should quadratic cons for 2x2 minors be added in the rank-1 case?",
7772 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/upgradequadconss",
7773 "Should quadratic constraints be upgraded to a rank 1 SDP?",
7776 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/upgradekeepquad",
7777 "Should the quadratic constraints be kept in the problem after upgrading and the corresponding SDP constraint be added without the rank 1 constraint?",
7780 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/separateonecut",
7781 "Should only one cut corresponding to the most negative eigenvalue be separated?",
7784 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/cutstopool",
7785 "Should the cuts be added to the pool?",
7788 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/sparsifycut",
7789 "Should the eigenvector cuts be sparsified?",
7792 SCIP_CALL( SCIPaddRealParam(scip,
"constraints/SDP/sparsifyfactor",
7793 "target size for sparsification in relation to number of variables",
7796 SCIP_CALL( SCIPaddIntParam(scip,
"constraints/SDP/sparsifytargetsize",
7797 "absolute target size for sparsification (-1: use sparsifyfactor instead)",
7800 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/multiplesparsecuts",
7801 "Should multiple sparsified eigenvector cuts be added?",
7804 SCIP_CALL( SCIPaddIntParam(scip,
"constraints/SDP/maxnsparsecuts",
7805 "maximal number of sparse eigenvector cuts that should be added (-1: no limit)",
7808 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/enforcesdp",
7809 "Solve SDP if we do lp-solving and have an integral solution in enforcing?",
7812 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/onlyfixedintssdp",
7813 "Should solving an SDP only be applied if all integral variables are fixed (instead of having integral values)?",
7816 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/addsocrelax",
7817 "Should a relaxation of SOC constraints be added?",
7820 SCIP_CALL( SCIPaddIntParam(scip,
"constraints/SDP/maxnvarsquadupgd",
7821 "maximal number of quadratic constraints and appearing variables so that the QUADCONSUPGD is performed",
7824 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/rank1approxheur",
7825 "Should the heuristic that computes the best rank-1 approximation for a given solution be executed?",
7828 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/usedimacsfeastol",
7829 "Should a feasibility tolerance based on the DIMACS be used for computing negative eigenvalues?",
7832 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/generaterows",
7833 "Should rows be generated (constraints otherwise)?",
7836 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/recomputesparseev",
7837 "Should the sparse eigenvalue returned from TPower be recomputed exactly by using Lapack for the corresponding submatrix?",
7840 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/recomputeinitial",
7841 "Should the inital vector for TPower be computed each time before calling TPower (instead of using the original smallest eigenvector)?",
7844 SCIP_CALL( SCIPaddBoolParam(scip,
"constraints/SDP/exacttrans",
7845 "Should the matrix be transformed with the exact maximal eigenvalue before calling TPower (instead of using estimate)?",
7856 SCIP_CONSHDLR* conshdlr = NULL;
7857 SCIP_CONSHDLR* sdpconshdlr;
7858 SCIP_CONSHDLRDATA* conshdlrdata = NULL;
7860 assert( scip != NULL );
7863 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
7866 conshdlrdata->diaggezerocuts = FALSE;
7867 conshdlrdata->propupperbounds = FALSE;
7868 conshdlrdata->propubpresol = FALSE;
7869 conshdlrdata->proptightenbounds = FALSE;
7870 conshdlrdata->proptbprobing = FALSE;
7871 conshdlrdata->tightenboundscont = FALSE;
7872 conshdlrdata->tightenmatrices = FALSE;
7873 conshdlrdata->tightenbounds = FALSE;
7874 conshdlrdata->diagzeroimplcuts = FALSE;
7875 conshdlrdata->twominorlinconss = FALSE;
7876 conshdlrdata->twominorprodconss = FALSE;
7877 conshdlrdata->twominorvarbounds = FALSE;
7878 conshdlrdata->quadconsrank1 = FALSE;
7879 conshdlrdata->upgradequadconss = FALSE;
7880 conshdlrdata->upgradekeepquad = FALSE;
7881 conshdlrdata->separateonecut = FALSE;
7882 conshdlrdata->cutstopool = FALSE;
7883 conshdlrdata->sparsifycut = FALSE;
7884 conshdlrdata->sparsifyfactor = SCIP_INVALID;
7885 conshdlrdata->sparsifytargetsize = -1;
7886 conshdlrdata->multiplesparsecuts = FALSE;
7887 conshdlrdata->maxnsparsecuts = 0;
7888 conshdlrdata->enforcesdp = FALSE;
7889 conshdlrdata->onlyfixedintssdp = FALSE;
7890 conshdlrdata->addsocrelax = FALSE;
7891 conshdlrdata->maxnvarsquadupgd = 0;
7892 conshdlrdata->triedlinearconss = FALSE;
7893 conshdlrdata->triedvarbounds = FALSE;
7894 conshdlrdata->rank1approxheur = FALSE;
7895 conshdlrdata->generaterows = FALSE;
7897 conshdlrdata->nthreads = 0;
7899 conshdlrdata->usedimacsfeastol = FALSE;
7900 conshdlrdata->recomputesparseev = FALSE;
7901 conshdlrdata->recomputeinitial = FALSE;
7902 conshdlrdata->exacttrans = FALSE;
7906 if ( sdpconshdlr == NULL )
7908 SCIPerrorMessage(
"Needs constraint handler <%s> to work.\n",
CONSHDLR_NAME);
7909 return SCIP_PLUGINNOTFOUND;
7911 conshdlrdata->sdpconshdlrdata = SCIPconshdlrGetData(sdpconshdlr);
7912 assert( conshdlrdata->sdpconshdlrdata != NULL );
7914 conshdlrdata->quadconsidx = NULL;
7915 conshdlrdata->quadconsvars = NULL;
7916 conshdlrdata->nquadconsidx = 0;
7917 conshdlrdata->X = NULL;
7918 conshdlrdata->nsdpvars = 0;
7919 conshdlrdata->sdpcons = NULL;
7920 conshdlrdata->randnumgen = NULL;
7921 conshdlrdata->relaxsdp = NULL;
7922 conshdlrdata->dimacsfeastol = SCIP_INVALID;
7927 consEnfolpSdp, consEnfopsSdp, consCheckSdp, consLockSdp, conshdlrdata) );
7929 assert( conshdlr != NULL );
7932 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSdp) );
7933 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSdp) );
7934 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySdpRank1, consCopySdp) );
7935 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr,consInitpreSdp) );
7936 SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitSdp) );
7937 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreSdp) );
7938 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSdp) );
7941 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSdp) );
7942 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSdp, consSepasolSdp,
CONSHDLR_SEPAFREQ,
7944 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSdp) );
7945 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSdp) );
7946 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSdp) );
7947 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSdp) );
7948 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSdp) );
7949 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSdp) );
7952 #if ( SCIP_VERSION >= 800 || ( SCIP_VERSION < 800 && SCIP_APIVERSION >= 100 ) ) 7953 SCIP_CALL( SCIPincludeConsUpgradeNonlinear(scip, consQuadConsUpgdSdp, 0, TRUE,
CONSHDLRRANK1_NAME) );
7955 SCIP_CALL( SCIPincludeQuadconsUpgrade(scip, consQuadConsUpgdSdp, 0, TRUE,
CONSHDLRRANK1_NAME) );
7972 return i*(i+1)/2 + j;
7999 SCIP_Real* constval,
8002 SCIP_Bool* addedquadcons
8005 SCIP_CONSDATA* consdata;
8008 assert( scip != NULL );
8009 assert( cons != NULL );
8010 assert( nvars != NULL );
8011 assert( nnonz != NULL );
8012 assert( blocksize != NULL );
8013 assert( arraylength != NULL );
8014 assert( nvarnonz != NULL );
8015 assert( col != NULL );
8016 assert( row != NULL );
8017 assert( val != NULL );
8018 assert( vars != NULL );
8019 assert( constnnonz != NULL );
8021 consdata = SCIPconsGetData(cons);
8023 assert( consdata->constnnonz == 0 || ( constcol != NULL && constrow != NULL && constval != NULL ) );
8025 *nvars = consdata->nvars;
8026 *nnonz = consdata->nnonz;
8027 *blocksize = consdata->blocksize;
8029 for (i = 0; i < consdata->nvars; i++)
8030 vars[i] = consdata->vars[i];
8033 if ( *arraylength < consdata->nvars )
8035 SCIPdebugMsg(scip,
"nvarnonz, col, row and val arrays were not long enough to store the information for cons %s, they need to be at least" 8036 "size %d, given was only length %d!\n", SCIPconsGetName(cons), consdata->nvars, *arraylength);
8037 *arraylength = consdata->nvars;
8041 for (i = 0; i < consdata->nvars; i++)
8043 nvarnonz[i] = consdata->nvarnonz[i];
8045 col[i] = consdata->col[i];
8046 row[i] = consdata->row[i];
8047 val[i] = consdata->val[i];
8052 if ( consdata->constnnonz > 0 )
8054 if ( consdata->constnnonz > *constnnonz )
8056 SCIPdebugMsg(scip,
"The constant nonzeros arrays were not long enough to store the information for cons %s, they need to be at least" 8057 "size %d, given was only length %d! \n", SCIPconsGetName(cons), consdata->constnnonz, *constnnonz);
8061 for (i = 0; i < consdata->constnnonz; i++)
8063 constcol[i] = consdata->constcol[i];
8064 constrow[i] = consdata->constrow[i];
8065 constval[i] = consdata->constval[i];
8070 *constnnonz = consdata->constnnonz;
8074 if ( rankone != NULL && maxevsubmat != NULL )
8076 *rankone = consdata->rankone;
8077 *maxevsubmat[0] = consdata->maxevsubmat[0];
8078 *maxevsubmat[1] = consdata->maxevsubmat[1];
8079 *addedquadcons = consdata->addedquadcons;
8096 SCIP_CONSDATA* consdata;
8098 assert( scip != NULL );
8099 assert( cons != NULL );
8101 consdata = SCIPconsGetData(cons);
8102 assert( consdata != NULL );
8104 if ( nnonz != NULL )
8105 *nnonz = consdata->nnonz;
8107 if ( constnnonz != NULL )
8108 *constnnonz = consdata->constnnonz;
8119 SCIP_CONSDATA* consdata;
8121 assert( scip != NULL );
8122 assert( cons != NULL );
8124 consdata = SCIPconsGetData(cons);
8125 assert( consdata != NULL );
8127 return consdata->nvars;
8136 SCIP_CONSDATA* consdata;
8138 assert( scip != NULL );
8139 assert( cons != NULL );
8141 consdata = SCIPconsGetData(cons);
8142 assert( consdata != NULL );
8144 return consdata->vars;
8153 SCIP_CONSDATA* consdata;
8155 assert( scip != NULL );
8156 assert( cons != NULL );
8158 consdata = SCIPconsGetData(cons);
8159 assert( consdata != NULL );
8161 return consdata->blocksize;
8172 SCIP_CONSDATA* consdata;
8176 assert( scip != NULL );
8177 assert( cons != NULL );
8179 assert( Aj != NULL );
8181 consdata = SCIPconsGetData(cons);
8182 assert( consdata != NULL );
8183 blocksize = consdata->blocksize;
8185 assert( j < consdata->nvars );
8187 for (i = 0; i < blocksize * blocksize; i++)
8190 for (i = 0; i < consdata->nvarnonz[j]; i++)
8192 Aj[consdata->col[j][i] * blocksize + consdata->row[j][i]] = consdata->val[j][i];
8193 Aj[consdata->row[j][i] * blocksize + consdata->col[j][i]] = consdata->val[j][i];
8206 SCIP_CONSDATA* consdata;
8211 assert( scip != NULL );
8212 assert( cons != NULL );
8213 assert( mat != NULL );
8215 consdata = SCIPconsGetData(cons);
8216 blocksize = consdata->blocksize;
8218 for (i = 0; i < blocksize; i++)
8220 for (j = 0; j < blocksize; j++)
8221 mat[i * blocksize + j] = 0.0;
8224 for (i = 0; i < consdata->constnnonz; i++)
8226 mat[consdata->constcol[i] * blocksize + consdata->constrow[i]] = consdata->constval[i];
8227 mat[consdata->constrow[i] * blocksize + consdata->constcol[i]] = consdata->constval[i];
8240 SCIP_CONSDATA* consdata;
8244 assert( scip != NULL );
8245 assert( cons != NULL );
8246 assert( mat != NULL );
8248 consdata = SCIPconsGetData(cons);
8249 assert( consdata != NULL );
8251 blocksize = consdata->blocksize;
8254 for (i = 0; i < (blocksize * (blocksize + 1)) / 2; i++)
8257 for (i = 0; i < consdata->constnnonz; i++)
8276 SCIP_Real* lambdastar
8279 SCIP_CONSDATA* consdata;
8281 SCIP_Real maxinfnorm;
8283 SCIP_Real mininfnorm;
8286 SCIP_Real primalguess;
8287 SCIP_Real dualguess;
8293 assert( scip != NULL );
8294 assert( cons != NULL );
8295 assert( lambdastar != NULL );
8296 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLR_NAME) == 0 || strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
CONSHDLRRANK1_NAME) == 0 );
8298 consdata = SCIPconsGetData(cons);
8299 assert( consdata != NULL );
8305 if ( consdata->nnonz == 0 )
8307 *lambdastar = 100.0;
8311 blocksize = consdata->blocksize;
8313 sparsity = consdata->nnonz / (0.5 * blocksize * (blocksize + 1));
8317 mininfnorm = SCIPinfinity(scip);
8318 for (v = 0; v < consdata->nvars; v++)
8320 for (i = 0; i < consdata->nvarnonz[v]; i++)
8322 if ( SCIPisGT(scip, REALABS(consdata->val[v][i]), maxinfnorm ) )
8323 maxinfnorm = REALABS(consdata->val[v][i]);
8324 if ( SCIPisLT(scip, REALABS(consdata->val[v][i]), mininfnorm) )
8325 mininfnorm = REALABS(consdata->val[v][i]);
8329 for (i = 0; i < consdata->constnnonz; i++)
8331 if ( SCIPisGT(scip, REALABS(consdata->constval[i]), maxconst ) )
8332 maxconst = REALABS(consdata->constval[i]);
8335 assert( SCIPisGT(scip, mininfnorm, 0.0) );
8340 for (v = 0; v < consdata->nvars; v++)
8342 if ( SCIPisGT(scip, REALABS(SCIPvarGetObj(consdata->vars[v])), maxobj) )
8343 maxobj = REALABS(SCIPvarGetObj(consdata->vars[v]));
8344 compval = SCIPisInfinity(scip, REALABS(SCIPvarGetUbGlobal(consdata->vars[v]))) ? 1e+6 : REALABS(SCIPvarGetUbGlobal(consdata->vars[v]));
8345 if ( SCIPisGT(scip, compval, maxbound) )
8347 compval = SCIPisInfinity(scip, REALABS(SCIPvarGetLbGlobal(consdata->vars[v]))) ? 1e+6 : REALABS(SCIPvarGetUbGlobal(consdata->vars[v]));
8348 if ( SCIPisGT(scip, compval, maxbound) )
8353 if ( SCIPisEQ(scip, maxbound, 0.0) )
8357 primalguess = maxobj / (sparsity * mininfnorm);
8358 dualguess = sparsity * maxinfnorm * maxbound + maxconst;
8360 if ( SCIPisGT(scip, primalguess, dualguess) )
8361 *lambdastar = primalguess;
8363 *lambdastar = dualguess;
8374 SCIP_CONSDATA* consdata;
8376 assert( scip != NULL );
8377 assert( cons != NULL );
8379 consdata = SCIPconsGetData(cons);
8381 return consdata->maxrhsentry;
8390 SCIP_CONSDATA* consdata;
8395 assert( scip != NULL );
8396 assert( cons != NULL );
8398 consdata = SCIPconsGetData(cons);
8402 for (v = 0; v < consdata->nvars; v++)
8404 for (i = 0; i < consdata->nvarnonz[v]; i++)
8406 if ( SCIPisGT(scip, REALABS(consdata->val[v][i]), maxcoef) )
8407 maxcoef = REALABS(consdata->val[v][i]);
8423 SCIP_CONSDATA* consdata;
8428 assert( cons != NULL );
8430 consdata = SCIPconsGetData(cons);
8431 assert( consdata != NULL );
8433 ub = consdata->constnnonz;
8435 for (v = 0; v < consdata->nvars; v++)
8436 ub += consdata->nvarnonz[v];
8438 denselength = consdata->blocksize * (consdata->blocksize + 1) / 2;
8440 return (ub <= denselength ? ub : denselength);
8458 SCIP_CONSDATA* consdata;
8463 assert( scip != NULL );
8464 assert( cons != NULL );
8465 assert( sol != NULL );
8466 assert( length != NULL );
8467 assert( row != NULL );
8468 assert( col != NULL );
8469 assert( val != NULL );
8471 consdata = SCIPconsGetData(cons);
8472 assert( consdata != NULL );
8475 nnonz = consdata->constnnonz;
8476 if ( *length < nnonz )
8479 SCIPerrorMessage(
"Arrays not long enough in SCIPconsSdpComputeSparseSdpMatrix, length %d given, need at least %d (probably more)\n",
8484 for (i = 0; i < consdata->constnnonz; i++)
8486 row[i] = consdata->constrow[i];
8487 col[i] = consdata->constcol[i];
8488 val[i] = -1 * consdata->constval[i];
8492 for (v = 0; v < consdata->nvars; v++)
8494 SCIP_CALL(
SCIPsdpVarfixerMergeArrays(SCIPblkmem(scip), SCIPepsilon(scip), consdata->row[v], consdata->col[v], consdata->val[v], consdata->nvarnonz[v],
8495 FALSE, SCIPgetSolVal(scip, sol, consdata->vars[v]), row, col, val, &nnonz, *length) );
8496 if ( nnonz > *length )
8499 SCIPerrorMessage(
"Arrays not long enough in SCIPconsSdpComputeSparseSdpMatrix, length %d given, need at least %d (probably more)\n",
8516 SCIP_CONSDATA* consdata;
8518 assert( cons != NULL );
8520 consdata = SCIPconsGetData(cons);
8521 assert( consdata != NULL );
8523 return consdata->rankone;
8533 SCIP_CONSDATA* consdata;
8535 assert( cons != NULL );
8537 consdata = SCIPconsGetData(cons);
8538 assert( consdata != NULL );
8539 assert( maxevsubmat != NULL );
8541 *maxevsubmat[0] = consdata->maxevsubmat[0];
8542 *maxevsubmat[1] = consdata->maxevsubmat[1];
8552 SCIP_CONSDATA* consdata;
8554 assert( cons != NULL );
8556 consdata = SCIPconsGetData(cons);
8557 assert( consdata != NULL );
8559 return consdata->addedquadcons;
8581 SCIP_Real* constval,
8582 SCIP_Bool removeduplicates
8585 SCIP_CONSHDLR* conshdlr;
8586 SCIP_CONSDATA* consdata = NULL;
8590 assert( scip != NULL );
8591 assert( cons != NULL );
8592 assert( name != NULL );
8593 assert( nvars >= 0 );
8594 assert( nnonz >= 0 );
8595 assert( blocksize >= 0 );
8596 assert( constnnonz >= 0 );
8597 assert( nvars == 0 || vars != NULL );
8598 assert( nnonz == 0 || (nvarnonz != NULL && col != NULL && row != NULL && val != NULL ));
8599 assert( constnnonz == 0 || (constcol != NULL && constrow != NULL && constval != NULL ));
8601 conshdlr = SCIPfindConshdlr(scip,
"SDP");
8602 if ( conshdlr == NULL )
8604 SCIPerrorMessage(
"SDP constraint handler not found\n");
8605 return SCIP_PLUGINNOTFOUND;
8609 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
8610 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->nvarnonz, nvars) );
8611 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col, nvars) );
8612 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row, nvars) );
8613 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val, nvars) );
8614 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constcol, constnnonz) );
8615 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constrow, constnnonz) );
8616 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constval, constnnonz) );
8617 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
8619 for (i = 0; i < nvars; i++)
8621 assert( nvarnonz[i] >= 0 );
8623 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col[i], nvarnonz[i]));
8624 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row[i], nvarnonz[i]));
8625 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val[i], nvarnonz[i]));
8628 consdata->nvars = nvars;
8629 consdata->nnonz = nnonz;
8630 consdata->constnnonz = constnnonz;
8631 consdata->blocksize = blocksize;
8632 consdata->locks = NULL;
8633 consdata->matrixvar = NULL;
8634 consdata->matrixval = NULL;
8635 consdata->matrixconst = NULL;
8636 consdata->nsingle = 0;
8637 consdata->tracebound = -2.0;
8638 consdata->allmatricespsd = FALSE;
8639 consdata->initallmatricespsd = FALSE;
8641 for (i = 0; i < nvars; i++)
8643 consdata->nvarnonz[i] = nvarnonz[i];
8645 if ( nvarnonz[i] > 0 )
8648 if ( removeduplicates )
8656 while ( cnt < nvarnonz[i] )
8658 assert( 0 <= row[i][cnt] && row[i][cnt] < blocksize );
8659 assert( 0 <= col[i][cnt] && col[i][cnt] < blocksize );
8660 assert( row[i][cnt] >= col[i][cnt] );
8662 while ( cnt < nvarnonz[i] - 1 && row[i][cnt] == row[i][cnt+1] && col[i][cnt] == col[i][cnt+1] )
8664 if ( ! SCIPisEQ(scip, val[i][cnt], val[i][cnt+1]) )
8666 SCIPerrorMessage(
"Duplicate matrix entry (%d,%d) with different value (%g vs. %g).\n", row[i][cnt], col[i][cnt], val[i][cnt], val[i][cnt+1]);
8667 return SCIP_INVALIDDATA;
8672 consdata->row[i][c] = row[i][cnt];
8673 consdata->col[i][c] = col[i][cnt];
8674 consdata->val[i][c] = val[i][cnt];
8680 if ( c < nvarnonz[i] )
8682 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col[i], nvarnonz[i], c));
8683 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row[i], nvarnonz[i], c));
8684 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val[i], nvarnonz[i], c));
8685 consdata->nvarnonz[i] = c;
8690 for (j = 0; j < nvarnonz[i]; j++)
8692 assert( 0 <= row[i][j] && row[i][j] < blocksize );
8693 assert( 0 <= col[i][j] && col[i][j] < blocksize );
8694 assert( row[i][j] >= col[i][j] );
8696 consdata->row[i][j] = row[i][j];
8697 consdata->col[i][j] = col[i][j];
8698 consdata->val[i][j] = val[i][j];
8704 if ( constnnonz > 0 )
8707 if ( removeduplicates )
8715 while ( cnt < constnnonz )
8717 while ( cnt < constnnonz - 1 && constrow[cnt] == constrow[cnt+1] && constcol[cnt] == constcol[cnt+1] )
8719 if ( ! SCIPisEQ(scip, constval[cnt], constval[cnt+1]) )
8721 SCIPerrorMessage(
"Duplicate entry (%d,%d) with different value (%g vs. %g) in constant matrix.\n", constrow[cnt], constcol[cnt], constval[cnt], constval[cnt+1]);
8722 return SCIP_INVALIDDATA;
8727 assert( 0 <= constrow[cnt] && constrow[cnt] < blocksize );
8728 assert( 0 <= constcol[cnt] && constcol[cnt] < blocksize );
8729 assert( constrow[cnt] >= constcol[cnt] );
8731 consdata->constrow[c] = constrow[cnt];
8732 consdata->constcol[c] = constcol[cnt];
8733 consdata->constval[c] = constval[cnt];
8739 if ( c < constnnonz )
8741 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constcol, constnnonz, c) );
8742 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constrow, constnnonz, c) );
8743 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constval, constnnonz, c) );
8744 consdata->constnnonz = c;
8749 for (j = 0; j < constnnonz; j++)
8751 assert( 0 <= constrow[j] && constrow[j] < blocksize );
8752 assert( 0 <= constcol[j] && constcol[j] < blocksize );
8753 assert( constrow[j] >= constcol[j] );
8755 consdata->constrow[j] = constrow[j];
8756 consdata->constcol[j] = constcol[j];
8757 consdata->constval[j] = constval[j];
8762 for (i = 0; i < nvars; i++)
8764 consdata->vars[i] = vars[i];
8765 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
8767 SCIPdebugMsg(scip,
"creating cons %s.\n", name);
8769 consdata->rankone = FALSE;
8772 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->maxevsubmat, 2) );
8773 consdata->maxevsubmat[0] = -1;
8774 consdata->maxevsubmat[1] = -1;
8777 consdata->addedquadcons = FALSE;
8780 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
8808 SCIP_Real* constval,
8809 SCIP_Bool removeduplicates
8812 SCIP_CONSHDLR* conshdlr;
8813 SCIP_CONSDATA* consdata = NULL;
8817 assert( scip != NULL );
8818 assert( cons != NULL );
8819 assert( name != NULL );
8820 assert( nvars >= 0 );
8821 assert( nnonz >= 0 );
8822 assert( blocksize >= 0 );
8823 assert( constnnonz >= 0 );
8824 assert( nvars == 0 || vars != NULL );
8825 assert( nnonz == 0 || (nvarnonz != NULL && col != NULL && row != NULL && val != NULL ));
8826 assert( constnnonz == 0 || (constcol != NULL && constrow != NULL && constval != NULL ));
8829 if ( conshdlr == NULL )
8831 SCIPerrorMessage(
"Rank 1 SDP constraint handler not found\n");
8832 return SCIP_PLUGINNOTFOUND;
8836 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
8837 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->nvarnonz, nvars) );
8838 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col, nvars) );
8839 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row, nvars) );
8840 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val, nvars) );
8841 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constcol, constnnonz) );
8842 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constrow, constnnonz) );
8843 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constval, constnnonz) );
8844 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
8846 for (i = 0; i < nvars; i++)
8848 assert( nvarnonz[i] >= 0 );
8850 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col[i], nvarnonz[i]));
8851 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row[i], nvarnonz[i]));
8852 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val[i], nvarnonz[i]));
8855 consdata->nvars = nvars;
8856 consdata->nnonz = nnonz;
8857 consdata->constnnonz = constnnonz;
8858 consdata->blocksize = blocksize;
8859 consdata->locks = NULL;
8860 consdata->matrixvar = NULL;
8861 consdata->matrixval = NULL;
8862 consdata->matrixconst = NULL;
8863 consdata->nsingle = 0;
8864 consdata->tracebound = -2.0;
8865 consdata->allmatricespsd = FALSE;
8866 consdata->initallmatricespsd = FALSE;
8868 for (i = 0; i < nvars; i++)
8870 consdata->nvarnonz[i] = nvarnonz[i];
8872 if ( nvarnonz[i] > 0 )
8875 if ( removeduplicates )
8883 while ( cnt < nvarnonz[i] )
8885 assert( 0 <= row[i][cnt] && row[i][cnt] < blocksize );
8886 assert( 0 <= col[i][cnt] && col[i][cnt] < blocksize );
8887 assert( row[i][cnt] >= col[i][cnt] );
8889 while ( cnt < nvarnonz[i] - 1 && row[i][cnt] == row[i][cnt+1] && col[i][cnt] == col[i][cnt+1] )
8891 if ( ! SCIPisEQ(scip, val[i][cnt], val[i][cnt+1]) )
8893 SCIPerrorMessage(
"Duplicate matrix entry (%d,%d) with different value (%g vs. %g).\n", row[i][cnt], col[i][cnt], val[i][cnt], val[i][cnt+1]);
8894 return SCIP_INVALIDDATA;
8899 consdata->row[i][c] = row[i][cnt];
8900 consdata->col[i][c] = col[i][cnt];
8901 consdata->val[i][c] = val[i][cnt];
8907 if ( c < nvarnonz[i] )
8909 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col[i], nvarnonz[i], c));
8910 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row[i], nvarnonz[i], c));
8911 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val[i], nvarnonz[i], c));
8912 consdata->nvarnonz[i] = c;
8917 for (j = 0; j < nvarnonz[i]; j++)
8919 assert( 0 <= row[i][j] && row[i][j] < blocksize );
8920 assert( 0 <= col[i][j] && col[i][j] < blocksize );
8921 assert( row[i][j] >= col[i][j] );
8923 consdata->row[i][j] = row[i][j];
8924 consdata->col[i][j] = col[i][j];
8925 consdata->val[i][j] = val[i][j];
8931 if ( constnnonz > 0 )
8934 if ( removeduplicates )
8942 while ( cnt < constnnonz )
8944 while ( cnt < constnnonz - 1 && constrow[cnt] == constrow[cnt+1] && constcol[cnt] == constcol[cnt+1] )
8946 if ( ! SCIPisEQ(scip, constval[cnt], constval[cnt+1]) )
8948 SCIPerrorMessage(
"Duplicate entry (%d,%d) with different value (%g vs. %g) in constant matrix.\n", constrow[cnt], constcol[cnt], constval[cnt], constval[cnt+1]);
8949 return SCIP_INVALIDDATA;
8954 assert( 0 <= constrow[cnt] && constrow[cnt] < blocksize );
8955 assert( 0 <= constcol[cnt] && constcol[cnt] < blocksize );
8956 assert( constrow[cnt] >= constcol[cnt] );
8958 consdata->constrow[c] = constrow[cnt];
8959 consdata->constcol[c] = constcol[cnt];
8960 consdata->constval[c] = constval[cnt];
8966 if ( c < constnnonz )
8968 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constcol, constnnonz, c) );
8969 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constrow, constnnonz, c) );
8970 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->constval, constnnonz, c) );
8971 consdata->constnnonz = c;
8976 for (j = 0; j < constnnonz; j++)
8978 assert( 0 <= constrow[j] && constrow[j] < blocksize );
8979 assert( 0 <= constcol[j] && constcol[j] < blocksize );
8980 assert( constrow[j] >= constcol[j] );
8982 consdata->constrow[j] = constrow[j];
8983 consdata->constcol[j] = constcol[j];
8984 consdata->constval[j] = constval[j];
8989 for (i = 0; i < nvars; i++)
8991 consdata->vars[i] = vars[i];
8992 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
8994 SCIPdebugMsg(scip,
"creating cons %s (rank 1).\n", name);
8995 consdata->rankone = TRUE;
8998 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->maxevsubmat, 2) );
8999 consdata->maxevsubmat[0] = -1;
9000 consdata->maxevsubmat[1] = -1;
9003 consdata->addedquadcons = FALSE;
9006 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
SCIP_Real SCIPconsSdpGetMaxConstEntry(SCIP *scip, SCIP_CONS *cons)
int SCIPconsSdpGetNVars(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE addMultipleSparseCuts(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int blocksize, SCIP_Real *fullmatrix, SCIP_Real *fullconstmatrix, SCIP_Real *eigenvector, SCIP_Real tol, int maxncuts, SCIP_Real *vector, SCIP_VAR **vars, SCIP_Real *vals, int *ncuts, SCIP_Bool *success, SCIP_RESULT *result)
static SCIP_DECL_CONSTRANS(consTransSdp)
int SCIPconsSdpComputeUbSparseSdpMatrixLength(SCIP_CONS *cons)
#define DEFAULT_QUADCONSRANK1
SCIP_RETCODE SCIPconsSdpGetFullAj(SCIP *scip, SCIP_CONS *cons, int j, SCIP_Real *Aj)
static SCIP_RETCODE addTwoMinorProdConstraints(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool solvesdps, int *naddconss)
#define DEFAULT_MULTIPLESPARSECUTS
void SCIPsdpVarfixerSortRowCol(int *row, int *col, SCIP_Real *val, int length)
#define DEFAULT_ENFORCESDP
static SCIP_RETCODE convertRowToColFormatFullMatrix(int rows, int cols, SCIP_Real *rowmatrix, SCIP_Real *colmatrix)
#define CONSHDLR_PRESOLTIMING
SCIP_RETCODE SCIPsolveOneVarSDPDense(BMS_BUFMEM *bufmem, SCIP_Real obj, SCIP_Real lb, SCIP_Real ub, int blocksize, SCIP_Real *fullconstmatrix, int sdpnnonz, int *sdprow, int *sdpcol, SCIP_Real *sdpval, SCIP_Real infinity, SCIP_Real feastol, SCIP_Real *objval, SCIP_Real *optval)
static SCIP_RETCODE addRank1QuadConss(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *naddconss)
SCIP_RETCODE SCIPincludeConshdlrSdp(SCIP *scip)
static SCIP_RETCODE multiplyConstraintMatrix(SCIP_CONS *cons, int j, SCIP_Real *v, SCIP_Real *vAv)
#define DEFAULT_ONLYFIXEDINTSSDP
static SCIP_DECL_CONSENFORELAX(consEnforelaxSdp)
#define DEFAULT_PROPUPPERBOUNDS
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPcreateConsSdpRank1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, int nnonz, int blocksize, int *nvarnonz, int **col, int **row, SCIP_Real **val, SCIP_VAR **vars, int constnnonz, int *constcol, int *constrow, SCIP_Real *constval, SCIP_Bool removeduplicates)
#define DEFAULT_SPARSIFYFACTOR
static SCIP_RETCODE tightenBounds(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool tightenboundscont, int *nchgbds, SCIP_Bool *infeasible)
#define DEFAULT_TWOMINORPRODCONSS
static SCIP_DECL_CONSDELETE(consDeleteSdp)
#define DEFAULT_SEPARATEONECUT
SCIP_Bool SCIPconsSdpAddedQuadCons(SCIP_CONS *cons)
#define CONSHDLR_SEPAFREQ
#define DEFAULT_CUTSTOPOOL
static SCIP_RETCODE SCIPconsSdpCheckSdpCons(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_RESULT *result)
#define DEFAULT_RECOMPUTEINITIAL
SCIP_RETCODE SCIPcreateConsSdp(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, int nnonz, int blocksize, int *nvarnonz, int **col, int **row, SCIP_Real **val, SCIP_VAR **vars, int constnnonz, int *constcol, int *constrow, SCIP_Real *constval, SCIP_Bool removeduplicates)
static SCIP_RETCODE sparsifyCut(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_SOL *sol, int blocksize, SCIP_Real *fullconstmatrix, SCIP_Real *eigenvector, SCIP_Real *vector, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Bool *success, SCIP_RESULT *result)
static SCIP_DECL_CONSEXIT(consExitSdp)
#define DEFAULT_PROPTIGHTENBOUNDS
static SCIP_DECL_CONSPROP(consPropSdp)
static SCIP_RETCODE addTwoMinorVarBounds(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool solvesdps, int *naddconss)
#define CONSHDLR_DELAYSEPA
static SCIP_RETCODE checkVarsLocks(SCIP *scip, SCIP_CONS *cons)
#define CONSHDLR_EAGERFREQ
#define DEFAULT_MAXNVARSQUADUPGD
#define DEFAULT_DIAGGEZEROCUTS
SCIP_RETCODE SCIPconsSdpComputeSparseSdpMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, int *length, int *row, int *col, SCIP_Real *val)
#define DEFAULT_TIGHTENBOUNDS
SCIP_RETCODE SCIPconsSdpGetLowerTriangConstMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat)
static SCIP_DECL_CONSSEPALP(consSepalpSdp)
static SCIP_RETCODE truncatedPowerMethod(SCIP *scip, int blocksize, SCIP_Real *fullmatrix, SCIP_Real *vector, int sparsity, SCIP_Real convergencetol, SCIP_Real *eigenvector, int *support, SCIP_Real *eigenvalue)
static SCIP_RETCODE setMaxRhsEntry(SCIP_CONS *cons)
SCIP_RETCODE SCIPlapackMatrixMatrixMult(int nrowsA, int ncolsA, SCIP_Real *matrixA, SCIP_Bool transposeA, int nrowsB, int ncolsB, SCIP_Real *matrixB, SCIP_Bool transposeB, SCIP_Real *result)
#define DEFAULT_RANK1APPROXHEUR
static SCIP_DECL_CONSCHECK(consCheckSdp)
Constraint handler for SDP-constraints.
static SCIP_RETCODE expandSymMatrix(int size, SCIP_Real *symMat, SCIP_Real *fullMat)
#define DEFAULT_PROPTBPROBING
maps SCIP variables to SDP indices (the SCIP variables are given SDP indices in the order in which th...
SCIP_RETCODE SCIPconsSdpGetFullConstMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat)
static SCIP_RETCODE separateSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool enforce, SCIP_RESULT *result)
static SCIP_RETCODE constructMatrixvar(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata)
SCIP_Real SCIPconsSdpGetMaxSdpCoef(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE scaleRowsMatrix(int blocksize, SCIP_Real *matrix, SCIP_Real *scale)
int SCIPconsSdpCompLowerTriangPos(int i, int j)
static SCIP_RETCODE propagateUpperBounds(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *infeasible, int *nprop)
SCIP_RETCODE SCIPconsSdpGetMaxEVSubmat(SCIP_CONS *cons, int **maxevsubmat)
SCIP_RETCODE SCIPlapackMatrixVectorMult(int nrows, int ncols, SCIP_Real *matrix, SCIP_Real *vector, SCIP_Real *result)
SCIP_RETCODE SCIPconsSdpGetData(SCIP *scip, SCIP_CONS *cons, int *nvars, int *nnonz, int *blocksize, int *arraylength, int *nvarnonz, int **col, int **row, SCIP_Real **val, SCIP_VAR **vars, int *constnnonz, int *constcol, int *constrow, SCIP_Real *constval, SCIP_Bool *rankone, int **maxevsubmat, SCIP_Bool *addedquadcons)
#define CONSHDLR_CHECKPRIORITY
#define DEFAULT_TIGHTENBOUNDSCONT
#define DEFAULT_MAXNSPARSECUTS
static SCIP_DECL_CONSENFOPS(consEnfopsSdp)
SCIP_Bool SCIPconsSdpShouldBeRankOne(SCIP_CONS *cons)
#define DEFAULT_DIAGZEROIMPLCUTS
SCIP_Bool SCIPrelaxSdpSolvedProbing(SCIP_RELAX *relax)
#define CONSHDLR_PROPFREQ
static SCIP_RETCODE computeSdpMatrix(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, SCIP_Real *matrix)
static SCIP_RETCODE isMatrixRankOne(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *result)
#define CONSHDLR_PROPTIMING
adds the main functionality to fix/unfix/(multi-)aggregate variables by merging two three-tuple-array...
#define DEFAULT_UPGRADEQUADCONSS
#define CONSHDLR_ENFOPRIORITY
static SCIP_RETCODE tightenMatrices(SCIP *scip, SCIP_CONS **conss, int nconss, int *nchgcoefs)
SCIP_VAR ** SCIPconsSdpGetVars(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE addTwoMinorLinConstraints(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool solvesdps, int *naddconss)
static SCIP_DECL_CONSFREE(consFreeSdp)
static SCIP_DECL_CONSPRESOL(consPresolSdp)
SCIP_RETCODE SCIPincludeConshdlrSdpRank1(SCIP *scip)
static SCIP_DECL_CONSEXITPRE(consExitpreSdp)
static SCIP_DECL_CONSPRINT(consPrintSdp)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySdp)
static SCIP_RETCODE updateVarLocks(SCIP *scip, SCIP_CONS *cons, int v)
#define CONSHDLR_MAXPREROUNDS
#define CONSHDLRRANK1_NAME
static SCIP_DECL_CONSINITPRE(consInitpreSdp)
static SCIP_DECL_CONSINITSOL(consInitsolSdp)
static SCIP_DECL_CONSPARSE(consParseSdp)
#define CONSHDLRRANK1_DESC
#define DEFAULT_TWOMINORVARBOUNDS
static SCIP_RETCODE addTwoMinorSOCConstraints(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool solvesdps, int *naddconss)
#define DEFAULT_SPARSIFYTARGETSIZE
#define DEFAULT_USEDIMACSFEASTOL
static SCIP_RETCODE diagZeroImpl(SCIP *scip, SCIP_CONS **conss, int nconss, int *naddconss)
int SCIPconsSdpGetBlocksize(SCIP *scip, SCIP_CONS *cons)
#define DEFAULT_UPGRADEKEEPQUAD
#define DEFAULT_TIGHTENMATRICES
static SCIP_RETCODE diagGEzero(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_Bool solvesdps, int *naddconss, int *nchgbds, SCIP_Bool *infeasible)
static SCIP_DECL_CONSSEPASOL(consSepasolSdp)
SCIP_RETCODE SCIPsdpVarfixerMergeArrays(BMS_BLKMEM *blkmem, SCIP_Real epsilon, int *originrow, int *origincol, SCIP_Real *originval, int originlength, SCIP_Bool originsorted, SCIP_Real scalar, int *targetrow, int *targetcol, SCIP_Real *targetval, int *targetlength, int targetmemory)
#define DEFAULT_RECOMPUTESPARSEEV
Solve SDP with one variable.
static SCIP_RETCODE computeFullSdpMatrix(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol, SCIP_Real *fullmatrix)
static SCIP_DECL_CONSGETVARS(consGetVarsSdp)
static SCIP_RETCODE computeAllmatricespsd(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPrelaxSdpIsFeasible(SCIP_RELAX *relax)
#define CONSHDLR_SEPAPRIORITY
SCIP_RETCODE SCIPlapackLinearSolve(BMS_BUFMEM *bufmem, int m, int n, SCIP_Real *A, SCIP_Real *b, SCIP_Real *x)
#define DEFAULT_ADDSOCRELAX
SCIP_RETCODE SCIPconsSdpGetNNonz(SCIP *scip, SCIP_CONS *cons, int *nnonz, int *constnnonz)
#define DEFAULT_SPARSIFYCUT
interface methods for eigenvector computation and matrix multiplication using openblas ...
SCIP_RETCODE SCIPlapackComputeEigenvectorsNegative(BMS_BUFMEM *bufmem, int n, SCIP_Real *A, SCIP_Real tol, int *neigenvalues, SCIP_Real *eigenvalues, SCIP_Real *eigenvectors)
static SCIP_DECL_CONSRESPROP(consRespropSdp)
static SCIP_RETCODE fixAndAggrVars(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool aggregate)
static SCIP_DECL_CONSLOCK(consLockSdp)
SCIP_RETCODE SCIPlapackComputeEigenvectorDecomposition(BMS_BUFMEM *bufmem, int n, SCIP_Real *A, SCIP_Real *eigenvalues, SCIP_Real *eigenvectors)
SCIP_RETCODE SCIPlapackComputeIthEigenvalue(BMS_BUFMEM *bufmem, SCIP_Bool geteigenvectors, int n, SCIP_Real *A, int i, SCIP_Real *eigenvalue, SCIP_Real *eigenvector)
#define DEFAULT_PROPUBPRESOL
static SCIP_RETCODE move_1x1_blocks_to_lp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int *naddconss, int *ndelconss, int *nchgbds, SCIP_Bool *infeasible)
#define DEFAULT_EXACTTRANS
static SCIP_DECL_CONSGETNVARS(consGetNVarsSdp)
static SCIP_DECL_CONSCOPY(consCopySdp)
#define DEFAULT_TWOMINORLINCONSS
SCIP_RETCODE SCIPconsSdpGuessInitialPoint(SCIP *scip, SCIP_CONS *cons, SCIP_Real *lambdastar)
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, int diags, int diagt, int pos, SCIP_Bool upperbound, SCIP_Bool usepos)
static SCIP_DECL_QUADCONSUPGD(consQuadConsUpgdSdp)
#define DEFAULT_GENERATEROWS
static SCIP_RETCODE multiaggrVar(SCIP *scip, SCIP_CONS *cons, int v, SCIP_VAR **aggrvars, SCIP_Real *scalars, int naggrvars, SCIP_Real constant, int *savedcol, int *savedrow, SCIP_Real *savedval, int *nfixednonz, int *vararraylength)
static SCIP_RETCODE unlockVar(SCIP *scip, SCIP_CONSDATA *consdata, int v)
static SCIP_DECL_CONSENFOLP(consEnfolpSdp)