SDP-relaxator. More...

Macros
#define	SLATERSOLVED_ABSOLUTE /* uncomment this to return the absolute number of nodes for, e.g., solved fast with slater in addition to percentages */

#define	RELAX_NAME "SDP"

#define	RELAX_DESC "SDP-relaxator"

#define	RELAX_PRIORITY 1

#define	RELAX_FREQ 1

#define	DEFAULT_SDPSOLVERFEASTOL 1e-5

#define	DEFAULT_SDPSOLVERGAPTOL 1e-5

#define	DEFAULT_PENALTYPARAM -1.0

#define	DEFAULT_LAMBDASTAR -1.0

#define	DEFAULT_MAXPENALTYPARAM -1.0

#define	DEFAULT_WARMSTARTIPFACTOR 0.50

#define	DEFAULT_WARMSTARTPRIMALTYPE 3

#define	DEFAULT_WARMSTARTIPTYPE 1

#define	DEFAULT_WARMSTARTPROJECT 2

#define	DEFAULT_WARMSTARTPROJMINEV -1.0

#define	DEFAULT_WARMSTARTPROJPDSAME TRUE

#define	DEFAULT_WARMSTART_PREOPTIMAL_SOL FALSE

#define	DEFAULT_WARMSTARTPREOPTGAP 1e-2

#define	DEFAULT_WARMSTARTROUNDONLYINF FALSE

#define	DEFAULT_SLATERCHECK 0

#define	DEFAULT_OBJLIMIT FALSE

#define	DEFAULT_RESOLVE TRUE

#define	DEFAULT_TIGHTENROWS TRUE

#define	DEFAULT_SDPINFO FALSE

#define	DEFAULT_WARMSTART FALSE

#define	DEFAULT_DISPLAYSTAT FALSE

#define	DEFAULT_SETTINGSRESETFREQ -1

#define	DEFAULT_SETTINGSRESETOFS 0

#define	DEFAULT_SDPSOLVERTHREADS 1

#define	DEFAULT_PENINFEASADJUST 10.0

#define	DEFAULT_USEPRESOLVING FALSE

#define	DEFAULT_USESCALING TRUE

#define	DEFAULT_SCALEOBJ FALSE

#define	WARMSTART_MINVAL 0.01

#define	WARMSTART_PROJ_MINRHSOBJ 1

#define	WARMSTART_PROJ_FACTOR 0.1

#define	WARMSTART_PROJ_FACTOR_LHS 10

#define	WARMSTART_PROJ_FACTOR_PRIMAL 0.1

#define	WARMSTART_PREOPT_MIN_Z_LPVAL 0.01

Functions
static SCIP_RETCODE	expandSparseMatrix (int nnonz, int blocksize, int row, int col, SCIP_Real val, SCIP_Real fullmat)

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

static SCIP_RETCODE	updateSDPStatistics (SCIP_RELAXDATA *relaxdata)

static SCIP_RETCODE	putSdpDataInInterface (SCIP scip, SCIP_SDPI sdpi, SdpVarmapper *varmapper, SCIP_Bool primalobj, SCIP_Bool boundprimal)

static SCIP_RETCODE	tightenRowCoefs (SCIP scip, SCIP_Real rowvals, SCIP_COL *rowcols, int rownnonz, SCIP_Real rowlhs, SCIP_Real rowrhs, SCIP_Bool lhsredundant, SCIP_Bool rhsredundant, int *nchgcoefs)

static SCIP_RETCODE	putLpDataInInterface (SCIP scip, SCIP_RELAXDATA relaxdata, SCIP_Bool primalobj, SCIP_Bool dualobj)

static SCIP_RETCODE	calcRelax (SCIP scip, SCIP_RELAX relax, SCIP_RESULT result, SCIP_Real lowerbound)

static	SCIP_DECL_RELAXEXEC (relaxExecSdp)

static	SCIP_DECL_RELAXINIT (relaxInitSdp)

static	SCIP_DECL_RELAXINITSOL (relaxInitSolSdp)

static	SCIP_DECL_RELAXCOPY (relaxCopySdp)

static	SCIP_DECL_RELAXEXITSOL (relaxExitSolSdp)

static	SCIP_DECL_RELAXEXIT (relaxExitSdp)

static	SCIP_DECL_RELAXFREE (relaxFreeSdp)

static	SCIP_DECL_PARAMCHGD (SCIPparamChgdSolvesdps)

SCIP_RETCODE	SCIPincludeRelaxSdp (SCIP *scip)

SCIP_RETCODE	SCIPrelaxSdpComputeAnalyticCenters (SCIP scip, SCIP_RELAX relax)

SCIP_RETCODE	SCIPrelaxSdpGetPrimalBoundVars (SCIP scip, SCIP_RELAX relax, SCIP_VAR *vars, int nvars, SCIP_Real lbvars, SCIP_Real ubvars, SCIP_Bool success)

SCIP_RETCODE	SCIPrelaxSdpRelaxVal (SCIP_RELAX relax, SCIP_Bool success, SCIP_Real *objval)

SCIP_RETCODE	SCIPrelaxSdpGetRelaxSol (SCIP scip, SCIP_RELAX relax, SCIP_Bool success, SCIP_Real solarray, int *sollength)

SCIP_Longint	SCIPrelaxSdpGetSdpNode (SCIP_RELAX *relax)

SCIP_Bool	SCIPrelaxSdpSolvedOrig (SCIP_RELAX *relax)

SCIP_Bool	SCIPrelaxSdpSolvedProbing (SCIP_RELAX *relax)

SCIP_Bool	SCIPrelaxSdpIsFeasible (SCIP_RELAX *relax)

SCIP_Bool	SCIPrelaxSdpIsUnbounded (SCIP_RELAX *relax)

SCIP_Real	SCIPrelaxSdpGetOptTime (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNIterations (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpCalls (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpInterfaceCalls (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpFast (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpMedium (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpStable (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpPenalty (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSdpUnsolved (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNdualSlaterHolds (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNdualSlaterFails (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNdualSlaterInfeasible (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNdualSlaterUnknown (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNprimalSlaterHolds (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNprimalSlaterFails (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNprimalSlaterUnknown (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHolds (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHoldsFast (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHoldsStable (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHoldsPenalty (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHoldsBounded (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterHoldsUnsolved (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFails (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFailsFast (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFailsStable (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFailsPenalty (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFailsBounded (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterFailsUnsolved (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterInfeasibleFast (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterInfeasibleStable (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterInfeasiblePenalty (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterInfeasibleBounded (SCIP_RELAX *relax)

int	SCIPrelaxSdpGetNSlaterInfeasibleUnsolved (SCIP_RELAX *relax)

SCIP_Real	SCIPrelaxSdpGetSolvingTime (SCIP scip, SCIP_RELAX relax)

SCIP_RETCODE	SCIPrelaxSdpGetStatistics (SCIP_RELAX relax, int ninfeasible, int nallfixed, int nonevarsdp)

Detailed Description

SDP-relaxator.

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

Definition in file relax_sdp.c.

Macro Definition Documentation

#define SLATERSOLVED_ABSOLUTE /* uncomment this to return the absolute number of nodes for, e.g., solved fast with slater in addition to percentages */

Definition at line 47 of file relax_sdp.c.

#define RELAX_NAME "SDP"

Definition at line 65 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXCOPY(), and SCIPincludeRelaxSdp().

#define RELAX_DESC "SDP-relaxator"

Definition at line 66 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define RELAX_PRIORITY 1

Definition at line 67 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define RELAX_FREQ 1

Definition at line 68 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPSOLVERFEASTOL 1e-5

default feasibility tolerance of SDP solver

Definition at line 71 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPSOLVERGAPTOL 1e-5

default feasibility tolerance of SDP solver

Definition at line 72 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_PENALTYPARAM -1.0

the penalty parameter Gamma used for the penalty formulation if the SDP solver didn't converge

Definition at line 74 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_LAMBDASTAR -1.0

the parameter lambda star used by SDPA to set the initial point

Definition at line 75 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_MAXPENALTYPARAM -1.0

the penalty parameter Gamma used for the penalty formulation if the SDP solver didn't converge

Definition at line 76 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTIPFACTOR 0.50

factor for interior point in convexcombination of IP and parent solution, if warmstarts are enabled

Definition at line 77 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTPRIMALTYPE 3

how to warmstart the primal problem? 1: scaled identity, 2: elementwise reciprocal, 3: saved primal sol

Definition at line 78 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTIPTYPE 1

which interior point to use for convex combination for warmstarts? 1: scaled identity, 2: analytic center

Definition at line 79 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTPROJECT 2

how to update dual matrix for new bounds? 1: use old bounds, 2: use new bounds, 3: use new bounds and project on psd cone, 4: use new bounds and solve rounding problem

Definition at line 80 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTPROJMINEV -1.0

minimum eigenvector to allow when projecting onto the positive (semi-)definite cone

Definition at line 81 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTPROJPDSAME TRUE

Should one shared minimum eigenvalue be computed for primal and dual problem instead of different ones if warmstartpmevpar = -1 ?

Definition at line 82 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTART_PREOPTIMAL_SOL FALSE

Should a preoptimal solution (with larger gap) instead of the optimal solution be used for warmstarts (currently only implemented fo DSDP)

Definition at line 83 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTPREOPTGAP 1e-2

If warmstartpreoptimalsol is TRUE, this is the gap where the preoptimal solution is saved (currently only implemented fo DSDP)

Definition at line 84 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTARTROUNDONLYINF FALSE

Only use solution of roundingproblem to detect infeasibility (only has an effect for warmstartproject = 4)

Definition at line 85 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SLATERCHECK 0

Should the Slater condition be checked ?

Definition at line 86 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_OBJLIMIT FALSE

Should an objective limit be given to the SDP-Solver ?

Definition at line 87 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_RESOLVE TRUE

Are we allowed to solve the relaxation of a single node multiple times in a row (outside of probing) ?

Definition at line 88 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_TIGHTENROWS TRUE

Should we perform coefficient tightening on the LP rows before giving them to the SDP-solver?

Definition at line 89 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPINFO FALSE

Should the SDP solver output information to the screen?

Definition at line 90 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_WARMSTART FALSE

Should the SDP solver try to use warmstarts?

Definition at line 91 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_DISPLAYSTAT FALSE

Should statistics about SDP iterations and solver settings/success be printed after quitting SCIP-SDP ?

Definition at line 92 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SETTINGSRESETFREQ -1

frequency for resetting parameters in SDP solver and trying again with fastest settings

Definition at line 93 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SETTINGSRESETOFS 0

frequency offset for resetting parameters in SDP solver and trying again with fastest settings

Definition at line 94 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPSOLVERTHREADS 1

number of threads the SDP solver should use (-1 = number of cores)

Definition at line 95 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_PENINFEASADJUST 10.0

gap- or feastol will be multiplied by this before checking for infeasibility using the penalty formulation

Definition at line 96 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_USEPRESOLVING FALSE

whether presolving of SDP-solver should be used

Definition at line 97 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_USESCALING TRUE

whether the SDP-solver should use scaling

Definition at line 98 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SCALEOBJ FALSE

whether the objective should be scaled in order to get a more stable behavior

Definition at line 99 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define WARMSTART_MINVAL 0.01

if we get a value less than this when warmstarting (currently only for the linear part when combining with analytic center), the value is set to this

Definition at line 101 of file relax_sdp.c.

Referenced by calcRelax().

#define WARMSTART_PROJ_MINRHSOBJ 1

minimum value for rhs/obj when computing minimum eigenvalue for warmstart-projection

Definition at line 102 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXINITSOL().

#define WARMSTART_PROJ_FACTOR 0.1

factor to multiply maximum rhs/obj/coef with when computing minimum eigenvalue for warmstart-projection

Definition at line 103 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXINITSOL().

#define WARMSTART_PROJ_FACTOR_LHS 10

factor to multiply maximum SDP coefficient with before applying WARMSTART_PROJ_FACTOr (to account for summation of lhs entries)

Definition at line 104 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXINITSOL().

#define WARMSTART_PROJ_FACTOR_PRIMAL 0.1

factor to multiply maximum obj with when computing minimum eigenvalue for warmstart-projection in the primal

Definition at line 105 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXINITSOL().

#define WARMSTART_PREOPT_MIN_Z_LPVAL 0.01

minimal (diagonal) entry for LP block of dual matrix for preoptimal warmstarts

Definition at line 106 of file relax_sdp.c.

Referenced by calcRelax().

Function Documentation

static SCIP_RETCODE expandSparseMatrix	(	int	nnonz,
		int	blocksize,
		int *	row,
		int *	col,
		SCIP_Real *	val,
		SCIP_Real *	fullmat
	)

static

expand sparse matrix to full matrix format needed by LAPACK

Parameters

nnonz	number of nonzeros and length of row/col/val arrays
blocksize	size of matrix (and squareroot of memory allocated for fullmat)
row	row indices
col	column indices
val	values
fullmat	pointer to store full matrix

Definition at line 225 of file relax_sdp.c.

Referenced by calcRelax().

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

static

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

Parameters

blocksize	number of rows and columns
matrix	matrix entries given as blocksize^2 array
scale	array of length blocksize to multiply the columns of matrix with

Definition at line 262 of file relax_sdp.c.

Referenced by calcRelax().

static SCIP_RETCODE updateSDPStatistics ( SCIP_RELAXDATA * relaxdata )

static

update SDP statistics after calling SCIPsdpiSolve()

Parameters

relaxdata relaxator data

Definition at line 288 of file relax_sdp.c.

Referenced by calcRelax(), and SCIPrelaxSdpComputeAnalyticCenters().

static SCIP_RETCODE putSdpDataInInterface	(	SCIP *	scip,
		SCIP_SDPI *	sdpi,
		SdpVarmapper *	varmapper,
		SCIP_Bool	primalobj,
		SCIP_Bool	boundprimal
	)

static

inserts all the SDP data into the corresponding SDP Interface

Parameters

scip	SCIP data structure
sdpi	SDP interface structure
varmapper	maps SCIP variables to their global SDP indices and vice versa
primalobj	should the primal objective coefficients (constant part of the SDP constraint) be used ?
boundprimal	should the primal problem be bounded (Tr(X)<=1) through a penalty term in the dual ?

Definition at line 490 of file relax_sdp.c.

References SCIPconsSdpGetData(), SCIPconsSdpGetNNonz(), SCIPsdpiLoadSDP(), SCIPsdpVarmapperGetNVars(), and SCIPsdpVarmapperGetSdpIndex().

Referenced by SCIP_DECL_RELAXEXEC(), SCIP_DECL_RELAXINITSOL(), and SCIPrelaxSdpComputeAnalyticCenters().

static SCIP_RETCODE tightenRowCoefs	(	SCIP *	scip,
		SCIP_Real *	rowvals,
		SCIP_COL **	rowcols,
		int *	rownnonz,
		SCIP_Real *	rowlhs,
		SCIP_Real *	rowrhs,
		SCIP_Bool *	lhsredundant,
		SCIP_Bool *	rhsredundant,
		int *	nchgcoefs
	)

static

tightens the coefficients of the given row based on the maximal activity

See cons_linear.c:consdataTightenCoefs() and cuts.c:SCIPcutsTightenCoefficients() for details. The speed can possibly be improved by sorting the coefficients - see cuts.c:SCIPcutsTightenCoefficients().

Following the dissertation of Achterberg (Algorithm 10.1, page 134), the formulas for tightening a linear constraint \( \underline{\beta} \leq a^T x \leq \overline{\beta} \) are as follows:

\begin{align*} & \text{For all } j \in I \text{ with } a_j > 0,\; \underline{\alpha} + a_j \geq \underline{\beta}, \text{ and } \overline{\alpha} - a_j \leq \overline{\beta}:\\ & a'_j := \max \{ \underline{\beta} - \underline{\alpha},\; \overline{\alpha} - \overline{\beta} \};\\ & \underline{\beta} := \underline{\beta} - (a_j - a'_j) \ell_j,\quad \overline{\beta} := \overline{\beta} - (a_j - a'_j) u_j;\\ & a_j := a'_j.\\[2ex] & \text{For all } j \in I \text{ with } a_j < 0,\; \underline{\alpha} - a_j \geq \underline{\beta}, \text{ and } \overline{\alpha} + a_j \leq \overline{\beta}: \\ & a'_j := \min \{\underline{\alpha} - \underline{\beta},\; \overline{\beta} - \overline{\alpha} \};\\ & \underline{\beta} := \underline{\beta} - (a_j - a'_j) u_j,\quad \overline{\beta} := \overline{\beta} - (a_j - a'_j) \ell_j;\\ & a_j := a'_j. \end{align*}

where \(\underline{\alpha}\) and \(\overline{\alpha}\) are the minimal and maximal activities.

Parameters

scip	SCIP data structure
rowvals	nonzero coefficients in row
rowcols	columns of row
rownnonz	pointer to store the number of nonzero coefficients
rowlhs	lhs of row
rowrhs	rhs of row
lhsredundant	pointer to store whether lhs of row is redundant
rhsredundant	pointer to store whether rhs of row is redundant
nchgcoefs	pointer to count total number of changed coefficients

Definition at line 756 of file relax_sdp.c.

Referenced by putLpDataInInterface().

static SCIP_RETCODE putLpDataInInterface	(	SCIP *	scip,
		SCIP_RELAXDATA *	relaxdata,
		SCIP_Bool	primalobj,
		SCIP_Bool	dualobj
	)

static

inserts all the LP data (including bounds and objective) into the corresponding SDP Interface

Parameters

scip	SCIP data structure
relaxdata	relaxator data
primalobj	Should the primal objective coefficients (lhs/rhs of LP-constraints) be used?
dualobj	Should the dual objective coefficients be used?

Definition at line 1049 of file relax_sdp.c.

References SCIPsdpiAddLPRows(), SCIPsdpiChgBounds(), SCIPsdpiChgObj(), SCIPsdpiDelLPRows(), SCIPsdpiGetNLPRows(), SCIPsdpVarmapperGetSdpIndex(), and tightenRowCoefs().

Referenced by SCIP_DECL_RELAXEXEC(), and SCIPrelaxSdpComputeAnalyticCenters().

static SCIP_RETCODE calcRelax	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_RESULT *	result,
		SCIP_Real *	lowerbound
	)

static

calculate relaxation and process the relaxation results

Parameters

scip	SCIP data structure
relax	relaxator
result	pointer to store result of relaxation process
lowerbound	pointer to store lowerbound

Definition at line 1258 of file relax_sdp.c.

References createConsSavedsdpsettings(), createConsSavesdpsol(), expandSparseMatrix(), scaleTransposedMatrix(), SCIP_SDPPAR_OBJLIMIT, SCIP_SDPSOLVERSETTING_UNSOLVED, SCIPconsSavedsdpsettingsGetSettings(), SCIPconsSavesdpsolGetDualVector(), SCIPconsSavesdpsolGetMaxPrimalEntry(), SCIPconsSavesdpsolGetNodeIndex(), SCIPconsSavesdpsolGetPrimalMatrix(), SCIPconsSavesdpsolGetPrimalMatrixNonzeros(), SCIPconsSdpCompLowerTriangPos(), SCIPconsSdpComputeSparseSdpMatrix(), SCIPconsSdpComputeUbSparseSdpMatrixLength(), SCIPconsSdpGetBlocksize(), SCIPconsSdpGetData(), SCIPconsSdpGetNNonz(), SCIPlapackComputeEigenvectorDecomposition(), SCIPlapackMatrixMatrixMult(), SCIPsdpiClockSetType(), SCIPsdpiDoesWarmstartNeedPrimal(), SCIPsdpiFeasibilityKnown(), SCIPsdpiGetLowerObjbound(), SCIPsdpiGetMaxPrimalEntry(), SCIPsdpiGetPreoptimalPrimalNonzeros(), SCIPsdpiGetPreoptimalSol(), SCIPsdpiGetPrimalMatrix(), SCIPsdpiGetPrimalNonzeros(), SCIPsdpiGetSol(), SCIPsdpiGetSolverName(), SCIPsdpiInfinity(), SCIPsdpiIsAcceptable(), SCIPsdpiIsDualFeasible(), SCIPsdpiIsDualInfeasible(), SCIPsdpiIsDualUnbounded(), SCIPsdpiIsObjlimExc(), SCIPsdpiIsOptimal(), SCIPsdpiIsPrimalFeasible(), SCIPsdpiIsTimelimExc(), SCIPsdpiSetRealpar(), SCIPsdpiSettingsUsed(), SCIPsdpiSolve(), SCIPsdpiSolvedOrig(), SCIPsdpiWasSolved(), SCIPsdpVarfixerMergeArrays(), SCIPsdpVarmapperGetNVars(), SCIPsdpVarmapperGetSCIPvar(), SCIPsdpVarmapperGetSdpIndex(), updateSDPStatistics(), WARMSTART_MINVAL, and WARMSTART_PREOPT_MIN_Z_LPVAL.

Referenced by SCIP_DECL_RELAXEXEC().

static SCIP_DECL_RELAXEXEC ( relaxExecSdp )

static

execution method of relaxator

Definition at line 3826 of file relax_sdp.c.

References calcRelax(), putLpDataInInterface(), putSdpDataInInterface(), SCIPsdpiGetNSDPBlocks(), SCIPsdpiGetSol(), SCIPsdpiIsDualUnbounded(), SCIPsdpVarmapperAddVars(), SCIPsdpVarmapperExistsSCIPvar(), and SCIPsdpVarmapperGetNVars().

static SCIP_DECL_RELAXINIT ( relaxInitSdp )

static

initialization method of relaxator (called after problem was transformed)

Definition at line 3985 of file relax_sdp.c.

static SCIP_DECL_RELAXINITSOL ( relaxInitSolSdp )

static

this method is called after presolving is finished, at this point the varmapper is prepared and the SDP Interface is initialized and gets the SDP information from the constraints

Definition at line 4002 of file relax_sdp.c.

References putSdpDataInInterface(), SCIP_SDPPAR_EPSILON, SCIP_SDPPAR_FEASTOL, SCIP_SDPPAR_GAPTOL, SCIP_SDPPAR_LAMBDASTAR, SCIP_SDPPAR_MAXPENALTYPARAM, SCIP_SDPPAR_NPENALTYINCR, SCIP_SDPPAR_NTHREADS, SCIP_SDPPAR_OBJLIMIT, SCIP_SDPPAR_PENALTYPARAM, SCIP_SDPPAR_PENINFEASADJUST, SCIP_SDPPAR_SCALEOBJ, SCIP_SDPPAR_SDPINFO, SCIP_SDPPAR_SDPSOLVERFEASTOL, SCIP_SDPPAR_SLATERCHECK, SCIP_SDPPAR_USEPRESOLVING, SCIP_SDPPAR_USESCALING, SCIP_SDPPAR_WARMSTARTPOGAP, SCIPconsSdpGetMaxConstEntry(), SCIPconsSdpGetMaxSdpCoef(), SCIPconsSdpGuessInitialPoint(), SCIPsdpiComputeLambdastar(), SCIPsdpiComputeMaxPenaltyparam(), SCIPsdpiComputePenaltyparam(), SCIPsdpiGetRealpar(), SCIPsdpiGetSolverName(), SCIPsdpiInfinity(), SCIPsdpiSetIntpar(), SCIPsdpiSetRealpar(), SCIPsdpVarmapperAddVars(), SCIPsdpVarmapperCreate(), WARMSTART_PROJ_FACTOR, WARMSTART_PROJ_FACTOR_LHS, WARMSTART_PROJ_FACTOR_PRIMAL, and WARMSTART_PROJ_MINRHSOBJ.

static SCIP_DECL_RELAXCOPY ( relaxCopySdp )

static

copy method for SDP-relaxation handler (called when SCIP copies plugins)

Definition at line 4506 of file relax_sdp.c.

References RELAX_NAME, and SCIPincludeRelaxSdp().

static SCIP_DECL_RELAXEXITSOL ( relaxExitSolSdp )

static

reset the relaxator's data

Definition at line 4519 of file relax_sdp.c.

References SCIPsdpiClear(), SCIPsdpiDoesWarmstartNeedPrimal(), SCIPsdpiGetSolverName(), and SCIPsdpVarmapperFree().

static SCIP_DECL_RELAXEXIT ( relaxExitSdp )

static

deinitialization method of relaxator (called before transformed problem is freed)

Definition at line 4714 of file relax_sdp.c.

static SCIP_DECL_RELAXFREE ( relaxFreeSdp )

static

free the relaxator's data

Definition at line 4733 of file relax_sdp.c.

References SCIPsdpiFree().

static SCIP_DECL_PARAMCHGD ( SCIPparamChgdSolvesdps )

static

callback function to adapt further parameters once changed

Definition at line 4762 of file relax_sdp.c.

SCIP_RETCODE SCIPincludeRelaxSdp ( SCIP * scip )

creates the SDP-relaxator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 4834 of file relax_sdp.c.

References DEFAULT_DISPLAYSTAT, DEFAULT_LAMBDASTAR, DEFAULT_MAXPENALTYPARAM, DEFAULT_OBJLIMIT, DEFAULT_PENALTYPARAM, DEFAULT_PENINFEASADJUST, DEFAULT_RESOLVE, DEFAULT_SCALEOBJ, DEFAULT_SDPINFO, DEFAULT_SDPSOLVERFEASTOL, DEFAULT_SDPSOLVERGAPTOL, DEFAULT_SDPSOLVERTHREADS, DEFAULT_SETTINGSRESETFREQ, DEFAULT_SETTINGSRESETOFS, DEFAULT_SLATERCHECK, DEFAULT_TIGHTENROWS, DEFAULT_USEPRESOLVING, DEFAULT_USESCALING, DEFAULT_WARMSTART, DEFAULT_WARMSTART_PREOPTIMAL_SOL, DEFAULT_WARMSTARTIPFACTOR, DEFAULT_WARMSTARTIPTYPE, DEFAULT_WARMSTARTPREOPTGAP, DEFAULT_WARMSTARTPRIMALTYPE, DEFAULT_WARMSTARTPROJECT, DEFAULT_WARMSTARTPROJMINEV, DEFAULT_WARMSTARTPROJPDSAME, DEFAULT_WARMSTARTROUNDONLYINF, RELAX_DESC, RELAX_FREQ, RELAX_NAME, RELAX_PRIORITY, SCIPsdpiCreate(), SCIPsdpiGetDefaultSdpiSolverNpenaltyIncreases(), SCIPsdpiGetSolverDesc(), and SCIPsdpiGetSolverName().

Referenced by SCIP_DECL_RELAXCOPY(), and SCIPSDPincludeDefaultPlugins().

SCIP_RETCODE SCIPrelaxSdpComputeAnalyticCenters	(	SCIP *	scip,
		SCIP_RELAX *	relax
	)

computes analytic centers of primal and dual feasible set and saves them in relaxdata

Note: This function should be called at the end of the root node (or at least after the solving stage starts and before the first non-root node).

Parameters

scip	SCIP data structure
relax	SDP-relaxator to compute analytic centers for

Definition at line 5015 of file relax_sdp.c.

References putLpDataInInterface(), putSdpDataInInterface(), SCIP_SDPSOLVERSETTING_UNSOLVED, SCIPconsSdpComputeSparseSdpMatrix(), SCIPconsSdpComputeUbSparseSdpMatrixLength(), SCIPconsSdpGetBlocksize(), SCIPsdpiClockSetType(), SCIPsdpiDoesWarmstartNeedPrimal(), SCIPsdpiGetPrimalMatrix(), SCIPsdpiGetPrimalNonzeros(), SCIPsdpiGetSol(), SCIPsdpiIsDualFeasible(), SCIPsdpiIsPrimalFeasible(), SCIPsdpiSolve(), SCIPsdpiSolvedOrig(), SCIPsdpiWasSolved(), SCIPsdpVarfixerSortRowCol(), SCIPsdpVarmapperGetNVars(), and updateSDPStatistics().

Referenced by SCIP_DECL_PROPEXEC().

SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_VAR **	vars,
		int	nvars,
		SCIP_Real *	lbvars,
		SCIP_Real *	ubvars,
		SCIP_Bool *	success
	)

gets the primal variables corresponding to the lower and upper variable-bounds in the dual problem

Note: If a variable is either fixed or unbounded in the dual problem, a zero will be returned for the non-existent primal variable.

Parameters

scip	SCIP datastructure
relax	SDP-relaxator to get information for
vars	variables to get bounds for
nvars	number of variables
lbvars	pointer to store the values of the variables corresponding to lower bounds in the dual problems
ubvars	pointer to store the values of the variables corresponding to upper bounds in the dual problems
success	pointer to store success (may fail if problem is infeasible or all variables are fixed)

Definition at line 5440 of file relax_sdp.c.

References SCIPsdpiGetPrimalBoundVars(), SCIPsdpVarmapperGetNVars(), and SCIPsdpVarmapperGetSdpIndex().

Referenced by SCIP_DECL_PROPEXEC().

SCIP_RETCODE SCIPrelaxSdpRelaxVal	(	SCIP_RELAX *	relax,
		SCIP_Bool *	success,
		SCIP_Real *	objval
	)

returns optimal objective value of the current SDP-relaxation if the last SDP-relaxation was successfully solved

Parameters

relax	SDP-relaxator to get objective value for
success	pointer to store whether the last SDP-relaxation was solved successfully
objval	pointer to store the optimal objective value of the SDP-relaxation

Definition at line 5496 of file relax_sdp.c.

Referenced by SCIP_DECL_PROPEXEC().

SCIP_RETCODE SCIPrelaxSdpGetRelaxSol	(	SCIP *	scip,
		SCIP_RELAX *	relax,
		SCIP_Bool *	success,
		SCIP_Real *	solarray,
		int *	sollength
	)

returns values of all variables in the solution of the current SDP-relaxation if the last SDP-relaxation was successfully solved

Parameters

scip	SCIP pointer
relax	SDP-relaxator to get solution for
success	pointer to store whether the last SDP-relaxation was solved successfully
solarray	pointer to store the solution, this has to be at least length nvars
sollength	length of the solarray

Definition at line 5518 of file relax_sdp.c.

References SCIPsdpiGetSol().

SCIP_Longint SCIPrelaxSdpGetSdpNode ( SCIP_RELAX * relax )

get the number of the SCIP-node which the current SDP solution belongs to

Parameters

relax SDP-relaxator to get solution for

Definition at line 5551 of file relax_sdp.c.

Referenced by SCIP_DECL_PROPEXEC().

SCIP_Bool SCIPrelaxSdpSolvedOrig ( SCIP_RELAX * relax )

Was the original problem solved for the last SDP-node (or a penalty or probing formulation) ?

Parameters

relax SDP-relaxator to get solution for

Definition at line 5562 of file relax_sdp.c.

References SCIPsdpiSolvedOrig().

Referenced by SCIP_DECL_PROPEXEC().

SCIP_Bool SCIPrelaxSdpSolvedProbing ( SCIP_RELAX * relax )

Was the last probing SDP solved successfully ?

Parameters

relax SDP-relaxator to get solution for

Definition at line 5579 of file relax_sdp.c.

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_PROPEXEC().

SCIP_Bool SCIPrelaxSdpIsFeasible ( SCIP_RELAX * relax )

returns whether the last solved problem was feasible

Parameters

relax SDP-relaxator to get feasibility for

Definition at line 5596 of file relax_sdp.c.

Referenced by SCIP_DECL_CONSENFOLP(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_PROPEXEC().

SCIP_Bool SCIPrelaxSdpIsUnbounded ( SCIP_RELAX * relax )

returns whether the last solved problem was unbounded

Parameters

relax SDP-relaxator to check for unboundedness

Definition at line 5607 of file relax_sdp.c.

References SCIPsdpiIsDualUnbounded().

Referenced by SCIP_DECL_PROPEXEC().

SCIP_Real SCIPrelaxSdpGetOptTime ( SCIP_RELAX * relax )

returns time in optimization of solver

Parameters

relax SDP-relaxator to get the iterations for

Definition at line 5624 of file relax_sdp.c.

Referenced by SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNIterations ( SCIP_RELAX * relax )

returns total number of SDP-iterations

Parameters

relax SDP-relaxator to get the iterations for

Definition at line 5635 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpCalls ( SCIP_RELAX * relax )

returns number of SDPs solved by SDP-solver (including multiple calls for penalty formulation etc.)

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5646 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpInterfaceCalls ( SCIP_RELAX * relax )

returns number of solved SDP-relaxations

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5657 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpFast ( SCIP_RELAX * relax )

returns number of SDP-relaxations solved with fastest settings

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5668 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpMedium ( SCIP_RELAX * relax )

returns number of SDP-relaxations solved with medium settings

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5679 of file relax_sdp.c.

Referenced by SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpStable ( SCIP_RELAX * relax )

returns number of SDP-relaxations solved with stable settings

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5690 of file relax_sdp.c.

Referenced by SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpPenalty ( SCIP_RELAX * relax )

returns number of SDP-relaxations solved with penalty formulation

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5701 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNSdpUnsolved ( SCIP_RELAX * relax )

returns number of SDP-relaxations unsolved even when using a penalty formulation

Parameters

relax SDP-relaxator to get the number of calls for

Definition at line 5712 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIP_DECL_TABLEOUTPUT().

int SCIPrelaxSdpGetNdualSlaterHolds ( SCIP_RELAX * relax )

returns number of SDP-relaxations for which dual Slater condition held

Parameters