Constraint handler for SDP-constraints. More...

Macros
#define	CONSHDLR_NAME "SDP"

#define	CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd"

#define	CONSHDLRRANK1_NAME "SDPrank1"

#define	CONSHDLRRANK1_DESC "rank 1 SDP constraints"

#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

#define	PARSE_STARTSIZE 1

#define	PARSE_SIZEFACTOR 10

#define	DEFAULT_DIAGGEZEROCUTS TRUE

#define	DEFAULT_DIAGZEROIMPLCUTS TRUE

#define	DEFAULT_TWOMINORLINCONSS FALSE

#define	DEFAULT_TWOMINORPRODCONSS FALSE

#define	DEFAULT_QUADCONSRANK1 TRUE

#define	DEFAULT_UPGRADQUADCONSS FALSE

#define	DEFAULT_UPGRADEKEEPQUAD FALSE

#define	DEFAULT_MAXNVARSQUADUPGD 1000

#define	DEFAULT_RANK1APPROXHEUR FALSE

Functions
static SCIP_RETCODE	convertRowToColFormatFullMatrix (int rows, int cols, SCIP_Real rowmatrix, SCIP_Real colmatrix)

static SCIP_RETCODE	scaleRowsMatrix (int blocksize, SCIP_Real matrix, SCIP_Real scale)

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	isMatrixRankOne (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, SCIP_Bool result)

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 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_CONSHDLR conshdlr, SCIP_CONS *conss, int nconss, int naddconss, int nchgbds, SCIP_RESULT result)

static SCIP_RETCODE	diagZeroImpl (SCIP scip, SCIP_CONS conss, int nconss, int naddconss)

static SCIP_RETCODE	addTwoMinorLinConstraints (SCIP scip, SCIP_CONS conss, int nconss, int naddconss)

static SCIP_RETCODE	addTwoMinorProdConstraints (SCIP scip, SCIP_CONS conss, int nconss, int naddconss)

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_RESULT *result)

static SCIP_RETCODE	unlockVar (SCIP scip, SCIP_CONSDATA consdata, int v)

static SCIP_RETCODE	updateVarLocks (SCIP scip, SCIP_CONS cons, int v)

static SCIP_RETCODE	checkVarsLocks (SCIP scip, 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_RETCODE	fixAndAggrVars (SCIP scip, SCIP_CONS *conss, int nconss, SCIP_Bool aggregate)

static SCIP_RETCODE	enforceConstraint (SCIP scip, SCIP_CONSHDLR conshdlr, SCIP_CONS *conss, int nconss, SCIP_SOL sol, SCIP_RESULT *result)

static	SCIP_DECL_QUADCONSUPGD (consQuadConsUpgdSdp)

static	SCIP_DECL_CONSINITPRE (consInitpreSdp)

static	SCIP_DECL_CONSLOCK (consLockSdp)

static	SCIP_DECL_CONSEXIT (consExitSdp)

static	SCIP_DECL_CONSEXITPRE (consExitpreSdp)

static	SCIP_DECL_CONSINITSOL (consInitsolSdp)

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_CONSENFORELAX (consEnforelaxSdp)

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_CONSHDLRCOPY (conshdlrCopySdpRank1)

static	SCIP_DECL_CONSCOPY (consCopySdp)

static	SCIP_DECL_CONSPRINT (consPrintSdp)

static	SCIP_DECL_CONSPARSE (consParseSdp)

static	SCIP_DECL_CONSGETVARS (consGetVarsSdp)

static	SCIP_DECL_CONSGETNVARS (consGetNVarsSdp)

SCIP_RETCODE	SCIPincludeConshdlrSdp (SCIP *scip)

SCIP_RETCODE	SCIPincludeConshdlrSdpRank1 (SCIP *scip)

int	SCIPconsSdpCompLowerTriangPos (int i, int j)

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_RETCODE	SCIPconsSdpGetNNonz (SCIP scip, SCIP_CONS cons, int nnonz, int constnnonz)

int	SCIPconsSdpGetBlocksize (SCIP scip, SCIP_CONS cons)

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	SCIPconsSdpGuessInitialPoint (SCIP scip, SCIP_CONS cons, SCIP_Real *lambdastar)

SCIP_Real	SCIPconsSdpGetMaxConstEntry (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPconsSdpGetMaxSdpCoef (SCIP scip, SCIP_CONS cons)

int	SCIPconsSdpComputeUbSparseSdpMatrixLength (SCIP_CONS *cons)

SCIP_RETCODE	SCIPconsSdpComputeSparseSdpMatrix (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, int length, int row, int col, SCIP_Real *val)

SCIP_Bool	SCIPconsSdpShouldBeRankOne (SCIP_CONS *cons)

SCIP_RETCODE	SCIPconsSdpGetMaxEVSubmat (SCIP_CONS cons, int *maxevsubmat)

SCIP_Bool	SCIPconsSdpAddedQuadCons (SCIP_CONS *cons)

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	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)

Detailed Description

Constraint handler for SDP-constraints.

Author: Sonja Mars; Lars Schewe; Tristan Gally; Frederic Matter; Marc Pfetsch

Constraint handler for semidefinite constraints of the form $\sum_{j=1}^n A_j y_j - A_0 \succeq 0$ , where the matrices $A_j$ and $A_0$ need to be symmetric. Only the nonzero entries of the matrices are stored.

This file also contains a separate constraint handler for handling rank 1 SDP constraints. The callback functions are essentially the same, but some quadratic constraints are added to enforce the rank 1 condition.

Definition in file cons_sdp.c.

Macro Definition Documentation

#define CONSHDLR_NAME "SDP"

Definition at line 78 of file cons_sdp.c.

Referenced by diagGEzero(), fixAndAggrVars(), move_1x1_blocks_to_lp(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSHDLRCOPY(), SCIPconsSdpCheckSdpCons(), SCIPconsSdpGuessInitialPoint(), SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_DESC "SDP constraints of the form \\sum_{j} A_j y_j - A_0 psd"

Definition at line 79 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define CONSHDLRRANK1_NAME "SDPrank1"

Definition at line 81 of file cons_sdp.c.

Referenced by diagGEzero(), fixAndAggrVars(), move_1x1_blocks_to_lp(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_QUADCONSUPGD(), SCIPconsSdpCheckSdpCons(), SCIPconsSdpGuessInitialPoint(), SCIPcreateConsSdpRank1(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLRRANK1_DESC "rank 1 SDP constraints"

Definition at line 82 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_SEPAPRIORITY +1000000

priority of the constraint handler for separation

Definition at line 84 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_ENFOPRIORITY -2000000

priority of the constraint handler for constraint enforcing

Definition at line 85 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_CHECKPRIORITY -2000000

priority of the constraint handler for checking feasibility

Definition at line 86 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_SEPAFREQ 1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 87 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#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 88 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_MAXPREROUNDS -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 91 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_DELAYSEPA FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 92 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_NEEDSCONS TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 93 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST

Definition at line 95 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp(), and SCIPincludeConshdlrSdpRank1().

#define PARSE_STARTSIZE 1

initial size of the consdata-arrays when parsing a problem

Definition at line 96 of file cons_sdp.c.

Referenced by SCIP_DECL_CONSPARSE().

#define PARSE_SIZEFACTOR 10

size of consdata-arrays is increased by this factor when parsing a problem

Definition at line 97 of file cons_sdp.c.

Referenced by SCIP_DECL_CONSPARSE().

#define DEFAULT_DIAGGEZEROCUTS TRUE

Should linear cuts enforcing the non-negativity of diagonal entries of SDP-matrices be added?

Definition at line 98 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_DIAGZEROIMPLCUTS TRUE

Should linear cuts enforcing the implications of diagonal entries of zero in SDP-matrices be added?

Definition at line 99 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_TWOMINORLINCONSS FALSE

Should linear cuts corresponding to 2 by 2 minors be added?

Definition at line 100 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_TWOMINORPRODCONSS FALSE

Should linear cuts corresponding to products of 2 by 2 minors be added?

Definition at line 101 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_QUADCONSRANK1 TRUE

Should quadratic cons for 2x2 minors be added in the rank-1 case?

Definition at line 102 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_UPGRADQUADCONSS FALSE

Should quadratic constraints be upgraded to a rank 1 SDP?

Definition at line 103 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_UPGRADEKEEPQUAD FALSE

Should the quadratic constraints be kept in the problem after upgrading and the corresponding SDP constraint be added without the rank 1 constraint?

Definition at line 104 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_MAXNVARSQUADUPGD 1000

maximal number of quadratic constraints and appearing variables so that the QUADCONSUPGD is performed

Definition at line 105 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

#define DEFAULT_RANK1APPROXHEUR FALSE

Should the heuristic that computes the best rank-1 approximation for a given solution be executed?

Definition at line 106 of file cons_sdp.c.

Referenced by SCIPincludeConshdlrSdp().

Function Documentation

static SCIP_RETCODE convertRowToColFormatFullMatrix	(	int	rows,
		int	cols,
		SCIP_Real *	rowmatrix,
		SCIP_Real *	colmatrix
	)

static

generates matrix in colum-first format (needed by LAPACK) from matrix given in full row-first format (SCIP-SDP default)

Parameters

rows	number of rows
cols	number of columns
rowmatrix	matrix entries given as rows*cols array
colmatrix	pointer to array of length blocksize^2 to store rowmatrix in column-first format

Definition at line 165 of file cons_sdp.c.

References scaleRowsMatrix().

Referenced by SCIP_DECL_CONSCHECK().

static SCIP_RETCODE scaleRowsMatrix	(	int	blocksize,
		SCIP_Real *	matrix,
		SCIP_Real *	scale
	)

static

multiplies all entries in the i-th row by scale[i]

Definition at line 196 of file cons_sdp.c.

References expandSymMatrix().

Referenced by convertRowToColFormatFullMatrix(), and SCIP_DECL_CONSCHECK().

static SCIP_RETCODE expandSymMatrix	(	int	size,
		SCIP_Real *	symMat,
		SCIP_Real *	fullMat
	)

static

takes a 0.5*n*(n+1) array of a symmetric matrix and expands it to an n*n array of the full matrix to input into LAPACK

Parameters

size	size of the matrix, named n above
symMat	symmetric matrix indexed via SCIPconsSdpCompLowerTriangPos that should be expanded
fullMat	pointer to store the n*n matrix, that is the symmetric expansion of symMat

Definition at line 223 of file cons_sdp.c.

References computeSdpMatrix(), and SCIPconsSdpCompLowerTriangPos().

Referenced by cutUsingEigenvector(), isMatrixRankOne(), scaleRowsMatrix(), SCIP_DECL_CONSCHECK(), and SCIPconsSdpCheckSdpCons().

static SCIP_RETCODE computeSdpMatrix	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	y,
		SCIP_Real *	matrix
	)

static

For a given vector $ y $ computes the (length of y) * (length of y + 1) /2 -long array of the lower-triangular part of the SDP-Matrix $\sum_{j=1}^m A_j y_j - A_0$ for this SDP block, indexed by SCIPconsSdpCompLowerTriangPos.

Parameters

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 256 of file cons_sdp.c.

References isMatrixRankOne(), and SCIPconsSdpCompLowerTriangPos().

Referenced by cutUsingEigenvector(), expandSymMatrix(), isMatrixRankOne(), SCIP_DECL_CONSCHECK(), and SCIPconsSdpCheckSdpCons().

static SCIP_RETCODE isMatrixRankOne	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool *	result
	)

static

Check whether current matrix is rank one, if not so, sets maxevsubmat

Parameters

scip	SCIP data structure
cons	the SDP constraint to check the rank for
sol	solution to check for rank one
result	result pointer to return whether matrix is rank one

Definition at line 298 of file cons_sdp.c.

References computeSdpMatrix(), expandSymMatrix(), multiplyConstraintMatrix(), SCIPconsSdpCheckSdpCons(), SCIPconsSdpCompLowerTriangPos(), and SCIPlapackComputeIthEigenvalue().

Referenced by computeSdpMatrix(), and SCIP_DECL_CONSCHECK().

static SCIP_RETCODE multiplyConstraintMatrix	(	SCIP_CONS *	cons,
		int	j,
		SCIP_Real *	v,
		SCIP_Real *	vAv
	)

static

For a given variable-index j and a Vector v computes $ v^T A_j v $ .

Parameters

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 398 of file cons_sdp.c.

References setMaxRhsEntry().

Referenced by cutUsingEigenvector(), and isMatrixRankOne().

static SCIP_RETCODE setMaxRhsEntry ( SCIP_CONS * cons )

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)

Parameters

cons	the SDP constraint that includes the Matrix

Definition at line 438 of file cons_sdp.c.

References cutUsingEigenvector().

Referenced by multiplyConstraintMatrix(), SCIP_DECL_CONSPARSE(), SCIPcreateConsSdp(), and SCIPcreateConsSdpRank1().

static SCIP_RETCODE cutUsingEigenvector	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Real *	coeff,
		SCIP_Real *	lhs
	)

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 one corresponding to the smallest eigenvalue and multiplies the matrix with it such that $ coeff[i] = x^TA_ix , lhs = x^TA_0x $ .

Parameters

scip	SCIP data structure
cons	the constraint to compute the cut for
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 471 of file cons_sdp.c.

References computeSdpMatrix(), expandSymMatrix(), multiplyConstraintMatrix(), SCIPconsSdpCheckSdpCons(), SCIPconsSdpGetFullConstMatrix(), SCIPlapackComputeIthEigenvalue(), and SCIPlapackMatrixVectorMult().

Referenced by enforceConstraint(), separateSol(), and setMaxRhsEntry().

SCIP_RETCODE SCIPconsSdpCheckSdpCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool	printreason,
		SCIP_RESULT *	result
	)

checks feasibility for a single SDP constraint

Parameters

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().

static SCIP_RETCODE separateSol	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

separates the current solution

Parameters

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 603 of file cons_sdp.c.

References cutUsingEigenvector(), and diagGEzero().

Referenced by SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and SCIPconsSdpCheckSdpCons().

static SCIP_RETCODE diagGEzero	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss,
		int *	naddconss,
		int *	nchgbds,
		SCIP_RESULT *	result
	)

static

approximates the sdpcone using the fact that every diagonal entry must be non-negative, so it adds the LP-cut $\sum_{j = 1}^m (A_j)_{kk} y_j - (A_0)_{kk} \geq 0 \quad \forall k \leq n$

Parameters

scip	SCIP data structure
conshdlr	constraint handler
conss	array of constraints to add cuts for
nconss	number of constraints to add cuts for
naddconss	pointer to store how many constraints were added
nchgbds	pointer to store how many bounds were changed
result	result pointer

Definition at line 698 of file cons_sdp.c.

References CONSHDLR_NAME, CONSHDLRRANK1_NAME, diagZeroImpl(), SCIPconsSdpCompLowerTriangPos(), and SCIPconsSdpGetLowerTriangConstMatrix().

Referenced by SCIP_DECL_CONSPRESOL(), and separateSol().

static SCIP_RETCODE diagZeroImpl	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		int *	naddconss
	)

static

Presolve-routine that enforces implications of diagonal entries of zero in SDP-matrices, namely that if $X_{ij} > 0$ , then also $X_{ii} > 0$ and $X_{jj} > 0$ .

More precisely, if $(A_0)_{k\ell} \neq 0$ , $(A_0)_{kk} = 0$ , $(A_i)_{k\ell} = 0$ for all $i \leq m$ , $(A_i)_{kk} = 0$ for all continuous variables and $\ell_i \geq 0$ for all integer variables, we add the cut $\sum_{\substack{i \in \mathcal{I}:\\ (A_i)_{kk} > 0}} y_i \geq 1.$

Parameters

scip	SCIP data structure
conss	array of constraints
nconss	number of constraints
naddconss	pointer to store how many constraints were added

Definition at line 869 of file cons_sdp.c.

References addTwoMinorLinConstraints().

Referenced by diagGEzero(), and SCIP_DECL_CONSPRESOL().

static SCIP_RETCODE addTwoMinorLinConstraints	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		int *	naddconss
	)

static

presolve-routine that adds linear constraints arising from 2 by 2 minor inequalities

For a positive semidefinite matrix $X$ the following two inequalities hold: $X_{ss} + X_{tt} - 2\, X_{st} \geq 0$ and $X_{ss} + X_{tt} + 2\, X_{st} \geq 0$ . This follows by using a 2 by 2 minor and multiplying from left and right by the all-ones vector and $[1,-1]$ , respectively. We add the corresponding linear constraint only to be propagated.

Translated to the matrix pencil notation the cut looks as follows:

$\sum_{i=1}^m (A_i)_{ss}\, y_i - (A_0)_{ss} + \sum_{i=1}^m (A_i)_{tt}\, y_i - (A_0)_{tt} - 2 \Big(\sum_{i=1}^m (A_i)_{st}\, y_i - (A_0)_{st}\Big) \geq 0 \quad\Leftrightarrow\quad \sum_{i=1}^m \Big((A_i)_{ss} + (A_i)_{tt} - 2\, (A_i)_{st}\Big)\, y_i \geq (A_0)_{ss} + (A_0)_{tt} - 2 (A_0)_{st}.$

Parameters

scip	SCIP data structure
conss	array of constraints
nconss	number of constraints
naddconss	pointer to store how many constraints were added

Definition at line 1117 of file cons_sdp.c.

References addTwoMinorProdConstraints(), name, SCIPconsSdpGetFullAj(), and SCIPconsSdpGetFullConstMatrix().

Referenced by diagZeroImpl(), and SCIP_DECL_CONSPRESOL().

static SCIP_RETCODE addTwoMinorProdConstraints	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		int *	naddconss
	)

static

Presolve-routine that adds a linear cut arising from 2 by 2 minor inequalities $\sum_{i=1}^m (A_i)_{st} y_i \geq (A_0)_{st} - \sqrt{(A_0)_{ss} (A_0)_{tt}}$ , if $(A_i)_{ss} = (A_i)_{tt} = 0$ and $(A_0)_{ss} (A_0)_{tt} > 0$ for all $i,s,t$ .

See the dissertation of T. Gally, page 150.

Parameters

scip	SCIP data structure
conss	array of constraints
nconss	number of constraints
naddconss	pointer to store how many constraints were added

Definition at line 1275 of file cons_sdp.c.

References move_1x1_blocks_to_lp(), name, SCIPconsSdpGetFullAj(), and SCIPconsSdpGetFullConstMatrix().

Referenced by addTwoMinorLinConstraints(), and SCIP_DECL_CONSPRESOL().

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_RESULT *	result
	)

static

detects if there are blocks with size one and transforms them to lp-rows

Parameters

scip	SCIP data structure
conshdlr	constraint handler
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
nchgbds	pointer to store how many bounds were changed
result	pointer to store if this routine was successfull or if it detected infeasibility

Definition at line 1415 of file cons_sdp.c.

References CONSHDLR_NAME, CONSHDLRRANK1_NAME, and unlockVar().

Referenced by addTwoMinorProdConstraints(), and SCIP_DECL_CONSPRESOL().

static SCIP_RETCODE unlockVar	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		int	v
	)

static

unlock variable

Parameters

scip	SCIP pointer
consdata	data of constraint
v	index of variable

Definition at line 1566 of file cons_sdp.c.

References updateVarLocks().

Referenced by fixAndAggrVars(), move_1x1_blocks_to_lp(), multiaggrVar(), and updateVarLocks().

static SCIP_RETCODE updateVarLocks	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	v
	)

static

update locks of variable after aggregation

Parameters

scip	SCIP pointer
cons	constraint
v	index of variable

Definition at line 1599 of file cons_sdp.c.

References checkVarsLocks(), SCIPconsSdpGetFullAj(), SCIPlapackComputeIthEigenvalue(), and unlockVar().

Referenced by multiaggrVar(), and unlockVar().

static SCIP_RETCODE checkVarsLocks	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

static

check whether variable locks are correctly set

Parameters

scip	SCIP pointer
cons	constraint

Definition at line 1682 of file cons_sdp.c.

References multiaggrVar(), SCIPconsSdpGetFullAj(), and SCIPlapackComputeIthEigenvalue().

Referenced by multiaggrVar(), SCIP_DECL_CONSLOCK(), and updateVarLocks().

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

local function to perform (parts of) multiaggregation of a single variable within fixAndAggrVars

Parameters

scip	SCIP pointer
cons	constraint to multiaggregate for
v	position of the variable that gets (multi-)aggregated
aggrvars	variables this has to be (multi-)aggregated to
scalars	scalar parts to multiply with for each variable this is aggregated to
naggrvars	number of variables this is (multi-)aggregated to
constant	the constant part for the (multi-)aggregation
savedcol	array of columns for nonzeros that need to be added to the constant part
savedrow	array of rows for nonzeros that need to be added to the constant part
savedval	array of values for nonzeros that need to be added to the constant part
nfixednonz	length of the arrays of saved nonzeros for the constant part
vararraylength	length of the variable array

Definition at line 1747 of file cons_sdp.c.

References checkVarsLocks(), fixAndAggrVars(), SCIPsdpVarfixerMergeArrays(), SCIPsdpVarfixerSortRowCol(), unlockVar(), and updateVarLocks().

Referenced by checkVarsLocks(), and fixAndAggrVars().

static SCIP_RETCODE fixAndAggrVars	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_Bool	aggregate
	)

static

presolve routine that looks through the data and handles fixed, (multi-)aggregated and negated variables

Parameters

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 1966 of file cons_sdp.c.

References CONSHDLR_NAME, CONSHDLRRANK1_NAME, enforceConstraint(), multiaggrVar(), SCIPsdpVarfixerMergeArrays(), and unlockVar().

Referenced by multiaggrVar(), SCIP_DECL_CONSCOPY(), and SCIP_DECL_CONSEXITPRE().

static SCIP_RETCODE enforceConstraint	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

enforces the SDP constraints for a given solution

Parameters

scip	SCIP data structure
conshdlr	constraint handler
conss	constraints to process
nconss	number of constraints
sol	solution to enforce (NULL for the LP solution)
result	pointer to store the result of the enforcing call

Definition at line 2191 of file cons_sdp.c.

References cutUsingEigenvector(), SCIP_DECL_QUADCONSUPGD(), and SCIPconsSdpCheckSdpCons().

Referenced by fixAndAggrVars(), SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFORELAX().

static SCIP_DECL_QUADCONSUPGD ( consQuadConsUpgdSdp )

static

upgrade quadratic constraints to an SDP constraint with rank 1

Definition at line 2304 of file cons_sdp.c.

References CONSHDLRRANK1_NAME, name, SCIP_DECL_CONSINITPRE(), SCIPcreateConsSdp(), and SCIPcreateConsSdpRank1().

Referenced by enforceConstraint().

static SCIP_DECL_CONSINITPRE ( consInitpreSdp )

static

informs constraint handler that the presolving process is being started

Definition at line 2717 of file cons_sdp.c.

References SCIP_DECL_CONSLOCK().

Referenced by SCIP_DECL_QUADCONSUPGD().

static SCIP_DECL_CONSLOCK ( consLockSdp )

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 2735 of file cons_sdp.c.

References checkVarsLocks(), SCIP_DECL_CONSEXIT(), SCIPconsSdpGetFullAj(), and SCIPlapackComputeIthEigenvalue().

Referenced by SCIP_DECL_CONSINITPRE().

static SCIP_DECL_CONSEXIT ( consExitSdp )

static

deinitialization method of constraint handler (called before transformed problem is freed)

At the end of the solution process, the parameter for adding linear constraints in presolving needs to be reset.

Definition at line 2850 of file cons_sdp.c.

References SCIP_DECL_CONSEXITPRE().

Referenced by SCIP_DECL_CONSLOCK().

static SCIP_DECL_CONSEXITPRE ( consExitpreSdp )

static

after presolving variables are fixed and multiaggregated

Definition at line 2867 of file cons_sdp.c.

References fixAndAggrVars(), and SCIP_DECL_CONSINITSOL().

Referenced by SCIP_DECL_CONSEXIT().

static SCIP_DECL_CONSINITSOL ( consInitsolSdp )

static

solving process initialization method of constraint handler (called when branch and bound process is about to begin)

At the beginning of the solution process the stored rank one submatrix is reset.

Definition at line 2917 of file cons_sdp.c.

References name, SCIP_DECL_CONSPRESOL(), SCIPconsSdpCompLowerTriangPos(), SCIPconsSdpGetFullAj(), and SCIPconsSdpGetLowerTriangConstMatrix().

Referenced by SCIP_DECL_CONSEXITPRE().

static SCIP_DECL_CONSPRESOL ( consPresolSdp )

static

presolving method of constraint handler

Definition at line 3124 of file cons_sdp.c.

References addTwoMinorLinConstraints(), addTwoMinorProdConstraints(), diagGEzero(), diagZeroImpl(), move_1x1_blocks_to_lp(), and SCIP_DECL_CONSTRANS().

Referenced by SCIP_DECL_CONSINITSOL().

static SCIP_DECL_CONSTRANS ( consTransSdp )

static

creates transformed constraint

Definition at line 3200 of file cons_sdp.c.

References SCIP_DECL_CONSCHECK().

Referenced by SCIP_DECL_CONSPRESOL().

static SCIP_DECL_CONSCHECK ( consCheckSdp )

static

checks feasiblity of constraint, e.g. the positive semidefiniteness

Definition at line 3307 of file cons_sdp.c.

References computeSdpMatrix(), convertRowToColFormatFullMatrix(), expandSymMatrix(), isMatrixRankOne(), scaleRowsMatrix(), SCIP_DECL_CONSENFOPS(), SCIPconsSdpCheckSdpCons(), SCIPconsSdpGetFullAj(), SCIPconsSdpGetFullConstMatrix(), SCIPlapackComputeEigenvectorDecomposition(), SCIPlapackLinearSolve(), and SCIPlapackMatrixMatrixMult().

Referenced by SCIP_DECL_CONSTRANS().

static SCIP_DECL_CONSENFOPS ( consEnfopsSdp )

static

enforce pseudo solution method

Returns didnotrun if objinfeasible, computes feasibility otherwise.

Definition at line 3739 of file cons_sdp.c.

References SCIP_DECL_CONSENFOLP(), and SCIPconsSdpCheckSdpCons().

Referenced by SCIP_DECL_CONSCHECK().

static SCIP_DECL_CONSENFOLP ( consEnfolpSdp )

static

Enforce lp solution; if some block is not psd, an eigenvector cut is added.

Definition at line 3778 of file cons_sdp.c.

References enforceConstraint(), and SCIP_DECL_CONSENFORELAX().

Referenced by SCIP_DECL_CONSENFOPS().

static SCIP_DECL_CONSENFORELAX ( consEnforelaxSdp )

static

Enforce relaxation solution; if some block is not psd, an eigenvector cut is added.

Definition at line 3791 of file cons_sdp.c.

References enforceConstraint(), and SCIP_DECL_CONSSEPASOL().

Referenced by SCIP_DECL_CONSENFOLP().

static SCIP_DECL_CONSSEPASOL ( consSepasolSdp )

static

separates a solution using constraint specific ideas, gives cuts to SCIP

Definition at line 3803 of file cons_sdp.c.

References SCIP_DECL_CONSSEPALP(), and separateSol().

Referenced by SCIP_DECL_CONSENFORELAX().

static SCIP_DECL_CONSSEPALP ( consSepalpSdp )

static

separation method of constraint handler for LP solution

Definition at line 3820 of file cons_sdp.c.

References SCIP_DECL_CONSDELETE(), and separateSol().

Referenced by SCIP_DECL_CONSSEPASOL().

static SCIP_DECL_CONSDELETE ( consDeleteSdp )

static

delete method of SDP constrainthandler

Definition at line 3837 of file cons_sdp.c.

References SCIP_DECL_CONSFREE().

Referenced by SCIP_DECL_CONSSEPALP().

static SCIP_DECL_CONSFREE ( consFreeSdp )

static

free method of SDP constrainthandler

Definition at line 3878 of file cons_sdp.c.

References SCIP_DECL_CONSHDLRCOPY().

Referenced by SCIP_DECL_CONSDELETE().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySdp )

static

copy SDP constraint handler

Definition at line 3895 of file cons_sdp.c.

References CONSHDLR_NAME, and SCIPincludeConshdlrSdp().

Referenced by SCIP_DECL_CONSFREE().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopySdpRank1 )

static

copy rank 1 SDP constraint handler

Definition at line 3910 of file cons_sdp.c.

References CONSHDLRRANK1_NAME, SCIP_DECL_CONSCOPY(), and SCIPincludeConshdlrSdpRank1().

static SCIP_DECL_CONSCOPY ( consCopySdp )

static

copy an SDP constraint

Definition at line 3925 of file cons_sdp.c.

References CONSHDLR_NAME, CONSHDLRRANK1_NAME, fixAndAggrVars(), name, SCIP_DECL_CONSPRINT(), SCIPcreateConsSdp(), and SCIPcreateConsSdpRank1().

Referenced by SCIP_DECL_CONSHDLRCOPY().

static SCIP_DECL_CONSPRINT ( consPrintSdp )

static

print an SDP constraint

Definition at line 3999 of file cons_sdp.c.

References SCIP_DECL_CONSPARSE().

Referenced by SCIP_DECL_CONSCOPY().

static SCIP_DECL_CONSPARSE ( consParseSdp )

static

parse an SDP constraint

Definition at line 4140 of file cons_sdp.c.

References name, PARSE_SIZEFACTOR, PARSE_STARTSIZE, SCIP_DECL_CONSGETVARS(), and setMaxRhsEntry().

Referenced by SCIP_DECL_CONSPRINT().

static SCIP_DECL_CONSGETVARS ( consGetVarsSdp )

static

constraint method of constraint handler which returns the variables

Definition at line 4367 of file cons_sdp.c.

References SCIP_DECL_CONSGETNVARS().

Referenced by SCIP_DECL_CONSPARSE().

static SCIP_DECL_CONSGETNVARS ( consGetNVarsSdp )

static

constraint method of constraint handler which returns the number of variables

Definition at line 4401 of file cons_sdp.c.

References SCIPincludeConshdlrSdp().

Referenced by SCIP_DECL_CONSGETVARS().

SCIP_RETCODE SCIPincludeConshdlrSdp ( SCIP * scip )

creates the handler for SDP constraints and includes it in SCIP

Parameters

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_RETCODE SCIPincludeConshdlrSdpRank1 ( SCIP * scip )

creates the handler for rank 1 SDP constraints and includes it in SCIP

Parameters

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().

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

Parameters

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_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. rankone and maxevsubmat can be NULL-pointers, if the corresponding information is not needed.

Parameters

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_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.

Parameters

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().

int SCIPconsSdpGetBlocksize	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the blocksize of the SDP constraint

Parameters

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_RETCODE SCIPconsSdpGetFullAj	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int	j,
		SCIP_Real *	Aj
	)

gets the full constraint Matrix $ A_j $ for a given variable j

Parameters

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_RETCODE SCIPconsSdpGetFullConstMatrix	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Real *	mat
	)

gives an n*n-long array with the full constant matrix

Parameters

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_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

Parameters

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_RETCODE SCIPconsSdpGuessInitialPoint	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Real *	lambdastar
	)

Compute a heuristic guess for a good starting solution $\lambda ^* \cdot I$ .

The solution is computed as

$\lambda^* = \max \Bigg\{S \cdot \max_{i \in [m]} \{|u_i|, |l_i|\} \cdot \max_{i \in [m]} \|A_i\|_\infty + \|C\|_\infty, \frac{\max_{i \in [m]} b_i}{S \cdot \min_{i \in [m]} \min_{j, \ell \in [n]} (A_i)_{j\ell} } \Bigg\},$

where $S = \frac{ | \text{nonzero-entries of all } A_i | }{0.5 \cdot \text{ blocksize } (\text{ blocksize } + 1)}$ measures the sparsity of the matrices.

Parameters

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_Real SCIPconsSdpGetMaxConstEntry	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets maximum absolute entry of constant matrix $ A_0 $

Parameters

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_Real SCIPconsSdpGetMaxSdpCoef	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets maximum absolute entry of all matrices $ A_i $

Parameters

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().

int SCIPconsSdpComputeUbSparseSdpMatrixLength ( SCIP_CONS * cons )

Computes an upper bound on the number of nonzeros of the (dual) SDP matrix $Z = \sum_{j=1}^n A_j y_j - A_0$ , this should be used to allocate enough memory before calling SCIPconsSdpComputeSparseSdpMatrix.

Upper bound is computed as $\min \{ \sum_{v \leq m} \text{nvarnonz}(v) + \text{constnnonz}, n \cdot (n+1) / 2 \}$ .

Parameters

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_RETCODE SCIPconsSdpComputeSparseSdpMatrix	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		int *	length,
		int *	row,
		int *	col,
		SCIP_Real *	val
	)

Computes (dual) SDP matrix $Z = \sum_{j=1}^n A_j y_j - A_0$ and returns it in sparse format

Note: row, col and val should have memory allocated equal to SCIPconsSdpComputeUbSparseSdpMatrixLength(), if the memory is not sufficient, length will be set to -1 and an error will be thrown

Parameters

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_Bool SCIPconsSdpShouldBeRankOne ( SCIP_CONS * cons )

returns whether the matrix should be rank one

Parameters

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_RETCODE SCIPconsSdpGetMaxEVSubmat	(	SCIP_CONS *	cons,
		int **	maxevsubmat
	)

returns two row indices of 2x2 subdeterminant with maximal eigenvalue [or -1,-1 if not available]

Parameters

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_Bool SCIPconsSdpAddedQuadCons ( SCIP_CONS * cons )

returns whether the quadratic 2x2-minor constraints are already added (in the rank1-case)

Parameters

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().

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

Parameters

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_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

Parameters

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().

Macros

Functions

Detailed Description

Macro Definition Documentation

Function Documentation