  # SCIP

Solving Constraint Integer Programs

## Detailed Description

constraint handler for quadratic constraints $$\textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}$$

#include "scip/def.h"
#include "scip/type_cons.h"
#include "scip/type_lp.h"
#include "scip/type_misc.h"
#include "scip/type_nlp.h"
#include "nlpi/type_nlpi.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_sepa.h"
#include "scip/type_sol.h"
#include "scip/type_timing.h"
#include "scip/type_var.h"

Go to the source code of this file.

## Data Structures

struct  SCIP_BilinTerm

struct  SCIP_RowPrep

## Functions

This constraint handler handles constraints of the form

$\textrm{lhs} \leq \sum_{i,j=1}^n a_{i,j} x_ix_j + \sum_{i=1}^n b_i x_i \leq \textrm{rhs}$

Constraints are enforced by separation, domain propagation, and spatial branching.

For semidefinite matrices $$A=(a_{i,j})_{i,j}$$, cuts based on linearization of $$\langle x, Ax\rangle$$ are implemented. For underestimating a non-convex term, McCormick underestimators and secants for univariate concave quadratic terms are implemented. If $$\langle x, Ax\rangle$$ is factorable (i.e., can be written as product of two linear functions), specialized separation techniques (e.g., lifted tangent inequalities) that take the constraint sides into account are applied.

Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated. Further, domain propagation is applied.

During presolve, variable products which contain binary variables may be reformulated into linear constraints, thereby introducing new variables.

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.
Stefan Vigerske
Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming
PhD Thesis, Humboldt-University Berlin, 2012, submitted.
Pietro Belotti and Andrew J. Miller and Mahdi Namazifar
Linear inequalities for bounded products of variables
SIAG/OPT Views-and-News 22:1, 1-8, 2011.

typedef struct SCIP_BilinTerm SCIP_BILINTERM

typedef struct SCIP_RowPrep SCIP_ROWPREP

SCIP_EXPORT SCIP_RETCODE SCIPcreateConsQuadratic (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoeffs, SCIP_Real lhs, SCIP_Real rhs, 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_EXPORT SCIP_RETCODE SCIPcreateConsBasicQuadratic (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs)

SCIP_EXPORT SCIP_RETCODE SCIPcreateConsQuadratic2 (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs, 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_EXPORT SCIP_RETCODE SCIPcreateConsBasicQuadratic2 (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadvarterms, SCIP_QUADVARTERM *quadvarterms, int nbilinterms, SCIP_BILINTERM *bilinterms, SCIP_Real lhs, SCIP_Real rhs)

SCIP_EXPORT SCIP_RETCODE SCIPaddBilinTermQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)

SCIP_EXPORT SCIP_RETCODE SCIPgetNlRowQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)

SCIP_EXPORT int SCIPgetNLinearVarsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_VAR ** SCIPgetLinearVarsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_RealSCIPgetCoefsLinearVarsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT int SCIPgetNBilinTermsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_BILINTERMSCIPgetBilinTermsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_Real SCIPgetLhsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_Real SCIPgetRhsQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT int SCIPgetLinvarMayDecreaseQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT int SCIPgetLinvarMayIncreaseQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_RETCODE SCIPcheckCurvatureQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_Bool SCIPisConvexQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_Bool SCIPisConcaveQuadratic (SCIP *scip, SCIP_CONS *cons)

SCIP_EXPORT SCIP_RETCODE SCIPgetViolationQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation)

SCIP_EXPORT SCIP_Bool SCIPisLinearLocalQuadratic (SCIP *scip, SCIP_CONS *cons)

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

SCIP_EXPORT SCIP_RETCODE SCIPchgLhsQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)

SCIP_EXPORT SCIP_RETCODE SCIPchgRhsQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)

SCIP_EXPORT SCIP_RETCODE SCIPgetFeasibilityQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility)

SCIP_EXPORT SCIP_RETCODE SCIPgetActivityQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity)

SCIP_EXPORT SCIP_RETCODE SCIPchgLinearCoefQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)

SCIP_EXPORT SCIP_RETCODE SCIPchgSquareCoefQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)

SCIP_EXPORT SCIP_RETCODE SCIPchgBilinCoefQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)