Constraint handler for SDP-constraints. More...

Functions
EXTERN SCIP_RETCODE	SCIPincludeConshdlrSdp (SCIP *scip)

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

EXTERN int	SCIPconsSdpCompLowerTriangPos (int i, int j)

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

EXTERN SCIP_RETCODE	SCIPconsSdpGetNNonz (SCIP scip, SCIP_CONS cons, int nnonz, int constnnonz)

EXTERN int	SCIPconsSdpGetBlocksize (SCIP scip, SCIP_CONS cons)

EXTERN SCIP_RETCODE	SCIPconsSdpGetFullAj (SCIP scip, SCIP_CONS cons, int j, SCIP_Real *Aj)

EXTERN SCIP_RETCODE	SCIPconsSdpGetFullConstMatrix (SCIP scip, SCIP_CONS cons, SCIP_Real *mat)

EXTERN SCIP_RETCODE	SCIPconsSdpGetLowerTriangConstMatrix (SCIP scip, SCIP_CONS cons, SCIP_Real *mat)

EXTERN SCIP_RETCODE	SCIPconsSdpCheckSdpCons (SCIP scip, SCIP_CONS cons, SCIP_SOL sol, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_RESULT result)

EXTERN SCIP_RETCODE	SCIPconsSdpGuessInitialPoint (SCIP scip, SCIP_CONS cons, SCIP_Real *lambdastar)

EXTERN SCIP_Real	SCIPconsSdpGetMaxConstEntry (SCIP scip, SCIP_CONS cons)

EXTERN SCIP_Real	SCIPconsSdpGetMaxSdpCoef (SCIP scip, SCIP_CONS cons)

EXTERN int	SCIPconsSdpComputeUbSparseSdpMatrixLength (SCIP scip, SCIP_CONS cons)

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

Detailed Description

Constraint handler for SDP-constraints.

Author: Sonja Mars; Lars Schewe; Tristan Gally

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.

Definition in file cons_sdp.h.

Function Documentation

EXTERN SCIP_RETCODE SCIPincludeConshdlrSdp ( SCIP * scip )

creates the handler for SDP constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2448 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, and DEFAULT_DIAGZEROIMPLCUTS.

Referenced by runSCIP(), and SCIP_DECL_CONSHDLRCOPY().

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

References setMaxRhsEntry().

Referenced by SCIP_DECL_CONSCOPY(), scip::ObjReaderSDPAind::scip_read(), and scip::ObjReaderSDPA::scip_read().

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

Referenced by calcRelax(), computeSdpMatrix(), diagGEzero(), expandSymMatrix(), and SCIPconsSdpGetLowerTriangConstMatrix().

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

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

Definition at line 2518 of file cons_sdp.c.

References name.

Referenced by calcRelax(), and putSdpDataInInterface().

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

Referenced by calcRelax(), and putSdpDataInInterface().

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

Referenced by calcRelax(), and SCIPrelaxSdpComputeAnalyticCenters().

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

Referenced by SCIP_DECL_CONSLOCK().

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

Referenced by cutUsingEigenvector().

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

References SCIPconsSdpCompLowerTriangPos().

Referenced by diagGEzero().

EXTERN 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 constraint

Parameters

scip	SCIP data structure
cons	the constraint the solution should be checked for
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 341 of file cons_sdp.c.

References computeSdpMatrix(), expandSymMatrix(), and SCIPlapackComputeIthEigenvalue().

Referenced by EnforceConstraint(), SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOPS().

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

References CONSHDLR_NAME.

Referenced by SCIP_DECL_RELAXINITSOL().

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

Referenced by SCIP_DECL_RELAXINITSOL().

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

Referenced by SCIP_DECL_RELAXINITSOL().

EXTERN int SCIPconsSdpComputeUbSparseSdpMatrixLength	(	SCIP *	scip,
		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

scip	SCIP data structure
cons	the constraint for which the Matrix should be assembled

Definition at line 2910 of file cons_sdp.c.

Referenced by calcRelax(), and SCIPrelaxSdpComputeAnalyticCenters().

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

References SCIPsdpVarfixerMergeArrays().

Referenced by calcRelax(), and SCIPrelaxSdpComputeAnalyticCenters().

Functions

Detailed Description

Function Documentation