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 SCIPincludeConshdlrSOC ( SCIP scip)

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

Parameters
scipSCIP data structure
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'.
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()
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})
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
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
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
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
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
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
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
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
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
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