SCIP-SDP
2.0.0
|
Constraint handler for SDP-constraints. More...
Go to the source code of this file.
Macros | |
#define | CONSHDLR_NAME "SDP" |
#define | CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd" |
#define | CONSHDLR_SEPAPRIORITY +1000000 |
#define | CONSHDLR_ENFOPRIORITY -2000000 |
#define | CONSHDLR_CHECKPRIORITY -2000000 |
#define | CONSHDLR_SEPAFREQ 1 |
#define | CONSHDLR_EAGERFREQ 100 |
#define | CONSHDLR_MAXPREROUNDS -1 |
#define | CONSHDLR_DELAYSEPA FALSE |
#define | CONSHDLR_NEEDSCONS TRUE |
#define | CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST |
Functions | |
static int | compLowerTriangPos (int i, int j) |
static SCIP_RETCODE | expandSymMatrix (int size, SCIP_Real *symMat, SCIP_Real *fullMat) |
static SCIP_RETCODE | computeSdpMatrix (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *y, SCIP_Real *matrix) |
static SCIP_RETCODE | multiplyConstraintMatrix (SCIP_CONS *cons, int j, SCIP_Real *v, SCIP_Real *vAv) |
static SCIP_RETCODE | setMaxRhsEntry (SCIP_CONS *cons) |
static SCIP_RETCODE | cutUsingEigenvector (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *coeff, SCIP_Real *lhs) |
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_RETCODE | separateSol (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result) |
static SCIP_RETCODE | diagGEzero (SCIP *scip, SCIP_CONS **conss, int nconss, int *naddconss) |
static SCIP_RETCODE | move_1x1_blocks_to_lp (SCIP *scip, SCIP_CONS **conss, int nconss, int *naddconss, int *ndelconss, SCIP_RESULT *result) |
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 | fixAndAggrVars (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool aggregate) |
static | SCIP_DECL_CONSINITPRE (consInitpreSdp) |
static | SCIP_DECL_CONSLOCK (consLockSdp) |
static | SCIP_DECL_CONSEXITPRE (consExitpreSdp) |
static | SCIP_DECL_CONSPRESOL (consPresolSdp) |
static | SCIP_DECL_CONSTRANS (consTransSdp) |
static | SCIP_DECL_CONSCHECK (consCheckSdp) |
static | SCIP_DECL_CONSENFOPS (consEnfopsSdp) |
static | SCIP_DECL_CONSENFOLP (consEnfolpSdp) |
static | SCIP_DECL_CONSSEPASOL (consSepasolSdp) |
static | SCIP_DECL_CONSSEPALP (consSepalpSdp) |
static | SCIP_DECL_CONSDELETE (consDeleteSdp) |
static | SCIP_DECL_CONSFREE (consFreeSdp) |
static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopySdp) |
static | SCIP_DECL_CONSCOPY (consCopySdp) |
static | SCIP_DECL_CONSPRINT (consPrintSdp) |
static | SCIP_DECL_CONSGETVARS (consGetVarsSdp) |
static | SCIP_DECL_CONSGETNVARS (consGetNVarsSdp) |
SCIP_RETCODE | SCIPincludeConshdlrSdp (SCIP *scip) |
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_RETCODE | SCIPconsSdpGetNNonz (SCIP *scip, SCIP_CONS *cons, int *nnonz, int *constnnonz) |
SCIP_RETCODE | SCIPconsSdpGetFullAj (SCIP *scip, SCIP_CONS *cons, int j, SCIP_Real *Aj) |
SCIP_RETCODE | SCIPconsSdpGetFullConstMatrix (SCIP *scip, SCIP_CONS *cons, SCIP_Real *mat) |
SCIP_RETCODE | SCIPconsSdpGetLowerTriangConstMatrix (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) |
Constraint handler for SDP-constraints.
Definition in file cons_sdp.c.
#define CONSHDLR_NAME "SDP" |
Definition at line 56 of file cons_sdp.c.
Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSHDLRCOPY(), and SCIPincludeConshdlrSdp().
#define CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd" |
Definition at line 57 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_SEPAPRIORITY +1000000 |
priority of the constraint handler for separation
Definition at line 58 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_ENFOPRIORITY -2000000 |
priority of the constraint handler for constraint enforcing
Definition at line 59 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_CHECKPRIORITY -2000000 |
priority of the constraint handler for checking feasibility
Definition at line 60 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_SEPAFREQ 1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 61 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 62 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 65 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 66 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 67 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST |
Definition at line 69 of file cons_sdp.c.
Referenced by SCIPincludeConshdlrSdp().
|
static |
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 104 of file cons_sdp.c.
Referenced by computeSdpMatrix(), diagGEzero(), expandSymMatrix(), and SCIPconsSdpGetLowerTriangConstMatrix().
|
static |
takes a 0.5*n*(n+1) array of a symmetric matrix and expands it to a n*n array of the full matrix to input into LAPACK
size | size of the matrix, named n above |
symMat | symmetric matrix indexed via compLowerTriangPos that should be expanded |
fullMat | pointer to store the n*n matrix, that is the symmetric expansion of symMat |
Definition at line 120 of file cons_sdp.c.
References compLowerTriangPos().
Referenced by cutUsingEigenvector(), and SCIPconsSdpCheckSdpCons().
|
static |
For a given vector computes the (length of y) * (length of y + 1) /2 -long array of the lower-triangular part of the SDP-Matrix for this SDP block, indexed by compLowerTriangPos.
scip | SCIP data structure |
cons | the constraint for which the Matrix should be assembled |
y | solution to separate |
matrix | pointer to store the SDP-Matrix |
Definition at line 153 of file cons_sdp.c.
References compLowerTriangPos().
Referenced by cutUsingEigenvector(), and SCIPconsSdpCheckSdpCons().
|
static |
For a given variable-index j and a Vector v computes .
cons | the SDP constraint that includes the Matrix |
j | variable-index of the matrix to multiply with |
v | vector to multiply with |
vAv | pointer to store the the resulting scalar |
Definition at line 195 of file cons_sdp.c.
Referenced by cutUsingEigenvector().
|
static |
Set the maximum absolute value of an entry of the constant matrix. This must be done before presolving, because otherwise this is influenced by variable fixings (which might lead to solutions being feasible in presolving no longer being feasible afterwards)
cons | the SDP constraint that includes the Matrix |
Definition at line 235 of file cons_sdp.c.
Referenced by SCIPcreateConsSdp().
|
static |
separate current solution with a cut using the eigenvectors and -values of the solution matrix
This function computes the eigenvectors of the matrix, takes the first one and multiplies the matrix with it such that .
scip | SCIP data structure |
cons | the constraint for which the Matrix should be assembled |
sol | solution to separate |
coeff | pointer to store the coefficients of the computed cut |
lhs | pointer to store the lhs of the computed cut |
Definition at line 268 of file cons_sdp.c.
References computeSdpMatrix(), expandSymMatrix(), multiplyConstraintMatrix(), SCIPconsSdpGetFullConstMatrix(), SCIPlapackComputeIthEigenvalue(), and SCIPlapackMatrixVectorMult().
Referenced by SCIP_DECL_CONSENFOLP(), and separateSol().
SCIP_RETCODE SCIPconsSdpCheckSdpCons | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
SCIP_SOL * | sol, | ||
SCIP_Bool | checkintegrality, | ||
SCIP_Bool | checklprows, | ||
SCIP_Bool | printreason, | ||
SCIP_RESULT * | result | ||
) |
checks feasibility for a single SDP-Cone
scip | SCIP data structure |
cons | the constraint for which the Matrix should be assembled |
sol | the solution to check feasibility for |
checkintegrality | has integrality to be checked? |
checklprows | have current LP rows to be checked? |
printreason | should the reason for the violation be printed? |
result | pointer to store the result of the feasibility checking call |
Definition at line 337 of file cons_sdp.c.
References computeSdpMatrix(), expandSymMatrix(), and SCIPlapackComputeIthEigenvalue().
Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFOPS().
|
static |
separates the current solution
scip | SCIP data structure |
conshdlr | the constraint handler itself |
cons | constraint to process |
sol | primal solution that should be separated |
result | pointer to store the result of the separation call |
Definition at line 400 of file cons_sdp.c.
References cutUsingEigenvector().
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
|
static |
approximates the sdpcone using the fact that every diagonal entry must be non-negative, so it adds the LP-cut
scip | SCIP data structure |
conss | array of constraints |
nconss | number of constraints |
naddconss | pointer to store how many constraints were added |
Definition at line 492 of file cons_sdp.c.
References compLowerTriangPos(), and SCIPconsSdpGetLowerTriangConstMatrix().
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
detects if there are blocks with size one and transfers them to lp-rows
scip | SCIP data structure |
conss | array of constraints to check |
nconss | number of constraints to check |
naddconss | pointer to store how many constraints were added |
ndelconss | pointer to store how many constraints were deleted |
result | pointer to store if this routine was successfull or if it detected infeasibility |
Definition at line 756 of file cons_sdp.c.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
local function to perform (parts of) multiaggregation of a single variable within fixAndAggrVars
cons | SCIP pointer |
v | constraint to multiaggregate for |
aggrvars | position of the variable that gets (multi-)aggregated |
scalars | variables this has to be (multi-)aggregated to |
naggrvars | scalar parts to multiply with for each variable this is aggregated to |
constant | number of variables this is (multi-)aggregated to |
savedcol | the constant part for the (multi-)aggregation |
savedrow | array of columns for nonzeros that need to be added to the constant part |
savedval | array of rows for nonzeros that need to be added to the constant part |
nfixednonz | array of values for nonzeros that need to be added to the constant part |
vararraylength | length of the arrays of saved nonzeros for the constant part length of the variable array |
Definition at line 962 of file cons_sdp.c.
References SCIPsdpVarfixerMergeArrays(), and SCIPsdpVarfixerSortRowCol().
Referenced by fixAndAggrVars().
|
static |
presolve routine that looks through the data and handles fixed, (multi-)aggregated and negated variables
scip | SCIP data structure |
conss | array with constraints to check |
nconss | number of constraints to check |
aggregate | do we want to (mutli-)aggregate variables ? |
Definition at line 1166 of file cons_sdp.c.
References multiaggrVar(), and SCIPsdpVarfixerMergeArrays().
Referenced by SCIP_DECL_CONSCOPY(), and SCIP_DECL_CONSEXITPRE().
|
static |
informs constraint handler that the presolving process is being started
Definition at line 1384 of file cons_sdp.c.
|
static |
locks a variable up if the corresponding constraint matrix is not positive semidefinite, locks it down if it is not negative semidefinite
Definition at line 1403 of file cons_sdp.c.
References SCIPconsSdpGetFullAj(), and SCIPlapackComputeIthEigenvalue().
|
static |
after presolving variables are fixed and multiaggregated
Definition at line 1459 of file cons_sdp.c.
References fixAndAggrVars().
|
static |
presolving method of constraint handler
Definition at line 1471 of file cons_sdp.c.
References diagGEzero(), and move_1x1_blocks_to_lp().
|
static |
creates transformed constraint
Definition at line 1493 of file cons_sdp.c.
|
static |
checks feasiblity of constraint, e.g. the positive semidefiniteness
Definition at line 1553 of file cons_sdp.c.
References SCIPconsSdpCheckSdpCons().
|
static |
enforce pseudo solution method
Returns didnotrun, if objinfeasible, computes feasibility otherwise.
Definition at line 1577 of file cons_sdp.c.
References SCIPconsSdpCheckSdpCons().
|
static |
constraint enforcing method of constraint handler for LP solutions
Enforce lp solution method, if some block is not psd an eigenvector cut is added.
Definition at line 1616 of file cons_sdp.c.
References cutUsingEigenvector(), and SCIPconsSdpCheckSdpCons().
|
static |
separates a solution using constraint specific ideas, gives cuts to SCIP
Definition at line 1726 of file cons_sdp.c.
References separateSol().
|
static |
separation method of constraint handler for LP solution
Definition at line 1741 of file cons_sdp.c.
References separateSol().
|
static |
delete method of SDP constrainthandler
Definition at line 1756 of file cons_sdp.c.
|
static |
free method of sdp constrainthandler
Definition at line 1793 of file cons_sdp.c.
|
static |
copy an SDP constraint handler
Definition at line 1808 of file cons_sdp.c.
References CONSHDLR_NAME, and SCIPincludeConshdlrSdp().
|
static |
copy an SDP constraint
Definition at line 1823 of file cons_sdp.c.
References CONSHDLR_NAME, fixAndAggrVars(), and SCIPcreateConsSdp().
|
static |
print an SDP constraint
Definition at line 1878 of file cons_sdp.c.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 1959 of file cons_sdp.c.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 1994 of file cons_sdp.c.
SCIP_RETCODE SCIPincludeConshdlrSdp | ( | SCIP * | scip | ) |
creates the handler for SDP constraints and includes it in SCIP
scip | SCIP data structure |
Definition at line 2013 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, and CONSHDLR_SEPAPRIORITY.
Referenced by runSCIP(), and SCIP_DECL_CONSHDLRCOPY().
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 | ||
) |
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.
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 nonzeroes 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 nonzeroes for each variable |
row | pointer to store the row indices of the nonzeroes for each variable |
val | pointer to store the values of the nonzeroes for each variable |
vars | pointer to store the SCIP variables present in this constraint, indexing equals indices in col/row/val |
constnnonz | pointer to store the number of nonzeroes in the constant part of this SDP constraint, also length of the const arrays |
constcol | pointer to store the column indices of the constant nonzeroes |
constrow | pointer to store the row indices of the constant nonzeroes |
constval | pointer to store the values of the constant nonzeroes |
Definition at line 2055 of file cons_sdp.c.
Referenced by putSdpDataInInterface().
SCIP_RETCODE SCIPconsSdpGetNNonz | ( | SCIP * | scip, |
SCIP_CONS * | cons, | ||
int * | nnonz, | ||
int * | constnnonz | ||
) |
gets the number of nonzeroes and constant nonzeroes for this SDP constraint
Either nnonz or constnnonz may be NULL.
scip | SCIP data structure |
cons | SDP constraint to get data of |
nnonz | pointer to store the number of nonzeroes in this SDP constraint |
constnnonz | pointer to store the number of nonzeroes in the constant part of this SDP constraint |
Definition at line 2151 of file cons_sdp.c.
Referenced by putSdpDataInInterface().
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 data of |
j | the variable j to get the corresponding matrix for |
Aj | pointer to store the full matrix |
Definition at line 2176 of file cons_sdp.c.
Referenced by SCIP_DECL_CONSLOCK().
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 data of |
mat | pointer to store the full constant matrix |
Definition at line 2211 of file cons_sdp.c.
Referenced by cutUsingEigenvector().
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 compLowerTriangPos
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 2245 of file cons_sdp.c.
References compLowerTriangPos().
Referenced by diagGEzero().
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 nonzeroes 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 nonzeroes for each variable |
vars | SCIP_VARiables present in this SDP constraint, ordered by their begvar-indices |
constnnonz | number of nonzeroes in the constant part of this SDP constraint |
constcol | column indices of the constant nonzeroes |
constrow | row indices of the constant nonzeroes |
constval | values of the constant nonzeroes |
Definition at line 2275 of file cons_sdp.c.
References setMaxRhsEntry().
Referenced by SCIP_DECL_CONSCOPY(), and scip::ObjReaderSDPA::scip_read().