relax_sdp.c File Reference

SDP-relaxator. More...

Go to the source code of this file.

Macros
#define	RELAX_NAME   "SDP"
#define	RELAX_DESC   "SDP-relaxator"
#define	RELAX_PRIORITY   1
#define	RELAX_FREQ   1
#define	DEFAULT_SDPSOLVEREPSILON   1e-4
#define	DEFAULT_SDPSOLVERFEASTOL   1e-6
#define	DEFAULT_PENALTYPARAM   -1.0
#define	DEFAULT_LAMBDASTAR   -1.0
#define	DEFAULT_MAXPENALTYPARAM   -1.0
#define	DEFAULT_SLATERCHECK   0
#define	DEFAULT_OBJLIMIT   FALSE
#define	DEFAULT_RESOLVE   TRUE
#define	DEFAULT_TIGHTENVB   FALSE
#define	DEFAULT_SDPINFO   FALSE
#define	DEFAULT_DISPLAYSTAT   TRUE
#define	DEFAULT_SETTINGSRESETFREQ   -1
#define	DEFAULT_SETTINGSRESETOFS   0

Functions
static SCIP_RETCODE	putSdpDataInInterface (SCIP *scip, SCIP_SDPI *sdpi, SdpVarmapper *varmapper)
static SCIP_RETCODE	putLpDataInInterface (SCIP *scip, SCIP_SDPI *sdpi, SdpVarmapper *varmapper)
static SCIP_RETCODE	calcRelax (SCIP *scip, SCIP_RELAXDATA *relaxdata, SCIP_RESULT *result, SCIP_Real *lowerbound)
static SCIP_Bool	allVarsFixed (SCIP *scip)
static	SCIP_DECL_RELAXEXEC (relaxExecSdp)
static	SCIP_DECL_RELAXINITSOL (relaxInitSolSdp)
static	SCIP_DECL_RELAXCOPY (relaxCopySdp)
static	SCIP_DECL_RELAXEXIT (relaxExitSdp)
static	SCIP_DECL_RELAXFREE (relaxFreeSdp)
SCIP_RETCODE	SCIPincludeRelaxSdp (SCIP *scip)
SCIP_RETCODE	SCIPrelaxSdpGetPrimalBoundVars (SCIP_RELAX *relax, SCIP_Real *lbvars, SCIP_Real *ubvars, int *arraylength)
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)
long int	SCIPrelaxSdpGetSdpNode (SCIP_RELAX *relax)
SCIP_Bool	SCIPrelaxSdpSolvedOrig (SCIP_RELAX *relax)
SCIP_Bool	SCIPrelaxSdpSolvedProbing (SCIP_RELAX *relax)
SCIP_Bool	SCIPrelaxSdpIsFeasible (SCIP_RELAX *relax)
int	SCIPrelaxSdpGetNIterations (SCIP_RELAX *relax)
int	SCIPrelaxSdpGetNSdpCalls (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)

Detailed Description

SDP-relaxator.

Author

Sonja Mars

Tristan Gally

Definition in file relax_sdp.c.

Macro Definition Documentation

#define RELAX_NAME   "SDP"

Definition at line 59 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXCOPY(), and SCIPincludeRelaxSdp().

#define RELAX_DESC   "SDP-relaxator"

Definition at line 60 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define RELAX_PRIORITY   1

Definition at line 61 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define RELAX_FREQ   1

Definition at line 62 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPSOLVEREPSILON   1e-4

the stopping criterion for the duality gap the sdpsolver should use

Definition at line 66 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPSOLVERFEASTOL   1e-6

the feasibility tolerance the SDP solver should use for the SDP constraints

Definition at line 67 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 68 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 69 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 70 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SLATERCHECK   0

Should the Slater condition be checked ?

Definition at line 71 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 72 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 73 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_TIGHTENVB   FALSE

Should Big-Ms in varbound-like constraints be tightened before giving them to the SDP-solver ?

Definition at line 74 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_SDPINFO   FALSE

Should the SDP solver output information to the screen?

Definition at line 75 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

#define DEFAULT_DISPLAYSTAT   TRUE

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

Definition at line 76 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 77 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 78 of file relax_sdp.c.

Referenced by SCIPincludeRelaxSdp().

Function Documentation

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

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

Definition at line 145 of file relax_sdp.c.

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

Referenced by SCIP_DECL_RELAXINITSOL().

static SCIP_RETCODE putLpDataInInterface ( SCIP *  scip, SCIP_SDPI *  sdpi, SdpVarmapper *  varmapper  )

static

inserts all the LP data (including bounds and objective) 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

Definition at line 338 of file relax_sdp.c.

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

Referenced by SCIP_DECL_RELAXEXEC().

static SCIP_RETCODE calcRelax ( SCIP *  scip, SCIP_RELAXDATA *  relaxdata, SCIP_RESULT *  result, SCIP_Real *  lowerbound  )

static

calculate relaxation and process the relaxation results

Parameters

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

Definition at line 565 of file relax_sdp.c.

References createConsSavedsdpsettings(), SCIP_SDPPAR_OBJLIMIT, SCIP_SDPSLATER_HOLDS, SCIP_SDPSLATER_INF, SCIP_SDPSLATER_NOINFO, SCIP_SDPSLATER_NOT, SCIP_SDPSLATERSETTING_BOUNDEDINFEASIBLE, SCIP_SDPSLATERSETTING_BOUNDEDNOSLATER, SCIP_SDPSLATERSETTING_BOUNDEDWSLATER, SCIP_SDPSLATERSETTING_NOINFO, SCIP_SDPSLATERSETTING_PENALTYINFEASIBLE, SCIP_SDPSLATERSETTING_PENALTYNOSLATER, SCIP_SDPSLATERSETTING_PENALTYWSLATER, SCIP_SDPSLATERSETTING_STABLEINFEASIBLE, SCIP_SDPSLATERSETTING_STABLENOSLATER, SCIP_SDPSLATERSETTING_STABLEWSLATER, SCIP_SDPSLATERSETTING_UNSOLVEDINFEASIBLE, SCIP_SDPSLATERSETTING_UNSOLVEDNOSLATER, SCIP_SDPSLATERSETTING_UNSOLVEDWSLATER, SCIP_SDPSLATERSETTING_UNSTABLEINFEASIBLE, SCIP_SDPSLATERSETTING_UNSTABLENOSLATER, SCIP_SDPSLATERSETTING_UNSTABLEWSLATER, SCIP_SDPSOLVERSETTING_FAST, SCIP_SDPSOLVERSETTING_MEDIUM, SCIP_SDPSOLVERSETTING_PENALTY, SCIP_SDPSOLVERSETTING_STABLE, SCIP_SDPSOLVERSETTING_UNSOLVED, SCIPconsSavedsdpsettingsGetSettings(), SCIPsdpiFeasibilityKnown(), SCIPsdpiGetIterations(), SCIPsdpiGetLowerObjbound(), SCIPsdpiGetSdpCalls(), SCIPsdpiGetSol(), SCIPsdpiInfinity(), SCIPsdpiIsAcceptable(), SCIPsdpiIsDualFeasible(), SCIPsdpiIsDualInfeasible(), SCIPsdpiIsDualUnbounded(), SCIPsdpiIsObjlimExc(), SCIPsdpiIsPrimalFeasible(), SCIPsdpiIsTimelimExc(), SCIPsdpiSetRealpar(), SCIPsdpiSettingsUsed(), SCIPsdpiSlater(), SCIPsdpiSlaterSettings(), SCIPsdpiSolve(), SCIPsdpiSolvedOrig(), SCIPsdpiWasSolved(), and SCIPsdpVarmapperGetSCIPvar().

Referenced by SCIP_DECL_RELAXEXEC().

static SCIP_Bool allVarsFixed ( SCIP *  scip )

static

checks whether all variables are fixed

Parameters

scip	SCIP data structure

Definition at line 1047 of file relax_sdp.c.

Referenced by SCIP_DECL_RELAXEXEC().

static SCIP_DECL_RELAXEXEC ( relaxExecSdp  )

static

execution method of relaxator

Definition at line 1071 of file relax_sdp.c.

References allVarsFixed(), calcRelax(), putLpDataInInterface(), SCIPsdpiGetSol(), and SCIPsdpiIsDualUnbounded().

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 1252 of file relax_sdp.c.

References putSdpDataInInterface(), SCIP_SDPPAR_EPSILON, SCIP_SDPPAR_FEASTOL, SCIP_SDPPAR_LAMBDASTAR, SCIP_SDPPAR_MAXPENALTYPARAM, SCIP_SDPPAR_PENALTYPARAM, SCIP_SDPPAR_SDPINFO, SCIP_SDPPAR_SLATERCHECK, SCIPconsSdpGuessInitialPoint(), SCIPsdpiComputeLambdastar(), SCIPsdpiComputeMaxPenaltyparam(), SCIPsdpiComputePenaltyparam(), SCIPsdpiGetSolverName(), SCIPsdpiSetIntpar(), SCIPsdpiSetRealpar(), SCIPsdpVarmapperAddVars(), and SCIPsdpVarmapperCreate().

static SCIP_DECL_RELAXCOPY ( relaxCopySdp  )

static

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

Definition at line 1492 of file relax_sdp.c.

References RELAX_NAME, and SCIPincludeRelaxSdp().

static SCIP_DECL_RELAXEXIT ( relaxExitSdp  )

static

reset the relaxator's data

Definition at line 1505 of file relax_sdp.c.

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

static SCIP_DECL_RELAXFREE ( relaxFreeSdp  )

static

free the relaxator's data

Definition at line 1629 of file relax_sdp.c.

References SCIPsdpiFree().

SCIP_RETCODE SCIPincludeRelaxSdp

(

SCIP *

scip

)

creates the SDP-relaxator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1649 of file relax_sdp.c.

References DEFAULT_DISPLAYSTAT, DEFAULT_LAMBDASTAR, DEFAULT_MAXPENALTYPARAM, DEFAULT_OBJLIMIT, DEFAULT_PENALTYPARAM, DEFAULT_RESOLVE, DEFAULT_SDPINFO, DEFAULT_SDPSOLVEREPSILON, DEFAULT_SDPSOLVERFEASTOL, DEFAULT_SETTINGSRESETFREQ, DEFAULT_SETTINGSRESETOFS, DEFAULT_SLATERCHECK, DEFAULT_TIGHTENVB, RELAX_DESC, RELAX_FREQ, RELAX_NAME, RELAX_PRIORITY, SCIPsdpiCreate(), SCIPsdpiGetSolverDesc(), and SCIPsdpiGetSolverName().

Referenced by runSCIP(), and SCIP_DECL_RELAXCOPY().

SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars	(	SCIP_RELAX *	relax,
		SCIP_Real *	lbvars,
		SCIP_Real *	ubvars,
		int *	arraylength
	)

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

The last input should specify the length of the arrays. If this is less than the number of variables, the needed length will be returned and a debug message thrown.

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

relax	SDP-relaxator to get information for
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
arraylength	input: length of lbvars and ubvars output: number of elements inserted into lbvars/ubvars (or needed length if it wasn't sufficient)

Definition at line 1749 of file relax_sdp.c.

References SCIPsdpiGetPrimalBoundVars().

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 1774 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 1796 of file relax_sdp.c.

References SCIPsdpiGetSol().

long int SCIPrelaxSdpGetSdpNode

(

SCIP_RELAX *

relax

)

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

Parameters

relax

SDP-relaxator to get solution for

Definition at line 1829 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 1840 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 1857 of file relax_sdp.c.

Referenced by 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 1874 of file relax_sdp.c.

Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_PROPEXEC().

int SCIPrelaxSdpGetNIterations

(

SCIP_RELAX *

relax

)

returns total number of SDP-iterations

Parameters

relax

SDP-relaxator to get the iterations for

Definition at line 1885 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT().

int SCIPrelaxSdpGetNSdpCalls

(

SCIP_RELAX *

relax

)

returns number of solved SDP-relaxations

Parameters

relax

SDP-relaxator to get the number of calls for

Definition at line 1896 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT().

int SCIPrelaxSdpGetNSdpFast

(

SCIP_RELAX *

relax

)

returns number of SDP-relaxations solved with fast settings

Parameters

relax

SDP-relaxator to get the number of calls for

Definition at line 1907 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT().

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 1918 of file relax_sdp.c.

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 1929 of file relax_sdp.c.

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 1940 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT().

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 1951 of file relax_sdp.c.

Referenced by SCIP_DECL_DISPOUTPUT().