Detailed Description

constraint handler for second order cone constraints $\sqrt{\gamma + \sum_{i=1}^{n} (\alpha_i\, (x_i + \beta_i))^2} \leq \alpha_{n+1}\, (x_{n+1}+\beta_{n+1})$

Author: Stefan Vigerske

This constraint handler implements second order cone constraints of the form

$\sqrt{\gamma + \sum_{i=1}^{n} (\alpha_i\, (x_i + \beta_i))^2} \leq \alpha_{n+1}\, (x_{n+1}+\beta_{n+1})$

Here, $\gamma \geq 0$ and either $x_{n+1} \geq -\beta_{n+1}, \alpha_{n+1} \geq 0$ or $x_{n+1} \leq -\beta_{n+1}, \alpha_{n+1} \leq 0$ .

Constraints are enforced by separation, where cuts are generated by linearizing the (convex) nonlinear function on the left-hand-side of the constraint. Further, a linear outer-approximation (which includes new variables) based on Ben-Tal & Nemirovski or Glineur can be added. See also

: Timo Berthold and Stefan Heinz and Stefan Vigerske
Extending a CIP framework to solve MIQCPs
In: Jon Lee and Sven Leyffer (eds.), Mixed-integer nonlinear optimization: Algorithmic advances and applications, IMA volumes in Mathematics and its Applications, volume 154, 427-444, 2012.

: Aharon Ben-Tal and Arkadi Nemirovski
On Polyhedral Approximations of the Second-order Cone
Mathematics of Operations Research 26:2, 193-205, 2001

: François Glineur
Computational experiments with a linear approximation of second order cone optimization
Technical Report 2000:1, Faculté Polytechnique de Mons, Belgium

Definition in file cons_soc.h.

#include "scip/scip.h"
#include "nlpi/type_nlpi.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeConshdlrSOC (SCIP *scip)

SCIP_RETCODE	SCIPcreateConsSOC (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, SCIP_Real coefs, SCIP_Real offsets, SCIP_Real constant, SCIP_VAR rhsvar, SCIP_Real rhscoeff, SCIP_Real rhsoffset, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)

SCIP_RETCODE	SCIPcreateConsBasicSOC (SCIP scip, SCIP_CONS cons, const char name, int nvars, SCIP_VAR *vars, SCIP_Real coefs, SCIP_Real offsets, SCIP_Real constant, SCIP_VAR rhsvar, SCIP_Real rhscoeff, SCIP_Real rhsoffset)

SCIP_RETCODE	SCIPgetNlRowSOC (SCIP scip, SCIP_CONS cons, SCIP_NLROW **nlrow)

int	SCIPgetNLhsVarsSOC (SCIP scip, SCIP_CONS cons)

SCIP_VAR **	SCIPgetLhsVarsSOC (SCIP scip, SCIP_CONS cons)

SCIP_Real *	SCIPgetLhsCoefsSOC (SCIP scip, SCIP_CONS cons)

SCIP_Real *	SCIPgetLhsOffsetsSOC (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPgetLhsConstantSOC (SCIP scip, SCIP_CONS cons)

SCIP_VAR *	SCIPgetRhsVarSOC (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPgetRhsCoefSOC (SCIP scip, SCIP_CONS cons)

SCIP_Real	SCIPgetRhsOffsetSOC (SCIP scip, SCIP_CONS cons)

SCIP_RETCODE	SCIPaddToNlpiProblemSOC (SCIP scip, SCIP_CONS cons, SCIP_NLPI nlpi, SCIP_NLPIPROBLEM nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names)

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrSOC ( SCIP * scip )

creates the handler for second order cone constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 4367 of file cons_soc.c.

References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPRESOL, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, FALSE, NULL, QUADCONSUPGD_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPfindConshdlr(), SCIPincludeConshdlrBasic(), SCIPincludeEventhdlrBasic(), SCIPincludeQuadconsUpgrade(), SCIPinfinity(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExit(), SCIPsetConshdlrExitpre(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrGetNVars(), SCIPsetConshdlrGetVars(), SCIPsetConshdlrInit(), SCIPsetConshdlrInitsol(), SCIPsetConshdlrParse(), SCIPsetConshdlrPresol(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

Referenced by SCIP_DECL_CONSHDLRCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPcreateConsSOC	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	coefs,
		SCIP_Real *	offsets,
		SCIP_Real	constant,
		SCIP_VAR *	rhsvar,
		SCIP_Real	rhscoeff,
		SCIP_Real	rhsoffset,
		SCIP_Bool	initial,
		SCIP_Bool	separate,
		SCIP_Bool	enforce,
		SCIP_Bool	check,
		SCIP_Bool	propagate,
		SCIP_Bool	local,
		SCIP_Bool	modifiable,
		SCIP_Bool	dynamic,
		SCIP_Bool	removable
	)

creates and captures a second order cone constraint

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables on left hand side of constraint (n)
vars	array with variables on left hand side (x_i)
coefs	array with coefficients of left hand side variables (alpha_i), or NULL if all 1.0
offsets	array with offsets of variables (beta_i), or NULL if all 0.0
constant	constant on left hand side (gamma)
rhsvar	variable on right hand side of constraint (x_{n+1})
rhscoeff	coefficient of variable on right hand side (alpha_{n+1})
rhsoffset	offset of variable on right hand side (beta_{n+1})
initial	should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separate	should the constraint be separated during LP processing? Usually set to TRUE.
enforce	should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
check	should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagate	should the constraint be propagated during node processing? Usually set to TRUE.
local	is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiable	is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamic	is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removable	should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.

Definition at line 4477 of file cons_soc.c.

References BMSclearMemoryArray, catchVarEvents(), CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcaptureVar(), SCIPcomputeVarLbGlobal(), SCIPcomputeVarLbLocal(), SCIPcomputeVarUbGlobal(), SCIPcomputeVarUbLocal(), SCIPconshdlrGetData(), SCIPcreateCons(), SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfindConshdlr(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), and SCIPisTransformed().

Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_QUADCONSUPGD(), and SCIPcreateConsBasicSOC().

SCIP_RETCODE SCIPcreateConsBasicSOC	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_Real *	coefs,
		SCIP_Real *	offsets,
		SCIP_Real	constant,
		SCIP_VAR *	rhsvar,
		SCIP_Real	rhscoeff,
		SCIP_Real	rhsoffset
	)

creates and captures a second order cone constraint in its most basic variant, i. e., with all constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h

See Also: SCIPcreateConsSOC() for the default constraint flag configuration

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

creates and captures a second order cone constraint with all its constraint flags set to their default values

Note: the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
nvars	number of variables on left hand side of constraint (n)
vars	array with variables on left hand side (x_i)
coefs	array with coefficients of left hand side variables (alpha_i), or NULL if all 1.0
offsets	array with offsets of variables (beta_i), or NULL if all 0.0
constant	constant on left hand side (gamma)
rhsvar	variable on right hand side of constraint (x_{n+1})
rhscoeff	coefficient of variable on right hand side (alpha_{n+1})
rhsoffset	offset of variable on right hand side (beta_{n+1})

Definition at line 4605 of file cons_soc.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPcreateConsSOC(), and TRUE.

SCIP_RETCODE SCIPgetNlRowSOC	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_NLROW **	nlrow
	)

Gets the SOC constraint as a nonlinear row representation.

Parameters

scip	SCIP data structure
cons	constraint
nlrow	pointer to store nonlinear row

Definition at line 4628 of file cons_soc.c.

References createNlRow(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPconsGetHdlr().

Referenced by createCoveringProblem().

int SCIPgetNLhsVarsSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the number of variables on the left hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4654 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_VAR** SCIPgetLhsVarsSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the variables on the left hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4667 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_Real* SCIPgetLhsCoefsSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the coefficients of the variables on the left hand side of a SOC constraint, or NULL if all are equal to 1.0.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4680 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), and SCIPwriteGms().

SCIP_Real* SCIPgetLhsOffsetsSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the offsets of the variables on the left hand side of a SOC constraint, or NULL if all are equal to 0.0.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4693 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by printSOCCons(), SCIP_DECL_READERWRITE(), and SCIPwriteGms().

SCIP_Real SCIPgetLhsConstantSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the constant on the left hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4706 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by printSOCCons(), SCIP_DECL_READERWRITE(), and SCIPwriteGms().

SCIP_VAR* SCIPgetRhsVarSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the variable on the right hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4719 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPwriteGms(), and SCIPwriteLp().

SCIP_Real SCIPgetRhsCoefSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the coefficient of the variable on the right hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4732 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), and SCIPwriteGms().

SCIP_Real SCIPgetRhsOffsetSOC	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

Gets the offset of the variables on the right hand side of a SOC constraint.

Parameters

scip	SCIP data structure
cons	constraint data

Definition at line 4745 of file cons_soc.c.

References NULL, and SCIPconsGetData().

Referenced by printSOCCons(), SCIP_DECL_READERWRITE(), and SCIPwriteGms().

SCIP_RETCODE SCIPaddToNlpiProblemSOC	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_NLPI *	nlpi,
		SCIP_NLPIPROBLEM *	nlpiprob,
		SCIP_HASHMAP *	scipvar2nlpivar,
		SCIP_Bool	names
	)

Adds the constraint to an NLPI problem. Uses nonconvex formulation as quadratic function.

Parameters

scip	SCIP data structure
cons	SOC constraint
nlpi	interface to NLP solver
nlpiprob	NLPI problem where to add constraint
scipvar2nlpivar	mapping from SCIP variables to variable indices in NLPI
names	whether to pass constraint names to NLPI

Definition at line 4759 of file cons_soc.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPhashmapGetImage(), SCIPinfinity(), and SCIPnlpiAddConstraints().

SCIP

Detailed Description

Functions

Function Documentation