Scippy

SCIP

Solving Constraint Integer Programs

Data Structures | Functions
cons_quadratic.h File Reference
Public API of SCIP » Plugin API of SCIP » Constraint Handlers

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}\)

Author
Stefan Vigerske

Definition in file cons_quadratic.h.

#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_QuadVarTerm
 
struct  SCIP_BilinTerm
 
struct  SCIP_RowPrep
 

Functions

SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrQuadratic (SCIP *scip)
 

Quadratic Constraints

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.

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.
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.
#define SCIP_DECL_QUADCONSUPGD(x)
 
typedef struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA
 
typedef struct SCIP_QuadVarTerm SCIP_QUADVARTERM
 
typedef struct SCIP_BilinTerm SCIP_BILINTERM
 
typedef struct SCIP_RowPrep SCIP_ROWPREP
 
SCIP_EXPORT SCIP_RETCODE SCIPincludeQuadconsUpgrade (SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname)
 
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 void SCIPaddConstantQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_Real constant)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddLinearVarQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddSquareCoefQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
 
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_Real * SCIPgetCoefsLinearVarsQuadratic (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT int SCIPgetNQuadVarTermsQuadratic (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_RETCODE SCIPsortQuadVarTermsQuadratic (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_RETCODE SCIPfindQuadVarTermQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos)
 
SCIP_EXPORT int SCIPgetNBilinTermsQuadratic (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPORT SCIP_BILINTERM * SCIPgetBilinTermsQuadratic (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 SCIPisConvexConsQuadratic (SCIP *scip, SCIP_CONS *cons, SCIP_HASHMAP *assumevarfixed, SCIP_Bool *result)
 
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)
 
SCIP_EXPORT int SCIPgetNAllBilinearTermsQuadratic (SCIP *scip)
 
SCIP_EXPORT SCIP_RETCODE SCIPgetAllBilinearTermsQuadratic (SCIP *scip, SCIP_VAR **RESTRICT x, SCIP_VAR **RESTRICT y, int *RESTRICT nbilinterms, int *RESTRICT nunderests, int *RESTRICT noverests, SCIP_Real *maxnonconvexity)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddBilinearIneqQuadratic (SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, int idx, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)