Scippy

SCIP

Solving Constraint Integer Programs

cons_soc.h File Reference

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_RealSCIPgetLhsCoefsSOC (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RealSCIPgetLhsOffsetsSOC (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetLhsConstantSOC (SCIP *scip, SCIP_CONS *cons)
 
SCIP_VARSCIPgetRhsVarSOC (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 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables on left hand side of constraint (n)
varsarray with variables on left hand side (x_i)
coefsarray with coefficients of left hand side variables (alpha_i), or NULL if all 1.0
offsetsarray with offsets of variables (beta_i), or NULL if all 0.0
constantconstant on left hand side (gamma)
rhsvarvariable on right hand side of constraint (x_{n+1})
rhscoeffcoefficient of variable on right hand side (alpha_{n+1})
rhsoffsetoffset of variable on right hand side (beta_{n+1})
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints.
removableshould 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 5063 of file cons_soc.c.

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

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

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nvarsnumber of variables on left hand side of constraint (n)
varsarray with variables on left hand side (x_i)
coefsarray with coefficients of left hand side variables (alpha_i), or NULL if all 1.0
offsetsarray with offsets of variables (beta_i), or NULL if all 0.0
constantconstant on left hand side (gamma)
rhsvarvariable on right hand side of constraint (x_{n+1})
rhscoeffcoefficient of variable on right hand side (alpha_{n+1})
rhsoffsetoffset of variable on right hand side (beta_{n+1})

Definition at line 5191 of file cons_soc.c.

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

Referenced by SCIPcreateConsSOC().

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

Gets the SOC constraint as a nonlinear row representation.

Parameters
scipSCIP data structure
consconstraint
nlrowpointer to store nonlinear row

Definition at line 5214 of file cons_soc.c.

References VarEventData::consdata, createNlRow(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), and SCIPgetNLhsVarsSOC().

Referenced by createCoveringProblem(), and SCIPcreateConsBasicSOC().

int SCIPgetNLhsVarsSOC ( SCIP scip,
SCIP_CONS cons 
)

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

Parameters
scipSCIP data structure
consconstraint data

Definition at line 5240 of file cons_soc.c.

References NULL, SCIPconsGetData(), and SCIPgetLhsVarsSOC().

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

SCIP_VAR** SCIPgetLhsVarsSOC ( SCIP scip,
SCIP_CONS cons 
)

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

Parameters
scipSCIP data structure
consconstraint data

Definition at line 5253 of file cons_soc.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetLhsCoefsSOC().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPgetNLhsVarsSOC(), 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
scipSCIP data structure
consconstraint data

Definition at line 5266 of file cons_soc.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetLhsOffsetsSOC().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPgetLhsVarsSOC(), 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
scipSCIP data structure
consconstraint data

Definition at line 5279 of file cons_soc.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetLhsConstantSOC().

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

SCIP_Real SCIPgetLhsConstantSOC ( SCIP scip,
SCIP_CONS cons 
)

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

Parameters
scipSCIP data structure
consconstraint data

Definition at line 5292 of file cons_soc.c.

References NULL, SCIPconsGetData(), and SCIPgetRhsVarSOC().

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

SCIP_VAR* SCIPgetRhsVarSOC ( SCIP scip,
SCIP_CONS cons 
)

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

Parameters
scipSCIP data structure
consconstraint data

Definition at line 5305 of file cons_soc.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetRhsCoefSOC().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPgetLhsConstantSOC(), 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
scipSCIP data structure
consconstraint data

Definition at line 5318 of file cons_soc.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetRhsOffsetSOC().

Referenced by createCoveringProblem(), printSOCCons(), SCIP_DECL_READERWRITE(), SCIPgetRhsVarSOC(), 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
scipSCIP data structure
consconstraint data

Definition at line 5331 of file cons_soc.c.

References NULL, SCIPaddToNlpiProblemSOC(), and SCIPconsGetData().

Referenced by printSOCCons(), SCIP_DECL_READERWRITE(), SCIPgetRhsCoefSOC(), 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
scipSCIP data structure
consSOC constraint
nlpiinterface to NLP solver
nlpiprobNLPI problem where to add constraint
scipvar2nlpivarmapping from SCIP variables to variable indices in NLPI
nameswhether to pass constraint names to NLPI

Definition at line 5345 of file cons_soc.c.

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

Referenced by SCIPgetRhsOffsetSOC().