cons_quadratic.h
Go to the documentation of this file.
18 * @brief constraint handler for quadratic constraints \f$\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}\f$
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
70 * For semidefinite matrices \f$A=(a_{i,j})_{i,j}\f$, cuts based on linearization of \f$\langle x, Ax\rangle\f$ are implemented.
71 * For underestimating a non-convex term, McCormick underestimators and secants for univariate concave quadratic terms are implemented.
72 * If \f$\langle x, Ax\rangle\f$ is factorable (i.e., can be written as product of two linear functions),
73 * specialized separation techniques (e.g., lifted tangent inequalities) that take the constraint sides into account are applied.
75 * Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated.
78 * During presolve, variable products which contain binary variables may be reformulated into linear constraints, thereby introducing new variables.
83 * <a href="http://dx.doi.org/10.1007/978-1-4614-1927-3">Extending a CIP framework to solve MIQCPs</a>@n
90 * Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming@n
119 * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2
176 int nbinlin, int nbinquad, int nintlin, int nintquad, int nimpllin, int nimplquad, int ncontlin, int ncontquad, \
177 SCIP_Bool integral, int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize, SCIP_PRESOLTIMING presoltiming)
183 SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), /**< method to call for upgrading quadratic constraint */
197 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
206 SCIP_Real* lincoefs, /**< coefficients of variables in linear part (b_i) or NULL if nlinvars == 0 */
208 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms (y_j) or NULL if nquadterms == 0 */
209 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms (z_j) or NULL if nquadterms == 0 */
210 SCIP_Real* quadcoeffs, /**< array with coefficients of quadratic terms (a_j) or NULL if nquadterms == 0 */
236 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
248 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
270 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_k v_k w_k \leq u.
273 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
297 SCIP_Bool removable /**< should the constraint be removed from the LP due to aging or cleanup? */
301 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
306 * \ell \leq \sum_{i=1}^n b_i x_i + \sum_{j=1}^m (a_j y_j^2 + b_j y_j) + \sum_{k=1}^p c_kv_kw_k \leq u.
311 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
329 /** Adds a constant to the constraint function, that is, subtracts a constant from both sides */
457 * @note If the quadratic variable terms have not been sorted before, then a search may reorder the current order of the terms.
500 /** get index of a variable in linvars that may be decreased without making any other constraint infeasible, or -1 if none */
507 /** get index of a variable in linvars that may be increased without making any other constraint infeasible, or -1 if none */
514 /** Check the quadratic function of a quadratic constraint for its semi-definiteness, if not done yet.
530 /** Indicates whether the quadratic function of a quadratic constraint is (known to be) concave.
543 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
544 SCIP_Bool* result /**< buffer where to store whether constraint is convex (under given variable fixing) */
558 * That is, checks whether each variable with a square term is fixed and for each bilinear term at least one variable is fixed.
579 * @note This method may only be called during problem creation stage for an original constraint.
590 * @note This method may only be called during problem creation stage for an original constraint.
617 /** changes the linear coefficient value for a given quadratic variable in a quadratic constraint data; if not
630 /** changes the square coefficient value for a given quadratic variable in a quadratic constraint data; if not
643 /** changes the bilinear coefficient value for a given quadratic variable in a quadratic constraint data; if not
657 /** returns the total number of bilinear terms that are contained in all quadratic constraints */
670 int* RESTRICT nunderests, /**< array to store the total number of constraints that require to underestimate a bilinear term */
671 int* RESTRICT noverests, /**< array to store the total number of constraints that require to overestimate a bilinear term */
672 SCIP_Real* maxnonconvexity /**< estimate of nonconvex eigenvalues of all quadratic constraints containing a bilinear term */
675 /** adds a globally valid inequality of the form xcoef x <= ycoef y + constant for a bilinear term (x,y)
677 * @note the indices of bilinear terms match with the entries of bilinear terms returned by SCIPgetAllBilinearTermsQuadratic
803 * Drops small or large coefficients if coefrange is too large, if this can be done by relaxing the cut.
807 * Scales coefficients and side down if they are large and if the minimal violation is still reached.
808 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the cut.
811 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
820 SCIP_Real* coefrange, /**< buffer to store coefrange of cleaned up cut, or NULL if not of interest */
821 SCIP_Real* viol /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
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)
Definition: cons_quadratic.c:14672
SCIP_EXPORT SCIP_RETCODE SCIPgetViolationQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation)
Definition: cons_quadratic.c:15337
type definitions for miscellaneous datastructures
timing definitions for SCIP
Definition: struct_scip.h:59
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)
Definition: cons_quadratic.c:14579
type definitions for NLP management
SCIP_EXPORT SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15112
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
Definition: cons_quadratic.c:16346
SCIP_EXPORT SCIP_RETCODE SCIPaddSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:14840
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefrange, SCIP_Real minviol, SCIP_Real *coefrange, SCIP_Real *viol)
Definition: cons_quadratic.c:16919
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:16321
SCIP_EXPORT SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15191
Definition: struct_var.h:198
Definition: cons_quadratic.h:104
SCIP_EXPORT void SCIPaddConstantQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real constant)
Definition: cons_quadratic.c:14696
SCIP_EXPORT SCIP_RETCODE SCIPchgBilinCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
Definition: cons_quadratic.c:15876
SCIP_EXPORT SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15125
SCIP_EXPORT SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15047
SCIP_RETCODE SCIPgetRowprepRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
Definition: cons_quadratic.c:17052
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPaddToNlpiProblemQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *scipvar2nlpivar, SCIP_Bool names)
Definition: cons_quadratic.c:15412
SCIP_EXPORT SCIP_RETCODE SCIPchgSquareCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:15807
Definition: struct_sepa.h:37
SCIP_EXPORT SCIP_RETCODE SCIPfindQuadVarTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, int *pos)
Definition: cons_quadratic.c:15078
SCIP_EXPORT SCIP_RETCODE SCIPchgLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:15714
SCIP_EXPORT SCIP_RETCODE SCIPgetActivityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *activity)
Definition: cons_quadratic.c:15679
SCIP_EXPORT int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15032
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
Definition: cons_quadratic.c:17075
SCIP_EXPORT SCIP_RETCODE SCIPsortQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15060
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real lincoef, SCIP_Real sqrcoef)
Definition: cons_quadratic.c:14757
SCIP_EXPORT SCIP_RETCODE SCIPchgLhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_quadratic.c:15550
type definitions for LP management
Definition: struct_sol.h:64
SCIP_EXPORT SCIP_RETCODE SCIPaddQuadVarLinearCoefQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:14787
Definition: struct_misc.h:128
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: cons_quadratic.c:16228
SCIP_EXPORT SCIP_RETCODE SCIPincludeConshdlrQuadratic(SCIP *scip)
Definition: cons_quadratic.c:14159
struct SCIP_QuadVarEventData SCIP_QUADVAREVENTDATA
Definition: cons_quadratic.h:100
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: cons_quadratic.c:16270
Definition: struct_cons.h:37
SCIP_EXPORT SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15205
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
Definition: cons_quadratic.c:16404
Definition: struct_cons.h:117
type definitions for SCIP's main datastructure
void SCIPaddRowprepSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: cons_quadratic.c:16379
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: cons_quadratic.c:16208
SCIP_EXPORT SCIP_RETCODE SCIPaddBilinTermQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real coef)
Definition: cons_quadratic.c:14897
type definitions for problem variables
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)
Definition: cons_quadratic.c:14610
SCIP_EXPORT SCIP_RETCODE SCIPchgRhsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_quadratic.c:15595
SCIP_EXPORT SCIP_RETCODE SCIPincludeQuadconsUpgrade(SCIP *scip, SCIP_DECL_QUADCONSUPGD((*quadconsupgd)), int priority, SCIP_Bool active, const char *conshdlrname)
Definition: cons_quadratic.c:14321
SCIP_EXPORT int SCIPgetLinvarMayIncreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15171
SCIP_EXPORT SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15003
SCIP_EXPORT SCIP_RETCODE SCIPgetFeasibilityQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *feasibility)
Definition: cons_quadratic.c:15637
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
Definition: cons_quadratic.c:16437
Definition: struct_lp.h:192
Definition: cons_quadratic.h:121
type definitions for storing primal CIP solutions
SCIP_EXPORT SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15238
SCIP_EXPORT SCIP_RETCODE SCIPaddLinearVarQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
Definition: cons_quadratic.c:14732
SCIP_EXPORT int SCIPgetNAllBilinearTermsQuadratic(SCIP *scip)
Definition: cons_quadratic.c:15955
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
Definition: cons_quadratic.c:16243
SCIP_EXPORT SCIP_Bool SCIPisLinearLocalQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15366
SCIP_EXPORT int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14988
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)
Definition: cons_quadratic.c:15976
type definitions for separators
SCIP_EXPORT int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15097
SCIP_EXPORT SCIP_RETCODE SCIPisConvexConsQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_HASHMAP *assumevarfixed, SCIP_Bool *result)
Definition: cons_quadratic.c:15271
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
Definition: cons_quadratic.c:17023
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)
Definition: cons_quadratic.c:16065
Definition: struct_nlp.h:63
SCIP_EXPORT SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15138
SCIP_EXPORT SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15018
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)
Definition: cons_quadratic.c:14397
common defines and data types used in all packages of SCIP
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: cons_quadratic.c:16296
Definition: objbenders.h:33
SCIP_EXPORT int SCIPgetLinvarMayDecreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15151
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
Definition: cons_quadratic.c:17098
Definition: nlpi_all.c:47
type definitions for constraints and constraint handlers
type definitions for specific NLP solver interfaces
SCIP_EXPORT SCIP_RETCODE SCIPgetNlRowQuadratic(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
Definition: cons_quadratic.c:14963
Definition: cons_quadratic.h:134
void SCIPaddRowprepConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: cons_quadratic.c:16393
Definition: struct_nlpi.h:35