53 #include "scip/cons_linear.h"
54 #include "scip/scip.h"
56 #define CONSHDLR_NAME "SDP"
57 #define CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd"
58 #define CONSHDLR_SEPAPRIORITY +1000000
59 #define CONSHDLR_ENFOPRIORITY -2000000
60 #define CONSHDLR_CHECKPRIORITY -2000000
61 #define CONSHDLR_SEPAFREQ 1
62 #define CONSHDLR_EAGERFREQ 100
64 #define CONSHDLR_MAXPREROUNDS -1
65 #define CONSHDLR_DELAYSEPA FALSE
66 #define CONSHDLR_NEEDSCONS TRUE
68 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
86 SCIP_Real maxrhsentry;
90 struct SCIP_ConshdlrData
111 return i*(i+1)/2 + j;
114 #define compLowerTriangPos(i, j) (i*(i+1)/2 + j)
130 assert( symMat != NULL );
131 assert( fullMat != NULL );
134 for (i = 0; i < size; i++)
136 for (j = 0; j <= i; j++)
139 fullMat[i*size + j] = symMat[ind];
140 fullMat[j*size + i] = symMat[ind];
159 SCIP_CONSDATA* consdata;
166 assert( cons != NULL );
167 assert( matrix != NULL );
169 consdata = SCIPconsGetData(cons);
170 nvars = consdata->nvars;
171 blocksize = consdata->blocksize;
174 for (i = 0; i < (blocksize * (blocksize + 1))/2; i++)
178 for (i = 0; i < nvars; i++)
180 yval = SCIPgetSolVal(scip, y, consdata->vars[i]);
181 for (ind = 0; ind < consdata->nvarnonz[i]; ind++)
182 matrix[
compLowerTriangPos(consdata->row[i][ind], consdata->col[i][ind])] += yval * consdata->val[i][ind];
186 for (ind = 0; ind < consdata->constnnonz; ind++)
187 matrix[
compLowerTriangPos(consdata->constrow[ind], consdata->constcol[ind])] -= consdata->constval[ind];
201 SCIP_CONSDATA* consdata;
204 assert( cons != NULL );
206 assert( vAv != NULL );
208 consdata = SCIPconsGetData(cons);
209 assert( consdata != NULL );
211 assert( j < consdata->nvars );
216 for (i = 0; i < consdata->nvarnonz[j]; i++)
218 if (consdata->col[j][i] == consdata->row[j][i])
219 *vAv += v[consdata->col[j][i]] * consdata->val[j][i] * v[consdata->row[j][i]];
223 *vAv += 2.0 * v[consdata->col[j][i]] * consdata->val[j][i] * v[consdata->row[j][i]];
238 SCIP_CONSDATA* consdata;
242 consdata = SCIPconsGetData(cons);
243 assert( consdata != NULL );
249 for (i = 0; i < consdata->constnnonz; i++)
251 if ( REALABS(consdata->constval[i]) > max )
252 max = REALABS(consdata->constval[i]);
255 consdata->maxrhsentry = max;
275 SCIP_CONSDATA* consdata;
276 SCIP_Real* eigenvalues = NULL;
277 SCIP_Real* matrix = NULL;
278 SCIP_Real* fullmatrix = NULL;
279 SCIP_Real* fullconstmatrix = NULL;
280 SCIP_Real* eigenvector = NULL;
281 SCIP_Real* output_vector = NULL;
285 assert( cons != NULL );
286 assert( lhs != NULL );
290 consdata = SCIPconsGetData(cons);
291 assert( consdata != NULL );
293 blocksize = consdata->blocksize;
295 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvalues, blocksize) );
296 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, (blocksize * (blocksize+1))/2 ) );
297 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize ) );
298 SCIP_CALL( SCIPallocBufferArray(scip, &fullconstmatrix, blocksize * blocksize) );
299 SCIP_CALL( SCIPallocBufferArray(scip, &eigenvector, blocksize) );
300 SCIP_CALL( SCIPallocBufferArray(scip, &output_vector, blocksize) );
316 for (j = 0; j < blocksize; ++j)
317 *lhs += eigenvector[j] * output_vector[j];
320 for (j = 0; j < consdata->nvars; ++j)
325 SCIPfreeBufferArray(scip, &output_vector);
326 SCIPfreeBufferArray(scip, &eigenvector);
327 SCIPfreeBufferArray(scip, &fullconstmatrix);
328 SCIPfreeBufferArray(scip, &fullmatrix);
329 SCIPfreeBufferArray(scip, &matrix);
330 SCIPfreeBufferArray(scip, &eigenvalues);
340 SCIP_Bool checkintegrality,
341 SCIP_Bool checklprows,
342 SCIP_Bool printreason,
346 SCIP_CONSDATA* consdata;
349 SCIP_Real eigenvalue;
350 SCIP_Real* matrix = NULL;
351 SCIP_Real* fullmatrix = NULL;
353 assert( scip != NULL );
354 assert( cons != NULL );
355 assert( result != NULL );
356 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)),
"SDP") == 0);
358 consdata = SCIPconsGetData(cons);
359 assert( consdata != NULL );
360 blocksize = consdata->blocksize;
362 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, (blocksize * (blocksize+1)) / 2) );
363 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, blocksize * blocksize) );
371 check_value = (-eigenvalue) / (1.0 + consdata->maxrhsentry);
373 check_value = -eigenvalue;
376 if ( SCIPisFeasLE(scip, check_value, 0.0) )
377 *result = SCIP_FEASIBLE;
380 *result = SCIP_INFEASIBLE;
384 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
385 SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
386 SCIPinfoMessage(scip, NULL,
"non psd matrix (eigenvalue %f, dimacs error norm = %f).\n", eigenvalue, check_value);
391 SCIPfreeBufferArray(scip, &fullmatrix);
392 SCIPfreeBufferArray(scip, &matrix);
401 SCIP_CONSHDLR* conshdlr,
407 SCIP_CONSDATA* consdata;
408 SCIP_CONSHDLRDATA* conshdlrdata;
410 SCIP_Real* coeff = NULL;
422 assert( cons != NULL );
424 consdata = SCIPconsGetData(cons);
425 assert( consdata != NULL );
427 nvars = consdata->nvars;
428 SCIP_CALL( SCIPallocBufferArray(scip, &coeff, nvars ) );
432 SCIP_CALL( SCIPallocBufferArray(scip, &cols, nvars ) );
433 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars ) );
436 for (j = 0; j < nvars; ++j)
438 if ( SCIPisZero(scip, coeff[j]) )
441 cols[len] = SCIPvarGetCol(SCIPvarGetProbvar(consdata->vars[j]));
442 vals[len] = coeff[j];
446 conshdlrdata = SCIPconshdlrGetData(conshdlr);
447 assert( conshdlrdata != NULL );
449 SCIP_CALL( SCIPallocBufferArray(scip, &cutname, 255) );
451 snprintfreturn = SCIPsnprintf(cutname, 255,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
452 assert( snprintfreturn < 256 );
454 SCIPsnprintf(cutname, 255,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
456 SCIP_CALL( SCIPcreateRowCons(scip, &row, conshdlr, cutname , len, cols, vals, lhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
458 if ( SCIPisCutEfficacious(scip, sol, row) )
460 #ifdef SCIP_MORE_DEBUG
461 SCIPinfoMessage(scip, NULL,
"Added cut %s: ", cutname);
462 SCIPinfoMessage(scip, NULL,
"%f <= ", lhs);
463 for (j = 0; j < len; j++)
464 SCIPinfoMessage(scip, NULL,
"+ (%f)*%s", vals[j], SCIPvarGetName(SCIPcolGetVar(cols[j])));
465 SCIPinfoMessage(scip, NULL,
"\n");
468 SCIP_Bool infeasible;
469 SCIP_CALL( SCIPaddCut(scip, sol, row, FALSE, &infeasible) );
471 *result = SCIP_CUTOFF;
473 *result = SCIP_SEPARATED;
474 SCIP_CALL( SCIPresetConsAge(scip, cons) );
477 SCIP_CALL( SCIPreleaseRow(scip, &row) );
478 SCIPfreeBufferArray(scip, &cutname);
480 SCIPfreeBufferArray(scip, &vals);
481 SCIPfreeBufferArray(scip, &cols);
482 SCIPfreeBufferArray(scip, &coeff);
499 SCIP_CONSDATA* consdata;
511 SCIP_Real* cons_array;
512 SCIP_Real* lhs_array;
514 for (c = 0; c < nconss; ++c)
516 SCIP_CONSHDLR* conshdlr;
518 const char* conshdlrName;
521 conshdlr = SCIPconsGetHdlr(conss[c]);
522 assert( conshdlr != NULL );
524 conshdlrName = SCIPconshdlrGetName(conshdlr);
525 assert( strcmp(conshdlrName,
"SDP") == 0);
528 consdata = SCIPconsGetData(conss[c]);
529 assert( consdata != NULL );
531 blocksize = consdata->blocksize;
532 nvars = consdata->nvars;
533 rhs = SCIPinfinity(scip);
535 SCIP_CALL( SCIPallocBufferArray(scip, &matrix, (blocksize * (blocksize + 1)) / 2) );
538 SCIP_CALL( SCIPallocBufferArray(scip, &cons_array, blocksize * nvars) );
539 SCIP_CALL( SCIPallocBufferArray(scip, &lhs_array, blocksize) );
542 for (k = 0; k < blocksize; ++k)
546 for (j = 0; j < nvars; ++j)
548 for (k = 0; k < blocksize; ++k)
551 cons_array[k * nvars + j] = 0.0;
555 for (i = 0; i < consdata->nvarnonz[j]; i++)
557 if ( consdata->col[j][i] == consdata->row[j][i] )
558 cons_array[consdata->col[j][i] * nvars + j] = consdata->val[j][i];
562 SCIP_CALL( SCIPallocBufferArray(scip, &cutname, 255));
565 for (k = 0; k < blocksize; ++k)
568 SCIP_CONSHDLRDATA* conshdlrdata;
570 conshdlrdata = SCIPconshdlrGetData(conshdlr);
572 snprintfreturn = SCIPsnprintf(cutname, 255,
"diag_ge_zero_%d", ++(conshdlrdata->ndiaggezerocuts));
573 assert( snprintfreturn < 256 );
575 SCIPsnprintf(cutname, 255,
"diag_ge_zero_%d", ++(conshdlrdata->ndiaggezerocuts));
578 #ifdef SCIP_MORE_DEBUG
579 SCIPinfoMessage(scip, NULL,
"Added lp-constraint %s: ", cutname);
580 SCIPinfoMessage(scip, NULL,
"%f <= ", lhs_array[k]);
581 for (i = 0; i < consdata->nvars; i++)
583 if ( ! SCIPisZero(scip, cons_array[k * consdata->nvars + i]) )
584 SCIPinfoMessage(scip, NULL,
"+ (%f)*%s", cons_array[k * consdata->nvars + i], SCIPvarGetName(consdata->vars[i]));
586 SCIPinfoMessage(scip, NULL,
"\n");
589 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, cutname, consdata->nvars, consdata->vars, cons_array + k * consdata->nvars, lhs_array[k], rhs,
590 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
592 SCIP_CALL( SCIPaddCons(scip, cons) );
593 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
597 SCIPfreeBufferArray(scip, &cutname);
598 SCIPfreeBufferArray(scip, &lhs_array);
599 SCIPfreeBufferArray(scip, &cons_array);
600 SCIPfreeBufferArray(scip, &matrix);
616 SCIP_RETCODE diagDominant(
623 SCIP_Bool* nonzerorows;
630 SCIP_CONSHDLRDATA* conshdlrdata;
638 assert( scip != NULL );
639 assert( conss != NULL );
640 assert( nconss >= 0 );
641 assert( naddconss != NULL );
643 for (i = 0; i < nconss; ++i)
645 assert( conss[i] != NULL );
646 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[i])),
"SDP") == 0 );
648 SCIP_CONSDATA* consdata = SCIPconsGetData(conss[i]);
649 assert( consdata != NULL );
651 blocksize = consdata->blocksize;
652 nvars = consdata->nvars;
653 SCIP_CALL( SCIPallocBufferArray(scip, &nonzerorows, blocksize) );
656 for (j = 0; j < blocksize; j++)
657 nonzerorows[j] = FALSE;
660 for (j = 0; j < consdata->constnnonz; j++)
662 if ( consdata->constcol[j] != consdata->constrow[j] )
664 assert( ! SCIPisEQ(scip, consdata->constval[j], 0.0) );
665 nonzerorows[consdata->constcol[j]] = TRUE;
666 nonzerorows[consdata->constrow[j]] = TRUE;
672 SCIP_CALL( SCIPallocBufferArray(scip, &diagvars, blocksize) );
673 SCIP_CALL( SCIPallocBufferArray(scip, &ndiagvars, blocksize) );
674 for (j = 0; j < blocksize; ++j)
677 if ( nonzerorows[j] )
679 SCIP_CALL( SCIPallocBufferArray(scip, &(diagvars[j]), nvars) );
684 for (var = 0; var < nvars; var++)
686 for (j = 0; j < consdata->nvarnonz[var]; j++)
688 if ( consdata->col[var][j] == consdata->row[var][j] && nonzerorows[consdata->row[var][j]])
690 assert( ! SCIPisEQ(scip, consdata->val[var][j], 0.0) );
691 diagvars[consdata->col[var][j]][ndiagvars[consdata->col[var][j]]] = var;
692 ndiagvars[consdata->col[var][j]]++;
699 SCIP_CALL( SCIPallocBufferArray(scip, &cutname, 255));
701 for (j = 0; j < blocksize; ++j)
703 if ( nonzerorows[j] )
705 SCIP_CALL( SCIPallocBufferArray(scip, &vals, ndiagvars[j]) );
706 SCIP_CALL( SCIPallocBufferArray(scip, &vars, ndiagvars[j]) );
709 for (var = 0; var < ndiagvars[j]; ++var)
711 vars[var] = consdata->vars[diagvars[j][var]];
715 conshdlrdata = SCIPconshdlrGetData(SCIPconsGetHdlr(conss[i]));
717 snprintfreturn = SCIPsnprintf(cutname, 255,
"diag_dom_%d", ++(conshdlrdata->ndiagdomcuts));
718 assert( snprintfreturn < 256 );
720 SCIPsnprintf(cutname, 255,
"diag_dom_%d", ++(conshdlrdata->ndiagdomcuts));
723 #ifdef SCIP_MORE_DEBUG
724 SCIPinfoMessage(scip, NULL,
"Added lp-constraint %s: ", cutname);
725 SCIPinfoMessage(scip, NULL,
"1 <= ");
726 for (i = 0; i < ndiagvars[j]; i++)
727 SCIPinfoMessage(scip, NULL,
"+ (%f)*%s", vals[i], SCIPvarGetName(vars[i]));
728 SCIPinfoMessage(scip, NULL,
"\n");
732 SCIP_CALL(SCIPcreateConsLinear(scip, &cons, cutname , ndiagvars[j], vars, vals, 1.0, SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE));
733 SCIP_CALL(SCIPaddCons(scip, cons));
734 SCIP_CALL(SCIPreleaseCons(scip, &cons));
737 SCIPfreeBufferArray(scip, &vars);
738 SCIPfreeBufferArray(scip, &vals);
739 SCIPfreeBufferArray(scip, &diagvars[j]);
743 SCIPfreeBufferArray(scip, &cutname);
744 SCIPfreeBufferArray(scip, &ndiagvars);
745 SCIPfreeBufferArray(scip, &diagvars);
746 SCIPfreeBufferArray(scip, &nonzerorows);
766 SCIP_CONSHDLRDATA* conshdlrdata;
777 SCIP_CONSDATA* consdata;
780 const char* hdlrName;
783 *result = SCIP_SUCCESS;
785 for (i = 0; i < nconss; ++i)
787 hdlr = SCIPconsGetHdlr(conss[i]);
788 assert(hdlr != NULL);
791 hdlrName = SCIPconshdlrGetName(hdlr);
792 assert( strcmp(hdlrName,
"SDP") == 0);
795 consdata = SCIPconsGetData(conss[i]);
796 assert( consdata != NULL );
799 if ( consdata->blocksize == 1 )
801 nvars = consdata->nvars;
802 nnonz = consdata->nnonz;
803 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
804 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nnonz) );
809 for (var = 0; var < nvars; var++)
811 assert( consdata->nvarnonz[var] <= 1 );
813 for (j = 0; j < consdata->nvarnonz[var]; j++)
815 assert( consdata->col[var][j] == 0 && consdata->row[var][j] == 0 );
816 coeffs[count] = consdata->val[var][j];
817 vars[count] = consdata->vars[var];
823 assert( consdata->constnnonz <= 1 );
825 rhs = (consdata->constnnonz == 1) ? consdata->constval[0] : 0.0;
831 conshdlrdata = SCIPconshdlrGetData(hdlr);
832 SCIP_CALL( SCIPallocBufferArray(scip, &cutname, 255) );
834 snprintfreturn = SCIPsnprintf(cutname, 255,
"1x1block_%d", ++(conshdlrdata->n1x1blocks));
835 assert( snprintfreturn < 256 );
837 SCIPsnprintf(cutname, 255,
"1x1block_%d", ++(conshdlrdata->n1x1blocks));
840 #ifdef SCIP_MORE_DEBUG
841 SCIPinfoMessage(scip, NULL,
"Added lp-constraint %s: ", cutname);
842 for (i = 0; i < consdata->nvars; i++)
843 SCIPinfoMessage(scip, NULL,
"+ (%f)*%s", coeffs[i], SCIPvarGetName(vars[i]));
844 SCIPinfoMessage(scip, NULL,
" <= %f \n", rhs);
847 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, cutname, consdata->nvars, vars, coeffs, rhs, SCIPinfinity(scip),
848 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
850 SCIP_CALL( SCIPaddCons(scip, cons) );
851 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
853 SCIPfreeBufferArray(scip, &cutname);
861 if ( coeffs[0] > 0.0 )
864 if ( SCIPisFeasGT(scip, rhs / coeffs[0], SCIPvarGetLbLocal(vars[0])) )
867 if( SCIPisFeasGT(scip, rhs / coeffs[0], SCIPvarGetUbLocal(vars[0])) )
869 SCIPdebugMessage(
"Problem found infeasible during presolving, 1x1-SDP-constraint %s caused change"
870 "of lower bound for variable %s from %f to %f, which is bigger than upper bound of %f\n",
871 SCIPconsGetName(conss[i]), SCIPvarGetName(vars[0]), SCIPvarGetLbLocal(vars[0]), rhs / coeffs[0],
872 SCIPvarGetUbLocal(vars[0]));
874 *result = SCIP_CUTOFF;
876 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
879 SCIPfreeBufferArray(scip, &coeffs);
880 SCIPfreeBufferArray(scip, &vars);
885 SCIPdebugMessage(
"Changing lower bound of variable %s from %f to %f because of 1x1-SDP-constraint %s!\n",
886 SCIPvarGetName(vars[0]), SCIPvarGetLbLocal(vars[0]), rhs / coeffs[0], SCIPconsGetName(conss[i]));
887 SCIP_CALL( SCIPchgVarLb(scip, vars[0], rhs / coeffs[0]) );
891 SCIPdebugMessage(
"Deleting 1x1-SDP-constraint %s, new lower bound %f for variable %s no improvement over old bound %f!\n",
892 SCIPconsGetName(conss[i]), rhs / coeffs[0], SCIPvarGetName(vars[0]), SCIPvarGetLbLocal(vars[0]));
895 else if ( coeffs[0] < 0.0 )
898 if (SCIPisFeasLT(scip, rhs / coeffs[0], SCIPvarGetUbLocal(vars[0])))
901 if( SCIPisFeasLT(scip, rhs / coeffs[0], SCIPvarGetLbLocal(vars[0])) )
903 SCIPdebugMessage(
"Problem found infeasible during presolving, 1x1-SDP-constraint %s caused change"
904 "of upper bound for variable %s from %f to %f, which is less than lower bound of %f\n",
905 SCIPconsGetName(conss[i]), SCIPvarGetName(vars[0]), SCIPvarGetUbLocal(vars[0]), rhs / coeffs[0],
906 SCIPvarGetLbLocal(vars[0]));
908 *result = SCIP_CUTOFF;
910 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
913 SCIPfreeBufferArray(scip, &coeffs);
914 SCIPfreeBufferArray(scip, &vars);
919 SCIPdebugMessage(
"Changing upper bound of variable %s from %f to %f because of 1x1-SDP-constraint %s!\n",
920 SCIPvarGetName(vars[0]), SCIPvarGetUbLocal(vars[0]), -rhs / coeffs[0], SCIPconsGetName(conss[i]));
921 SCIP_CALL( SCIPchgVarUb(scip, vars[0], rhs / coeffs[0]) );
925 SCIPdebugMessage(
"Deleting 1x1-SDP-constraint %s, new upper bound %f for variable %s no improvement over old bound %f!\n",
926 SCIPconsGetName(conss[i]), rhs / coeffs[0], SCIPvarGetName(vars[0]), SCIPvarGetUbLocal(vars[0]));
931 SCIPdebugMessage(
"Detected 1x1 SDP-block without any nonzero coefficients \n");
932 if ( SCIPisFeasGT(scip, rhs, 0.0) )
934 SCIPdebugMessage(
"Detected infeasibility in 1x1 SDP-block without any nonzero coefficients but with strictly positive rhs\n");
935 *result = SCIP_CUTOFF;
937 SCIP_CALL( SCIPdelCons(scip, conss[i]) );
940 SCIPfreeBufferArray(scip, &coeffs);
941 SCIPfreeBufferArray(scip, &vars);
949 SCIP_CALL(SCIPdelCons(scip, conss[i]));
952 SCIPfreeBufferArray(scip, &coeffs);
953 SCIPfreeBufferArray(scip, &vars);
977 SCIP_CONSDATA* consdata;
980 int aggrtargetlength;
985 assert( scip != NULL );
986 assert( cons != NULL );
987 assert( scalars != NULL );
988 assert( naggrvars > 0 );
989 assert( savedcol != NULL );
990 assert( savedrow != NULL );
991 assert( savedval != NULL );
992 assert( nfixednonz != NULL );
994 consdata = SCIPconsGetData(cons);
995 assert( consdata != NULL );
997 SCIP_CALL( SCIPgetRealParam(scip,
"numerics/feastol", &feastol) );
1000 startind = *nfixednonz;
1002 if ( SCIPisEQ(scip, constant, 0.0) )
1008 for (i = 0; i < consdata->nvarnonz[*v]; i++)
1010 savedcol[*nfixednonz] = consdata->col[*v][i];
1011 savedrow[*nfixednonz] = consdata->row[*v][i];
1012 savedval[*nfixednonz] = consdata->val[*v][i];
1018 for (i = 0; i < consdata->nvarnonz[*v]; i++)
1020 savedcol[*nfixednonz] = consdata->col[*v][i];
1021 savedrow[*nfixednonz] = consdata->row[*v][i];
1022 savedval[*nfixednonz] = consdata->val[*v][i] * constant;
1026 assert( *nfixednonz - startind == consdata->nvarnonz[*v] );
1034 SCIP_CALL( SCIPreleaseVar(scip, &consdata->vars[*v]) );
1035 consdata->col[*v] = consdata->col[consdata->nvars - 1];
1036 consdata->row[*v] = consdata->row[consdata->nvars - 1];
1037 consdata->val[*v] = consdata->val[consdata->nvars - 1];
1038 consdata->nvarnonz[*v] = consdata->nvarnonz[consdata->nvars - 1];
1039 consdata->vars[*v] = consdata->vars[consdata->nvars - 1];
1040 (consdata->nvars)--;
1044 for (aggrind = 0; aggrind < naggrvars; aggrind++)
1048 for (i = 0; i < consdata->nvars; i++)
1050 if ( consdata->vars[i] == aggrvars[aggrind] )
1057 if ( aggrconsind > -1 )
1062 aggrtargetlength = consdata->nvarnonz[aggrconsind] + *nfixednonz - startind;
1063 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->row[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
1064 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->col[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
1065 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->val[aggrconsind]), consdata->nvarnonz[aggrconsind], aggrtargetlength) );
1067 if ( SCIPisEQ(scip, constant, 0.0) )
1071 SCIP_CALL(
SCIPsdpVarfixerMergeArrays(SCIPblkmem(scip), feastol, savedrow + startind, savedcol + startind, savedval + startind,
1072 *nfixednonz - startind, TRUE, scalars[aggrind], consdata->row[aggrconsind], consdata->col[aggrconsind],
1073 consdata->val[aggrconsind], &(consdata->nvarnonz[aggrconsind]), aggrtargetlength) );
1079 SCIP_CALL(
SCIPsdpVarfixerMergeArrays(SCIPblkmem(scip), feastol, savedrow + startind, savedcol + startind, savedval + startind,
1080 *nfixednonz - startind, TRUE, scalars[aggrind] / constant, consdata->row[aggrconsind], consdata->col[aggrconsind],
1081 consdata->val[aggrconsind], &(consdata->nvarnonz[aggrconsind]), aggrtargetlength) );
1085 assert( consdata->nvarnonz[aggrconsind] <= aggrtargetlength );
1086 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->row[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
1087 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->col[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
1088 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->val[aggrconsind]), aggrtargetlength, consdata->nvarnonz[aggrconsind]) );
1094 SCIPdebugMessage(
"adding variable %s to SDP constraint %s because of (multi-)aggregation\n", SCIPvarGetName(aggrvars[aggrind]), SCIPconsGetName(cons));
1097 if ( consdata->nvars == *vararraylength )
1099 globalnvars = SCIPgetNVars(scip);
1102 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col, *vararraylength, globalnvars) );
1103 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row, *vararraylength, globalnvars) );
1104 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val, *vararraylength, globalnvars) );
1105 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nvarnonz, *vararraylength, globalnvars) );
1106 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, *vararraylength, globalnvars) );
1107 *vararraylength = globalnvars;
1111 SCIP_CALL( SCIPcaptureVar(scip, aggrvars[aggrind]) );
1112 consdata->vars[consdata->nvars] = aggrvars[aggrind];
1115 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->col[consdata->nvars]), savedcol + startind, *nfixednonz - startind) );
1116 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->row[consdata->nvars]), savedrow + startind, *nfixednonz - startind) );
1122 if ( SCIPisEQ(scip, scalars[aggrind], constant) || SCIPisEQ(scip, constant, 0.0) )
1124 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(consdata->val[consdata->nvars]), savedval + startind, *nfixednonz - startind) );
1125 consdata->nvarnonz[consdata->nvars] = *nfixednonz - startind;
1132 SCIP_CALL( SCIPgetRealParam(scip,
"numerics/epsilon", &epsilon) );
1134 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->val[consdata->nvars]), *nfixednonz - startind) );
1136 consdata->nvarnonz[consdata->nvars] = 0;
1138 for (i = 0; i < *nfixednonz - startind; i++)
1141 if ( (scalars[i] / constant) * savedval[startind + i] >= epsilon )
1143 consdata->val[consdata->nvars][consdata->nvarnonz[consdata->nvars]] = (scalars[i] / constant) * savedval[startind + i];
1144 consdata->nvarnonz[consdata->nvars]++;
1149 if ( consdata->nvarnonz[consdata->nvars] > 0 )
1156 if ( SCIPisEQ(scip, constant, 0.0) )
1157 *nfixednonz = startind;
1172 SCIP_CONSDATA* consdata;
1177 SCIP_Real* savedval;
1182 SCIP_VAR** aggrvars;
1199 assert( scip != NULL );
1200 assert( conss != NULL );
1201 assert( nconss >= 0 );
1203 SCIPdebugMessage(
"Calling fixAndAggrVars with aggregate = %u\n", aggregate);
1205 SCIP_CALL( SCIPgetRealParam(scip,
"numerics/feastol", &feastol) );
1207 for (c = 0; c < nconss; ++c)
1209 assert( conss[c] != NULL );
1210 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(conss[c])),
"SDP") == 0);
1212 consdata = SCIPconsGetData(conss[c]);
1213 assert( consdata != NULL );
1216 SCIP_CALL( SCIPallocBufferArray(scip, &savedcol, consdata->nnonz) );
1217 SCIP_CALL( SCIPallocBufferArray(scip, &savedrow, consdata->nnonz) );
1218 SCIP_CALL( SCIPallocBufferArray(scip, &savedval, consdata->nnonz) );
1223 vararraylength = consdata->nvars;
1224 globalnvars = SCIPgetNVars(scip);
1226 for (v = 0; v < consdata->nvars; v++)
1230 if ( SCIPvarIsBinary(consdata->vars[v]) && SCIPvarIsNegated(consdata->vars[v]) )
1233 var = SCIPvarGetNegationVar(consdata->vars[v]);
1236 var = consdata->vars[v];
1239 if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)))
1241 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) );
1243 SCIPdebugMessage(
"Globally fixing Variable %s to value %f !\n", SCIPvarGetName(var), SCIPvarGetLbGlobal(var));
1245 if ( ((! negated) && (! SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0))) || (negated && SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0)) )
1250 for (i = 0; i < consdata->nvarnonz[v]; i++)
1252 savedcol[nfixednonz] = consdata->col[v][i];
1253 savedrow[nfixednonz] = consdata->row[v][i];
1256 savedval[nfixednonz] = consdata->val[v][i] * SCIPvarGetLbGlobal(var);
1258 savedval[nfixednonz] = consdata->val[v][i];
1267 consdata->nnonz -= consdata->nvarnonz[v];
1270 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vars[v])) );
1271 consdata->col[v] = consdata->col[consdata->nvars - 1];
1272 consdata->row[v] = consdata->row[consdata->nvars - 1];
1273 consdata->val[v] = consdata->val[consdata->nvars - 1];
1274 consdata->nvarnonz[v] = consdata->nvarnonz[consdata->nvars - 1];
1275 consdata->vars[v] = consdata->vars[consdata->nvars - 1];
1279 else if ( (SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED ||
1280 SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR)
1283 SCIP_CALL( SCIPallocBufferArray(scip, &aggrvars, globalnvars) );
1284 SCIP_CALL( SCIPallocBufferArray(scip, &scalars, globalnvars) );
1289 aggrvars[0] = consdata->vars[v];
1297 aggrvars[0] = consdata->vars[v];
1304 SCIP_CALL( SCIPgetProbvarLinearSum(scip, aggrvars, scalars, &naggrvars, globalnvars, &constant, &requiredsize, TRUE) );
1305 assert( requiredsize <= globalnvars );
1310 if ( SCIPvarGetStatus(consdata->vars[v]) == SCIP_VARSTATUS_AGGREGATED )
1311 SCIPdebugMessage(
"aggregating variable %s to ", SCIPvarGetName(var));
1313 SCIPdebugMessage(
"multiaggregating variable %s to ", SCIPvarGetName(var));
1314 for (i = 0; i < naggrvars; i++)
1315 printf(
"+ (%f2) * %s ", scalars[i], SCIPvarGetName(aggrvars[i]));
1316 printf(
"+ (%f2) \n", constant);
1321 SCIP_CALL(
multiaggrVar(scip, conss[c], &v, aggrvars, scalars, naggrvars, constant, savedcol, savedrow, savedval, &nfixednonz, &vararraylength) );
1323 SCIPfreeBufferArray(scip, &aggrvars);
1324 SCIPfreeBufferArray(scip, &scalars);
1326 else if ( negated && (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN)
1331 SCIPdebugMessage(
"Changing variable %s to negation of variable %s !\n", SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(var));
1335 SCIP_CALL(
multiaggrVar(scip, conss[c], &v, &var, &scalar, 1, 1.0, savedcol, savedrow, savedval, &nfixednonz, &vararraylength) );
1340 assert( consdata->nvars <= vararraylength );
1341 if ( consdata->nvars < vararraylength )
1343 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->col, vararraylength, consdata->nvars) );
1344 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->row, vararraylength, consdata->nvars) );
1345 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->val, vararraylength, consdata->nvars) );
1346 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->nvarnonz, vararraylength, consdata->nvars) );
1347 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, vararraylength, consdata->nvars) );
1351 arraylength = consdata->constnnonz + nfixednonz;
1352 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constcol), consdata->constnnonz, arraylength) );
1353 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constrow), consdata->constnnonz, arraylength) );
1354 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constval), consdata->constnnonz, arraylength) );
1357 SCIP_CALL(
SCIPsdpVarfixerMergeArrays(SCIPblkmem(scip), feastol, savedrow, savedcol, savedval, nfixednonz, FALSE, -1.0, consdata->constrow,
1358 consdata->constcol, consdata->constval, &(consdata->constnnonz), arraylength) );
1360 assert( consdata->constnnonz <= arraylength );
1363 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constcol), arraylength, consdata->constnnonz) );
1364 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constrow), arraylength, consdata->constnnonz) );
1365 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->constval), arraylength, consdata->constnnonz) );
1368 SCIPfreeBufferArray(scip, &savedval);
1369 SCIPfreeBufferArray(scip, &savedrow);
1370 SCIPfreeBufferArray(scip, &savedcol);
1373 consdata->nnonz = 0;
1374 for (v = 0; v < consdata->nvars; v++)
1375 consdata->nnonz += consdata->nvarnonz[v];
1385 SCIP_CONSHDLRDATA* conshdlrdata;
1387 assert( conshdlr != NULL );
1389 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1390 assert( conshdlrdata != NULL );
1392 conshdlrdata->neigveccuts = 0;
1393 conshdlrdata->ndiaggezerocuts = 0;
1394 conshdlrdata->ndiagdomcuts = 0;
1395 conshdlrdata->n1x1blocks = 0;
1405 SCIP_CONSDATA* consdata;
1409 SCIP_Real eigenvalue;
1411 consdata = SCIPconsGetData(cons);
1412 assert( consdata != NULL );
1413 blocksize = consdata->blocksize;
1414 nvars = consdata->nvars;
1416 SCIP_CALL( SCIPallocBufferArray(scip, &Aj, blocksize * blocksize) );
1418 for (var = 0; var < nvars; var++)
1424 if ( SCIPisNegative(scip, eigenvalue) )
1428 SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[var], nlocksneg, nlockspos) );
1432 if ( SCIPisPositive(scip, eigenvalue) )
1436 SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[var], nlockspos, nlocksneg) );
1442 if ( SCIPisPositive(scip, eigenvalue) )
1446 SCIP_CALL( SCIPaddVarLocks(scip, consdata->vars[var], nlockspos, nlocksneg) );
1451 SCIPfreeBufferArray(scip, &Aj);
1460 assert( scip != NULL );
1461 assert( conss != NULL );
1472 assert( result != 0 );
1476 SCIP_CALL(
diagGEzero(scip, conss, nconss, naddconss) );
1483 SCIP_CALL( diagDominant(scip, conss, nconss, naddconss) );
1494 SCIP_CONSDATA* sourcedata;
1495 SCIP_CONSDATA* targetdata;
1498 sourcedata = SCIPconsGetData(sourcecons);
1499 assert( sourcedata != NULL );
1501 SCIP_CALL( SCIPallocBlockMemory(scip, &targetdata) );
1504 targetdata->nvars = sourcedata->nvars;
1505 targetdata->nnonz = sourcedata->nnonz;
1506 targetdata->blocksize = sourcedata->blocksize;
1508 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->nvarnonz), sourcedata->nvarnonz, sourcedata->nvars) );
1511 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->col), sourcedata->nvars) );
1512 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->row), sourcedata->nvars) );
1513 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->val), sourcedata->nvars) );
1515 for (i = 0; i < sourcedata->nvars; i++)
1517 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->col[i]), sourcedata->col[i], sourcedata->nvarnonz[i]) );
1518 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->row[i]), sourcedata->row[i], sourcedata->nvarnonz[i]) );
1519 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->val[i]), sourcedata->val[i], sourcedata->nvarnonz[i]) );
1521 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(targetdata->vars), sourcedata->nvars));
1524 for (i = 0; i < sourcedata->nvars; i++)
1526 targetdata->vars[i] = SCIPvarGetTransVar(sourcedata->vars[i]);
1527 SCIP_CALL( SCIPcaptureVar(scip, targetdata->vars[i]) );
1531 targetdata->constnnonz = sourcedata->constnnonz;
1533 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constcol), sourcedata->constcol, sourcedata->constnnonz));
1534 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constrow), sourcedata->constrow, sourcedata->constnnonz));
1535 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(targetdata->constval), sourcedata->constval, sourcedata->constnnonz));
1538 targetdata->maxrhsentry = sourcedata->maxrhsentry;
1541 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1542 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1543 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1544 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons),
1545 SCIPconsIsStickingAtNode(sourcecons)) );
1556 assert( scip != NULL );
1557 assert( result != NULL );
1559 *result = SCIP_FEASIBLE;
1561 for (i = 0; i < nconss; ++i)
1563 SCIP_CALL(
SCIPconsSdpCheckSdpCons(scip, conss[i], sol, checkintegrality, checklprows, printreason, result) );
1564 if ( *result == SCIP_INFEASIBLE )
1580 assert( scip != NULL );
1581 assert( result != NULL );
1582 assert( conss != NULL );
1584 *result = SCIP_DIDNOTRUN;
1586 if ( objinfeasible )
1588 SCIPdebugMessage(
"-> pseudo solution is objective infeasible, return.\n");
1592 for (i = 0; i < nconss; ++i)
1596 if (*result == SCIP_INFEASIBLE)
1599 SCIPdebugMessage(
"-> pseudo solution infeasible for SDP-constraint %s, return.\n", SCIPconsGetName(conss[i]));
1604 SCIPdebugMessage(
"-> pseudo solution feasible for all SDP-constraints.\n");
1617 SCIP_CONSDATA* consdata;
1618 SCIP_CONSHDLRDATA* conshdlrdata;
1619 SCIP_Bool all_feasible = TRUE;
1620 SCIP_Bool separated = FALSE;
1629 SCIP_Bool infeasible;
1638 assert( result != NULL );
1639 *result = SCIP_FEASIBLE;
1641 for (i = 0; i < nconss; ++i)
1643 consdata = SCIPconsGetData(conss[i]);
1645 if ( *result == SCIP_FEASIBLE )
1648 all_feasible = FALSE;
1650 nvars = consdata->nvars;
1654 SCIP_CALL( SCIPallocBufferArray(scip, &coeff, nvars) );
1657 rhs = SCIPinfinity(scip);
1658 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1660 SCIP_CALL( SCIPallocBufferArray(scip, &cutname, 255) );
1662 snprintfreturn = SCIPsnprintf(cutname, 255,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
1663 assert( snprintfreturn < 256 );
1665 SCIPsnprintf(cutname, 255,
"sepa_eig_sdp_%d", ++(conshdlrdata->neigveccuts));
1668 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, cutname , lhs, rhs, FALSE, FALSE, TRUE) );
1669 SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
1671 for (j = 0; j < nvars; ++j)
1673 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], coeff[j]) );
1676 SCIP_CALL( SCIPflushRowExtensions(scip, row) );
1678 #ifdef SCIP_MORE_DEBUG
1679 SCIPinfoMessage(scip, NULL,
"Added cut %s: ", cutname);
1680 SCIPinfoMessage(scip, NULL,
"%f <= ", lhs);
1681 for (j = 0; j < nvars; j++)
1682 SCIPinfoMessage(scip, NULL,
"+ (%f)*%s", coeff[j], SCIPvarGetName(consdata->vars[j]));
1683 SCIPinfoMessage(scip, NULL,
"\n");
1686 SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, &infeasible) );
1689 *result = SCIP_CUTOFF;
1692 SCIP_CALL( SCIPaddPoolCut(scip, row) );
1694 SCIP_CALL( SCIPresetConsAge(scip, conss[i]) );
1695 *result = SCIP_SEPARATED;
1698 SCIP_CALL( SCIPreleaseRow(scip, &row) );
1699 SCIPfreeBufferArray(scip, &cutname);
1700 SCIPfreeBufferArray(scip, &coeff);
1706 *result = SCIP_SEPARATED;
1708 vars = SCIPgetVars(scip);
1710 for (i = 0; i < SCIPgetNVars(scip); ++i)
1712 if ( !SCIPisRelEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) && SCIPvarIsIntegral(vars[i]))
1714 SCIP_CALL( SCIPaddExternBranchCand(scip, vars[i], 10000.0, SCIP_INVALID) );
1729 *result = SCIP_DIDNOTFIND;
1730 for (i = 0; i < nusefulconss; ++i)
1732 SCIP_CALL(
separateSol(scip, conshdlr, conss[i], sol, result) );
1744 *result = SCIP_DIDNOTFIND;
1745 for (i = 0; i < nusefulconss; ++i)
1747 SCIP_CALL(
separateSol(scip, conshdlr, conss[i], NULL, result) );
1759 assert( cons != NULL );
1760 assert( consdata != NULL );
1762 SCIPdebugMessage(
"deleting %s \n", SCIPconsGetName(cons));
1764 for (i = 0; i < (*consdata)->nvars; i++)
1766 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->val[i], (*consdata)->nvarnonz[i]);
1767 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->row[i], (*consdata)->nvarnonz[i]);
1768 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->col[i], (*consdata)->nvarnonz[i]);
1772 for (i = 0; i < (*consdata)->nvars; i++)
1774 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[i])) );
1777 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->nvars);
1778 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constval, (*consdata)->constnnonz);
1779 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constrow, (*consdata)->constnnonz);
1780 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->constcol, (*consdata)->constnnonz);
1781 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->val, (*consdata)->nvars);
1782 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->row, (*consdata)->nvars);
1783 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->col, (*consdata)->nvars);
1784 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->nvarnonz, (*consdata)->nvars);
1785 SCIPfreeBlockMemory(scip, consdata);
1794 SCIP_CONSHDLRDATA* conshdlrdata;
1796 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1797 assert( conshdlrdata != NULL );
1799 SCIPfreeMemory(scip, &conshdlrdata);
1800 SCIPconshdlrSetData(conshdlr, NULL);
1809 assert(scip != NULL);
1810 assert(conshdlr != NULL);
1811 assert(strcmp(SCIPconshdlrGetName(conshdlr),
CONSHDLR_NAME) == 0);
1824 SCIP_CONSDATA* sourcedata;
1826 SCIP_VAR** targetvars;
1830 assert( scip != NULL );
1831 assert( sourcescip != NULL );
1832 assert( sourcecons != NULL );
1833 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)),
CONSHDLR_NAME) == 0 );
1835 SCIPdebugMessage(
"Copying SDP constraint %s\n", SCIPconsGetName(sourcecons));
1841 if ( SCIPgetStage(sourcescip) <= SCIP_STAGE_EXITPRESOLVE )
1847 sourcedata = SCIPconsGetData(sourcecons);
1848 assert( sourcedata != NULL );
1850 SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, sourcedata->nvars) );
1853 for (i = 0; i < sourcedata->nvars; i++)
1855 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->vars[i], &var, varmap, consmap, global, &success) );
1858 targetvars[i] = var;
1859 SCIP_CALL( SCIPcaptureVar(scip, targetvars[i]) );
1866 SCIP_CALL(
SCIPcreateConsSdp( scip, cons, name, sourcedata->nvars, sourcedata->nnonz, sourcedata->blocksize, sourcedata->nvarnonz,
1867 sourcedata->col, sourcedata->row, sourcedata->val, targetvars, sourcedata->constnnonz,
1868 sourcedata->constcol, sourcedata->constrow, sourcedata->constval) );
1870 SCIPfreeBufferArray(scip, &targetvars);
1879 SCIP_CONSDATA* consdata;
1880 SCIP_Real* fullmatrix;
1885 assert( cons != NULL );
1887 consdata = SCIPconsGetData(cons);
1889 SCIP_CALL( SCIPallocBufferArray(scip, &fullmatrix, consdata->blocksize * consdata->blocksize) );
1892 for (v = 0; v < consdata->nvars; v++)
1897 for (i = 0; i < consdata->blocksize; i++)
1899 for (j = 0; j < consdata->blocksize; j++)
1900 fullmatrix[i * consdata->blocksize + j] = 0.0;
1904 for (i = 0; i < consdata->nvarnonz[v]; i++)
1906 fullmatrix[consdata->row[v][i] * consdata->blocksize + consdata->col[v][i]] = consdata->val[v][i];
1907 fullmatrix[consdata->col[v][i] * consdata->blocksize + consdata->row[v][i]] = consdata->val[v][i];
1911 SCIPinfoMessage(scip, file,
"+\n");
1912 for (i = 0; i < consdata->blocksize; i++)
1914 SCIPinfoMessage(scip, file,
"( ");
1915 for (j = 0; j < consdata->blocksize; j++)
1916 SCIPinfoMessage(scip, file,
"%f ", fullmatrix[i * consdata->blocksize + j]);
1917 SCIPinfoMessage(scip, file,
")\n");
1919 SCIPinfoMessage(scip, file,
"* %s\n", SCIPvarGetName(consdata->vars[v]));
1927 for (i = 0; i < consdata->blocksize; i++)
1929 for (j = 0; j < consdata->blocksize; j++)
1930 fullmatrix[i * consdata->blocksize + j] = 0.0;
1934 for (i = 0; i < consdata->constnnonz; i++)
1936 fullmatrix[consdata->constrow[i] * consdata->blocksize + consdata->constcol[i]] = consdata->constval[i];
1937 fullmatrix[consdata->constcol[i] * consdata->blocksize + consdata->constrow[i]] = consdata->constval[i];
1941 SCIPinfoMessage(scip, file,
"-\n");
1942 for (i = 0; i < consdata->blocksize; i++)
1944 SCIPinfoMessage(scip, file,
"( ");
1945 for (j = 0; j < consdata->blocksize; j++)
1946 SCIPinfoMessage(scip, file,
"%f ", fullmatrix[i * consdata->blocksize + j]);
1947 SCIPinfoMessage(scip, file,
")\n");
1949 SCIPinfoMessage(scip, file,
">=0\n");
1951 SCIPfreeBufferArray(scip, &fullmatrix);
1960 SCIP_CONSDATA* consdata;
1964 assert( scip != NULL );
1965 assert( cons != NULL );
1966 assert( vars != NULL );
1967 assert( success != NULL );
1968 assert( varssize >= 0 );
1970 consdata = SCIPconsGetData(cons);
1971 assert( consdata != NULL );
1973 nvars = consdata->nvars;
1975 if ( nvars > varssize )
1977 SCIPdebugMessage(
"consGetVarsIndicator called for array of size %d, needed size %d.\n", varssize, nvars);
1982 for (i = 0; i < nvars; i++)
1984 vars[i] = consdata->vars[i];
1995 SCIP_CONSDATA* consdata;
1997 assert( scip != NULL );
1998 assert( cons != NULL );
1999 assert( nvars != NULL );
2000 assert( success != NULL );
2002 consdata = SCIPconsGetData(cons);
2003 assert( consdata != NULL );
2005 *nvars = consdata->nvars;
2016 SCIP_CONSHDLR* conshdlr = NULL;
2017 SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2019 assert( scip != 0 );
2022 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
2027 consEnfolpSdp, consEnfopsSdp, consCheckSdp, consLockSdp, conshdlrdata) );
2029 assert( conshdlr != NULL );
2032 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSdp) );
2033 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSdp) );
2034 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySdp, consCopySdp) );
2035 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr,consInitpreSdp) );
2036 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreSdp) );
2038 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSdp, consSepasolSdp,
CONSHDLR_SEPAFREQ,
2040 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSdp) );
2041 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSdp) );
2042 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSdp) );
2043 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSdp) );
2074 SCIP_CONSDATA* consdata;
2078 assert( scip != NULL );
2079 assert( cons != NULL );
2080 assert( nvars != NULL );
2081 assert( nnonz != NULL );
2082 assert( blocksize != NULL );
2083 assert( arraylength != NULL );
2084 assert( nvarnonz != NULL );
2085 assert( col != NULL );
2086 assert( row != NULL );
2087 assert( val != NULL );
2088 assert( vars != NULL );
2089 assert( constnnonz != NULL );
2091 consdata = SCIPconsGetData(cons);
2092 name = SCIPconsGetName(cons);
2094 assert( consdata->constnnonz == 0 || ( constcol != NULL && constrow != NULL && constval != NULL ) );
2096 *nvars = consdata->nvars;
2097 *nnonz = consdata->nnonz;
2098 *blocksize = consdata->blocksize;
2100 for (i = 0; i < consdata->nvars; i++)
2101 vars[i] = consdata->vars[i];
2104 if ( *arraylength < consdata->nvars )
2106 SCIPdebugMessage(
"nvarnonz, col, row and val arrays were not long enough to store the information for cons %s, they need to be at least"
2107 "size %d, given was only length %d! \n", name, consdata->nvars, *arraylength);
2108 *arraylength = consdata->nvars;
2112 for (i = 0; i < consdata->nvars; i++)
2114 nvarnonz[i] = consdata->nvarnonz[i];
2116 col[i] = consdata->col[i];
2117 row[i] = consdata->row[i];
2118 val[i] = consdata->val[i];
2123 if ( consdata->constnnonz > 0 )
2125 if ( consdata->constnnonz > *constnnonz )
2127 SCIPdebugMessage(
"The constant nonzeros arrays were not long enough to store the information for cons %s, they need to be at least"
2128 "size %d, given was only length %d! \n", name, consdata->constnnonz, *constnnonz);
2132 for (i = 0; i < consdata->constnnonz; i++)
2134 constcol[i] = consdata->constcol[i];
2135 constrow[i] = consdata->constrow[i];
2136 constval[i] = consdata->constval[i];
2141 *constnnonz = consdata->constnnonz;
2157 SCIP_CONSDATA* consdata;
2159 assert( scip != NULL );
2160 assert( cons != NULL );
2162 consdata = SCIPconsGetData(cons);
2163 assert( consdata != NULL );
2165 if ( nnonz != NULL )
2166 *nnonz = consdata->nnonz;
2168 if ( constnnonz != NULL )
2169 *constnnonz = consdata->constnnonz;
2182 SCIP_CONSDATA* consdata;
2186 assert( scip != NULL );
2187 assert( cons != NULL );
2189 assert( Aj != NULL );
2191 consdata = SCIPconsGetData(cons);
2192 assert( consdata != NULL );
2193 blocksize = consdata->blocksize;
2195 assert( j < consdata->nvars );
2197 for (i = 0; i < blocksize * blocksize; i++)
2200 for (i = 0; i < consdata->nvarnonz[j]; i++)
2202 Aj[consdata->col[j][i] * blocksize + consdata->row[j][i]] = consdata->val[j][i];
2203 Aj[consdata->row[j][i] * blocksize + consdata->col[j][i]] = consdata->val[j][i];
2216 SCIP_CONSDATA* consdata;
2221 assert( scip != NULL );
2222 assert( cons != NULL );
2223 assert( mat != NULL );
2225 consdata = SCIPconsGetData(cons);
2226 blocksize = consdata->blocksize;
2228 for (i = 0; i < blocksize; i++)
2230 for (j = 0; j < blocksize; j++)
2231 mat[i * blocksize + j] = 0.0;
2234 for (i = 0; i < consdata->constnnonz; i++)
2236 mat[consdata->constcol[i] * blocksize + consdata->constrow[i]] = consdata->constval[i];
2237 mat[consdata->constrow[i] * blocksize + consdata->constcol[i]] = consdata->constval[i];
2250 SCIP_CONSDATA* consdata;
2254 assert( scip != NULL );
2255 assert( cons != NULL );
2256 assert( mat != NULL );
2258 consdata = SCIPconsGetData(cons);
2259 assert( consdata != NULL );
2261 blocksize = consdata->blocksize;
2264 for (i = 0; i < (blocksize * (blocksize + 1)) / 2; i++)
2267 for (i = 0; i < consdata->constnnonz; i++)
2268 mat[
compLowerTriangPos(consdata->constrow[i], consdata->constcol[i])] = consdata->constval[i];
2292 SCIP_CONSHDLR* conshdlr;
2293 SCIP_CONSDATA* consdata = NULL;
2297 assert( scip != NULL );
2298 assert( cons != NULL );
2299 assert( name != NULL );
2300 assert( nvars >= 0 );
2301 assert( nnonz >= 0 );
2302 assert( blocksize >= 0 );
2303 assert( constnnonz >= 0 );
2304 assert( nvars == 0 || vars != NULL );
2305 assert( nnonz == 0 || (nvarnonz != NULL && col != NULL && row != NULL && val != NULL ));
2306 assert( constnnonz == 0 || (constcol != NULL && constrow != NULL && constval != NULL ));
2308 conshdlr = SCIPfindConshdlr(scip,
"SDP");
2309 if ( conshdlr == NULL )
2311 SCIPerrorMessage(
"SDP constraint handler not found\n");
2312 return SCIP_PLUGINNOTFOUND;
2316 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
2317 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->nvarnonz, nvars) );
2318 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col, nvars) );
2319 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row, nvars) );
2320 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val, nvars) );
2321 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constcol, constnnonz) );
2322 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constrow, constnnonz) );
2323 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->constval, constnnonz) );
2324 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars));
2326 for (i = 0; i < nvars; i++)
2328 assert( nvarnonz[i] >= 0 );
2330 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->col[i], nvarnonz[i]));
2331 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->row[i], nvarnonz[i]));
2332 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->val[i], nvarnonz[i]));
2335 consdata->nvars = nvars;
2336 consdata->nnonz = nnonz;
2337 consdata->constnnonz = constnnonz;
2338 consdata->blocksize = blocksize;
2340 for (i = 0; i < nvars; i++)
2342 consdata->nvarnonz[i] = nvarnonz[i];
2344 for (j = 0; j < nvarnonz[i]; j++)
2346 assert( col[i][j] >= 0 );
2347 assert( col[i][j] < blocksize );
2348 assert( row[i][j] >= 0 );
2349 assert( row[i][j] < blocksize );
2351 consdata->col[i][j] = col[i][j];
2352 consdata->row[i][j] = row[i][j];
2353 consdata->val[i][j] = val[i][j];
2357 for (i = 0; i < constnnonz; i++)
2359 consdata->constcol[i] = constcol[i];
2360 consdata->constrow[i] = constrow[i];
2361 consdata->constval[i] = constval[i];
2364 for (i = 0; i < nvars; i++)
2366 consdata->vars[i] = vars[i];
2367 SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
2371 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
static SCIP_DECL_CONSTRANS(consTransSdp)
EXTERN SCIP_RETCODE SCIPlapackMatrixVectorMult(int nrows, int ncols, SCIP_Real *matrix, SCIP_Real *vector, SCIP_Real *result)
static SCIP_RETCODE separateSol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_RETCODE SCIPconsSdpGetFullAj(SCIP *scip, SCIP_CONS *cons, int j, SCIP_Real *Aj)
void SCIPsdpVarfixerSortRowCol(int *row, int *col, SCIP_Real *val, int length)
#define CONSHDLR_PRESOLTIMING
SCIP_RETCODE SCIPincludeConshdlrSdp(SCIP *scip)
static SCIP_RETCODE multiplyConstraintMatrix(SCIP_CONS *cons, int j, SCIP_Real *v, SCIP_Real *vAv)
#define CONSHDLR_NEEDSCONS
static SCIP_RETCODE diagGEzero(SCIP *scip, SCIP_CONS **conss, int nconss, int *naddconss)
static SCIP_DECL_CONSDELETE(consDeleteSdp)
#define CONSHDLR_SEPAFREQ
#define CONSHDLR_DELAYSEPA
static SCIP_RETCODE computeSdpMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *y, SCIP_Real *matrix)
#define CONSHDLR_EAGERFREQ
static SCIP_RETCODE move_1x1_blocks_to_lp(SCIP *scip, SCIP_CONS **conss, int nconss, int *naddconss, int *ndelconss, SCIP_RESULT *result)
SCIP_RETCODE SCIPconsSdpGetLowerTriangConstMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat)
static SCIP_DECL_CONSSEPALP(consSepalpSdp)
static SCIP_RETCODE setMaxRhsEntry(SCIP_CONS *cons)
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_DECL_CONSCHECK(consCheckSdp)
Constraint handler for SDP-constraints.
static SCIP_RETCODE expandSymMatrix(int size, SCIP_Real *symMat, SCIP_Real *fullMat)
class that maps SCIP variables to SDP indices (the SCIP variables are given SDP indices in the order ...
SCIP_RETCODE SCIPconsSdpGetFullConstMatrix(SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat)
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_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)
#define CONSHDLR_CHECKPRIORITY
SCIP_RETCODE SCIPsdpVarfixerMergeArrays(BMS_BLKMEM *blkmem, SCIP_Real feastol, 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)
static SCIP_DECL_CONSENFOPS(consEnfopsSdp)
static int compLowerTriangPos(int i, int j)
adds the main functionality to fix/unfix/(multi-)aggregate variables by merging two three-tuple-array...
#define CONSHDLR_ENFOPRIORITY
static SCIP_DECL_CONSFREE(consFreeSdp)
static SCIP_DECL_CONSPRESOL(consPresolSdp)
static SCIP_DECL_CONSEXITPRE(consExitpreSdp)
static SCIP_DECL_CONSPRINT(consPrintSdp)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySdp)
#define CONSHDLR_MAXPREROUNDS
static SCIP_DECL_CONSINITPRE(consInitpreSdp)
SCIP_RETCODE SCIPconsSdpCheckSdpCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_RESULT *result)
static SCIP_DECL_CONSSEPASOL(consSepasolSdp)
static SCIP_DECL_CONSGETVARS(consGetVarsSdp)
#define CONSHDLR_SEPAPRIORITY
SCIP_RETCODE SCIPconsSdpGetNNonz(SCIP *scip, SCIP_CONS *cons, int *nnonz, int *constnnonz)
static SCIP_RETCODE fixAndAggrVars(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool aggregate)
static SCIP_DECL_CONSLOCK(consLockSdp)
static SCIP_DECL_CONSGETNVARS(consGetNVarsSdp)
static SCIP_DECL_CONSCOPY(consCopySdp)
interface methods for eigenvector computation and matrix multiplication using different versions of L...
static SCIP_RETCODE cutUsingEigenvector(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *coeff, SCIP_Real *lhs)
static SCIP_DECL_CONSENFOLP(consEnfolpSdp)
EXTERN SCIP_RETCODE SCIPlapackComputeIthEigenvalue(BMS_BLKMEM *blkmem, SCIP_Bool geteigenvectors, int n, SCIP_Real *A, int i, SCIP_Real *eigenvalue, SCIP_Real *eigenvector)