SCIP-SDP
3.2.0
|
Constraint handler for SDP-constraints. More...
Go to the source code of this file.
Functions | |
SCIP_EXPORT SCIP_RETCODE | SCIPincludeConshdlrSdp (SCIP *scip) |
SCIP_EXPORT SCIP_RETCODE | SCIPincludeConshdlrSdpRank1 (SCIP *scip) |
SCIP_EXPORT 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_EXPORT 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_EXPORT int | SCIPconsSdpCompLowerTriangPos (int i, int j) |
SCIP_EXPORT 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) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGetNNonz (SCIP *scip, SCIP_CONS *cons, int *nnonz, int *constnnonz) |
SCIP_EXPORT int | SCIPconsSdpGetBlocksize (SCIP *scip, SCIP_CONS *cons) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGetFullAj (SCIP *scip, SCIP_CONS *cons, int j, SCIP_Real *Aj) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGetFullConstMatrix (SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGetLowerTriangConstMatrix (SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpCheckSdpCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_RESULT *result) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGuessInitialPoint (SCIP *scip, SCIP_CONS *cons, SCIP_Real *lambdastar) |
SCIP_EXPORT SCIP_Real | SCIPconsSdpGetMaxConstEntry (SCIP *scip, SCIP_CONS *cons) |
SCIP_EXPORT SCIP_Real | SCIPconsSdpGetMaxSdpCoef (SCIP *scip, SCIP_CONS *cons) |
SCIP_EXPORT int | SCIPconsSdpComputeUbSparseSdpMatrixLength (SCIP_CONS *cons) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpComputeSparseSdpMatrix (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, int *length, int *row, int *col, SCIP_Real *val) |
SCIP_EXPORT SCIP_Bool | SCIPconsSdpShouldBeRankOne (SCIP_CONS *cons) |
SCIP_EXPORT SCIP_RETCODE | SCIPconsSdpGetMaxEVSubmat (SCIP_CONS *cons, int **maxevsubmat) |
SCIP_EXPORT SCIP_Bool | SCIPconsSdpAddedQuadCons (SCIP_CONS *cons) |
Constraint handler for SDP-constraints.
Constraint handler for semidefinite constraints of the form , where the matrices and need to be symmetric. Only the nonzero entries of the matrices are stored.
Definition in file cons_sdp.h.
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrSdp | ( | SCIP * | scip | ) |
creates the handler for SDP constraints and includes it in SCIP
scip | SCIP data structure |
Definition at line 4420 of file cons_sdp.c.
References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PRESOLTIMING, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, DEFAULT_DIAGGEZEROCUTS, DEFAULT_DIAGZEROIMPLCUTS, DEFAULT_MAXNVARSQUADUPGD, DEFAULT_QUADCONSRANK1, DEFAULT_RANK1APPROXHEUR, DEFAULT_TWOMINORLINCONSS, DEFAULT_TWOMINORPRODCONSS, DEFAULT_UPGRADEKEEPQUAD, DEFAULT_UPGRADQUADCONSS, and SCIPincludeConshdlrSdpRank1().
Referenced by SCIP_DECL_CONSGETNVARS(), SCIP_DECL_CONSHDLRCOPY(), and SCIPSDPincludeDefaultPlugins().
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrSdpRank1 | ( | SCIP * | scip | ) |
creates the handler for rank 1 SDP constraints and includes it in SCIP
scip | SCIP data structure |
Definition at line 4513 of file cons_sdp.c.
References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYSEPA, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PRESOLTIMING, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLRRANK1_DESC, CONSHDLRRANK1_NAME, and SCIPconsSdpCompLowerTriangPos().
Referenced by SCIP_DECL_CONSHDLRCOPY(), SCIPincludeConshdlrSdp(), and SCIPSDPincludeDefaultPlugins().
SCIP_EXPORT 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 | ||
) |
creates an SDP-constraint
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nvars | number of variables in this SDP constraint |
nnonz | number of nonzeros in this SDP constraint |
blocksize | size of this SDP-block |
nvarnonz | number of nonzeros for each variable, also length of the arrays col/row/val point to |
col | pointer to column indices of the nonzeros for each variable |
row | pointer to row indices of the nonzeros for each variable |
val | pointer to values of the nonzeros for each variable |
vars | SCIP_VARiables present in this SDP constraint that correspond to the indices in col/row/val |
constnnonz | number of nonzeros in the constant part of this SDP constraint |
constcol | column indices of the constant nonzeros |
constrow | row indices of the constant nonzeros |
constval | values of the constant nonzeros |
Definition at line 5150 of file cons_sdp.c.
References name, SCIPcreateConsSdpRank1(), and setMaxRhsEntry().
Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_QUADCONSUPGD(), scip::SCIP_DECL_READERREAD(), and SCIPconsSdpAddedQuadCons().
SCIP_EXPORT 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 | ||
) |
creates a rank 1 SDP-constraint
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nvars | number of variables in this SDP constraint |
nnonz | number of nonzeros in this SDP constraint |
blocksize | size of this SDP-block |
nvarnonz | number of nonzeros for each variable, also length of the arrays col/row/val point to |
col | pointer to column indices of the nonzeros for each variable |
row | pointer to row indices of the nonzeros for each variable |
val | pointer to values of the nonzeros for each variable |
vars | SCIP_VARiables present in this SDP constraint that correspond to the indices in col/row/val |
constnnonz | number of nonzeros in the constant part of this SDP constraint |
constcol | column indices of the constant nonzeros |
constrow | row indices of the constant nonzeros |
constval | values of the constant nonzeros |
Definition at line 5269 of file cons_sdp.c.
References CONSHDLRRANK1_NAME, name, and setMaxRhsEntry().
Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_QUADCONSUPGD(), and SCIPcreateConsSdp().
SCIP_EXPORT int SCIPconsSdpCompLowerTriangPos | ( | int | i, |
int | j | ||
) |
for given row and column (i,j) computes the position in the lower triangular part, if these positions are numbered from 0 to n(n+1)/2 - 1, this needs to be called for i >= j
i | row index |
j | column index |
Definition at line 4585 of file cons_sdp.c.
References SCIPconsSdpGetData().
Referenced by calcRelax(), computeSdpMatrix(), diagGEzero(), expandSymMatrix(), isMatrixRankOne(), SCIP_DECL_CONSINITSOL(), SCIPconsSdpGetLowerTriangConstMatrix(), and SCIPincludeConshdlrSdpRank1().
SCIP_EXPORT 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 | ||
) |
get the data belonging to a single SDP-constraint
In arraylength the length of the nvarnonz, col, row and val arrays has to be given, if it is not sufficient to store all block-pointers that need to be inserted, a debug message will be thrown and this variable will be set to the needed length. constnnonz should give the length of the const arrays, if it is too short it will also give the needed number and a debug message is thrown.
get the data belonging to a single SDP-constraint
In arraylength the length of the nvarnonz, col, row and val arrays has to be given, if it is not sufficient to store all block-pointers that need to be inserted, a debug message will be thrown and this variable will be set to the needed length. constnnonz should give the length of the const arrays, if it is too short it will also give the needed number and a debug message is thrown. rankone and maxevsubmat can be NULL-pointers, if the corresponding information is not needed.
scip | SCIP data structure |
cons | SDP constraint to get data of |
nvars | pointer to store the number of variables in this SDP constraint |
nnonz | pointer to store the number of nonzeros in this SDP constraint |
blocksize | pointer to store the size of this SDP-block |
arraylength | length of the given nvarnonz, col, row and val arrays, if this is too short this will return the needed length |
nvarnonz | pointer to store the number of nonzeros for each variable, also length of the arrays col/row/val are pointing to |
col | pointer to store the column indices of the nonzeros for each variable |
row | pointer to store the row indices of the nonzeros for each variable |
val | pointer to store the values of the nonzeros for each variable |
vars | pointer to store the SCIP variables present in this constraint that correspond to the indices in col/row/val |
constnnonz | pointer to store the number of nonzeros in the constant part of this SDP constraint, also length of the const arrays |
constcol | pointer to store the column indices of the constant nonzeros |
constrow | pointer to store the row indices of the constant nonzeros |
constval | pointer to store the values of the constant nonzeros |
rankone | pointer to store if matrix should be rank one (or NULL, if information not necessary) |
maxevsubmat | pointer to store two row indices of 2x2 subdeterminant with maximal eigenvalue [-1,-1 if not yet computed] (or NULL, if information not necessary) |
addedquadcons | pointer to store if the quadratic 2x2-minor constraints already added (in the rank1-case) (or NULL, if information not necessary) |
Definition at line 4603 of file cons_sdp.c.
References SCIPconsSdpGetNNonz().
Referenced by calcRelax(), putSdpDataInInterface(), and SCIPconsSdpCompLowerTriangPos().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGetNNonz | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
int * | nnonz, | ||
int * | constnnonz | ||
) |
gets the number of nonzeros and constant nonzeros for this SDP constraint
Either nnonz or constnnonz may be NULL if only the other one is needed.
scip | SCIP data structure |
cons | SDP constraint to get number of nonzeros for |
nnonz | pointer to store the number of nonzeros in this SDP constraint |
constnnonz | pointer to store the number of nonzeros in the constant part of this SDP constraint |
Definition at line 4710 of file cons_sdp.c.
References SCIPconsSdpGetBlocksize().
Referenced by calcRelax(), putSdpDataInInterface(), and SCIPconsSdpGetData().
SCIP_EXPORT int SCIPconsSdpGetBlocksize | ( | SCIP * | scip, |
SCIP_CONS * | cons | ||
) |
gets the blocksize of the SDP constraint
scip | SCIP data structure |
cons | SDP constraint to get blocksize for |
Definition at line 4735 of file cons_sdp.c.
References SCIPconsSdpGetFullAj().
Referenced by calcRelax(), SCIPconsSdpGetNNonz(), and SCIPrelaxSdpComputeAnalyticCenters().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGetFullAj | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
int | j, | ||
SCIP_Real * | Aj | ||
) |
gets the full constraint Matrix for a given variable j
scip | SCIP data structure |
cons | SDP constraint to get matrix for |
j | the variable j to get the corresponding matrix for |
Aj | pointer to store the full matrix |
Definition at line 4752 of file cons_sdp.c.
References SCIPconsSdpGetFullConstMatrix().
Referenced by addTwoMinorLinConstraints(), addTwoMinorProdConstraints(), checkVarsLocks(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSLOCK(), SCIPconsSdpGetBlocksize(), and updateVarLocks().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGetFullConstMatrix | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_Real * | mat | ||
) |
gives an n*n-long array with the full constant matrix
scip | SCIP data structure |
cons | SDP constraint to get matrix for |
mat | pointer to store the full constant matrix |
Definition at line 4787 of file cons_sdp.c.
References SCIPconsSdpGetLowerTriangConstMatrix().
Referenced by addTwoMinorLinConstraints(), addTwoMinorProdConstraints(), cutUsingEigenvector(), SCIP_DECL_CONSCHECK(), and SCIPconsSdpGetFullAj().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGetLowerTriangConstMatrix | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_Real * | mat | ||
) |
gives a 0.5*n*(n+1)-long array with the lower triangular part of the constant matrix indexed by SCIPconsSdpCompLowerTriangPos
scip | SCIP data structure |
cons | SDP constraint to get data of |
mat | pointer to store the lower triangular part of the constant matrix |
Definition at line 4821 of file cons_sdp.c.
References SCIPconsSdpCompLowerTriangPos(), and SCIPconsSdpGuessInitialPoint().
Referenced by diagGEzero(), SCIP_DECL_CONSINITSOL(), and SCIPconsSdpGetFullConstMatrix().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpCheckSdpCons | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_SOL * | sol, | ||
SCIP_Bool | printreason, | ||
SCIP_RESULT * | result | ||
) |
checks feasibility for a single SDP constraint
scip | SCIP data structure |
cons | the constraint the solution should be checked for |
sol | the solution to check feasibility for |
printreason | should the reason for the violation be printed? |
result | pointer to store the result of the feasibility checking call |
Definition at line 540 of file cons_sdp.c.
References computeSdpMatrix(), CONSHDLR_NAME, CONSHDLRRANK1_NAME, expandSymMatrix(), SCIPlapackComputeIthEigenvalue(), and separateSol().
Referenced by cutUsingEigenvector(), enforceConstraint(), isMatrixRankOne(), SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOPS().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGuessInitialPoint | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_Real * | lambdastar | ||
) |
Compute a heuristic guess for a good starting solution .
The solution is computed as
where measures the sparsity of the matrices.
scip | SCIP data structure |
cons | the constraint for which the initial point should be constructed |
lambdastar | pointer to store the guess for the initial point |
Definition at line 4860 of file cons_sdp.c.
References CONSHDLR_NAME, CONSHDLRRANK1_NAME, and SCIPconsSdpGetMaxConstEntry().
Referenced by SCIP_DECL_RELAXINITSOL(), and SCIPconsSdpGetLowerTriangConstMatrix().
SCIP_EXPORT SCIP_Real SCIPconsSdpGetMaxConstEntry | ( | SCIP * | scip, |
SCIP_CONS * | cons | ||
) |
Gets maximum absolute entry of constant matrix
scip | SCIP data structure |
cons | the constraint to get the maximum constant matrix entry for |
Definition at line 4956 of file cons_sdp.c.
References SCIPconsSdpGetMaxSdpCoef().
Referenced by SCIP_DECL_RELAXINITSOL(), and SCIPconsSdpGuessInitialPoint().
SCIP_EXPORT SCIP_Real SCIPconsSdpGetMaxSdpCoef | ( | SCIP * | scip, |
SCIP_CONS * | cons | ||
) |
Gets maximum absolute entry of all matrices
scip | SCIP data structure |
cons | the constraint to get the maximum constant matrix entry for |
Definition at line 4972 of file cons_sdp.c.
References SCIPconsSdpComputeUbSparseSdpMatrixLength().
Referenced by SCIP_DECL_RELAXINITSOL(), and SCIPconsSdpGetMaxConstEntry().
SCIP_EXPORT int SCIPconsSdpComputeUbSparseSdpMatrixLength | ( | SCIP_CONS * | cons | ) |
Computes an upper bound on the number of nonzeros of the (dual) SDP matrix , this should be used to allocate enough memory before calling SCIPconsSdpComputeSparseSdpMatrix.
Upper bound is computed as .
cons | the constraint for which the Matrix should be assembled |
Definition at line 5006 of file cons_sdp.c.
References SCIPconsSdpComputeSparseSdpMatrix().
Referenced by calcRelax(), SCIPconsSdpGetMaxSdpCoef(), and SCIPrelaxSdpComputeAnalyticCenters().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpComputeSparseSdpMatrix | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_SOL * | sol, | ||
int * | length, | ||
int * | row, | ||
int * | col, | ||
SCIP_Real * | val | ||
) |
Computes (dual) SDP matrix and returns it in sparse format
scip | SCIP data structure |
cons | the constraint for which the Matrix should be assembled |
sol | the solution to assemble the matrix for |
length | input: allocated memory for row/col/val arrays output: number of nonzeros of the matrix / length of row/col/val arrays |
row | pointer to store row indices of SDP-matrix |
col | pointer to store column indices of SDP-matrix |
val | pointer to store values of SDP-matrix |
Definition at line 5034 of file cons_sdp.c.
References SCIPconsSdpShouldBeRankOne(), and SCIPsdpVarfixerMergeArrays().
Referenced by calcRelax(), SCIPconsSdpComputeUbSparseSdpMatrixLength(), and SCIPrelaxSdpComputeAnalyticCenters().
SCIP_EXPORT SCIP_Bool SCIPconsSdpShouldBeRankOne | ( | SCIP_CONS * | cons | ) |
returns wheter matrix should be rank one
returns whether the matrix should be rank one
cons | the constraint for which the existence of a rank one constraint should be checked |
Definition at line 5099 of file cons_sdp.c.
References SCIPconsSdpGetMaxEVSubmat().
Referenced by SCIPconsSdpComputeSparseSdpMatrix().
SCIP_EXPORT SCIP_RETCODE SCIPconsSdpGetMaxEVSubmat | ( | SCIP_CONS * | cons, |
int ** | maxevsubmat | ||
) |
returns two row indices of 2x2 subdeterminant with maximal eigenvalue [or -1,-1 if not available]
cons | the constraint for which the existence of a rank one constraint should be checked |
maxevsubmat | pointer to store the two row indices of 2x2 subdeterminant with maximal eigenvalue [or -1,-1 if not available] |
Definition at line 5114 of file cons_sdp.c.
References SCIPconsSdpAddedQuadCons().
Referenced by SCIPconsSdpShouldBeRankOne().
SCIP_EXPORT SCIP_Bool SCIPconsSdpAddedQuadCons | ( | SCIP_CONS * | cons | ) |
returns whether the quadratic 2x2-minor constraints are already added (in the rank1-case)
cons | the constraint for which it should be checked whether the quadratic 2x2-minor constraints are already added (in the rank1-case) |
Definition at line 5135 of file cons_sdp.c.
References SCIPcreateConsSdp().
Referenced by SCIPconsSdpGetMaxEVSubmat().