presol_qpkktref.c
Go to the documentation of this file.
20 * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic
30 * We first check if the structure of the program is like (QP), see the documentation of the function
33 * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT
43 * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$
44 * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$.
58 * where \f$J = \{1,\dots, p\}\f$, \f$\mu\f$ and \f$\lambda\f$ are the Lagrangian variables, and \f$I_J\f$ is the
59 * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like
69 * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms()
70 * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms()
74 * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions.
77 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
105 #define PRESOL_PRIORITY -1 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers);
107 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
109 #define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
120 SCIP_Bool updatequadbounded; /**< if TRUE then only apply the update to QPs with bounded variables; if
123 SCIP_Bool updatequadindef; /**< if TRUE then apply quadratic constraint update even if the quadratic
132 /** for a linear constraint \f$a^T x \leq b\f$, create the complementarity constraint \f$\mu \cdot s = 0\f$, where
133 * \f$s = b - a^T x\f$ and \f$\mu\f$ is the dual variable associated to the constraint \f$a^T x \leq b\f$
179 SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
186 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &KKTlincons, name, nvars, vars, vals, eqval, eqval) );
191 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
213 * - for an upper bound constraint \f$x_i \leq u_i\f$, create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$,
214 * where \f$s_i = u_i - x_i\f$ and \f$\mu_i\f$ is the dual variable of the upper bound constraint
215 * - for a lower bound constraint \f$x_i \geq l_i\f$, create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$,
255 /* create complementarity constraint; if bound is nonzero, we additionally need to introduce a slack variable */
258 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
274 SCIP_CALL( SCIPcreateVarBasic(scip, &slack, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
287 /* create SOS1 (complementarity) constraint involving dual variable of linear constraint and slack variable */
309 /** create the complementarity constraints of the KKT-like conditions associated to a binary variable \f$x_i\f$;
310 * these are \f$(1 - x_i) \cdot z_i = 0\f$ and \f$x_i \cdot (z_i - \lambda_i) = 0\f$, where \f$z_i\f$ and
338 SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
371 SCIP_CALL( SCIPcreateVarBasic(scip, &slackbin2, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
408 * 4. create the complementarity constraint \f$\mu_i \cdot s_i = 0\f$, where \f$s_i = u_i - x_i\f$
409 * 5. create the complementarity constraint \f$\lambda_i \cdot w_i = 0\f$, where \f$w_i = x_i - l_i\f$
411 * 7. the treatment of binary variables needs special care see the documentation of createKKTComplementarityBinary()
413 * if variable exists in hasmap then the dual constraint associated to the variable has already been created and is returned
456 /* create dual variables corresponding to the bounds of the variables; binary variables have to be treated in a
460 /* create first dual variable associated to binary constraint; the domain of dualbin is [-inf,inf]; the objective
463 SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin1, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
469 /* create second variable associated to binary constraint; the domain of dualbin2 is [-inf,inf]; the objective
472 SCIP_CALL( SCIPcreateVarBasic(scip, &dualbin2, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
483 SCIP_CALL( SCIPcreateVarBasic(scip, &duallb, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
493 SCIP_CALL( SCIPcreateVarBasic(scip, &dualub, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
511 /* add dual variables to dual constraints and create complementarity constraints; binary variables have to be
531 /* create complementarity constraint between slack variable of lower bound constraint and dual variable of
543 /* create complementarity constraint between slack variable of upper bound constraint and dual variable of
557 * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to the variables of the
559 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the
562 * 4. create the complementarity constraint \f$\mu_i \cdot (Ax - b)_i = 0\f$ associated to this linear constraint
566 * for step 4 see the documentation of the function createKKTComplementarityLinear() for further information.
617 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
621 /* create complementarity constraint between dual variable and slack variable of linear constraint */
622 SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, TRUE,
633 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0,
640 SCIP_CALL( SCIPcreateVarBasic(scip, &duallin, name, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
644 /* create complementarity constraint between dual variable and slack variable of linear constraint */
645 SCIP_CALL( createKKTComplementarityLinear(scip, namepart, vars, vals, lhs, rhs, nvars, duallin, FALSE,
661 SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
682 /** handle linear constraints for quadratic constraint update, see the documentation of the function
732 /* remove linear constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
733 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
751 /** handle knapsack constraints for quadratic constraint update, see the documentation of the function
819 /* remove knapsack constraints, since they are now redundant; their feasibility is already expressed
820 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
831 /** handle set packing constraints for quadratic constraint update, see the documentation of the function
918 /* remove set packing constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
919 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
937 /** handle varbound constraints for quadratic constraint update, see the documentation of the function
1006 /* remove varbound constraints if lhs != rhs, since they are now redundant; their feasibility is already expressed
1007 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
1025 /** handle logicor constraints for quadratic constraint update, see the documentation of the function
1094 /* remove logicor constraints, since they are now redundant; their feasibility is already expressed
1095 * by s >= 0, where s is the new slack variable that we introduced for these linear constraints */
1108 * we apply the function presolveAddKKTLinearCons() to the aggregation constraint, see the documentation of this
1262 * 1. create the dual constraints (i.e., the two rows of \f$Q x + c + A^T \mu = 0\f$) associated to these variables, if not
1264 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of the two
1321 SCIP_CALL( createKKTDualCons(scip, objcons, bilvar1, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1336 * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
1338 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1380 SCIP_CALL( createKKTDualCons(scip, objcons, quadvar, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1385 SCIP_CALL( SCIPaddCoefLinear(scip, dualcons, quadvar, (SCIP_Real) quadterms[j].sqrcoef * 2 / scale) );
1394 * 1. create the dual constraint (i.e., a row of \f$Q x + c + A^T \mu = 0\f$) associated to this variable, if not done
1396 * 2. create the dual variables and the complementarity constraints for the lower and upper bound constraints of this
1399 * 4. add \f$c_i\f$ to the objective constraint \f$1/2 ( c^T x + b^T \mu) = t\f$, where t is the objective variable
1448 SCIP_CALL( createKKTDualCons(scip, objcons, var, varhash, dualconss, ndualconss, &dualcons, naddconss) );
1456 SCIP_CALL( SCIPchgLhsLinear(scip, dualcons, SCIPgetLhsLinear(scip, dualcons) - coef / scale) );
1457 SCIP_CALL( SCIPchgRhsLinear(scip, dualcons, SCIPgetRhsLinear(scip, dualcons) - coef / scale) );
1499 /** checks for a given constraint whether it is the objective function of a (mixed-binary) quadratic program
1519 * 1. there is a single quadratic constraint that can be written as \f$x^T Q x + c^T x + d \leq t\f$
1521 * 3. all integer variables are binary if allowbinary = TRUE, or all variables are continuous if allowbinary = FALSE
1529 SCIP_Bool allowbinary, /**< if TRUE then allow binary variables in the problem, if FALSE then all
1534 SCIP_Real* objrhs, /**< pointer to store the right hand side @p -d of the objective constraint */
1561 /* desired structure: there exists only one variable with nonzero objective value; this is the objective variable 'z' */
1565 /* desired structure: all integer variables are binary; if the parameter 'allowbinary' is set to FALSE, then all
1582 if( ! SCIPisFeasEQ(scip, quadlhs, quadrhs) && ! SCIPisInfinity(scip, -quadlhs) && ! SCIPisInfinity(scip, quadrhs) )
1623 * Here, -d is the objective shift. We define b to be the right hand side of the objective constraint.
1631 /* search for the objective variable 'objvar' in the linear term of quadratic constraint (it is already known that
1632 * at most one variable has a nonzero objective value); additionally, check the sign of the objective variable */
1660 *scale = -coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1669 *scale = coef; /* value by which we have to scale the quadratic constraint such that the objective variable
1718 /* not every optimal solution of the problem is a KKT point if the objective variable is bounded */
1825 SCIPdebugMsg(scip, "tries to add the KKT conditions for constraint <%s>\n", SCIPconsGetName(cons));
1834 if( ! presoldata->updatequadindef && ( SCIPisConvexQuadratic(scip, cons) || SCIPisConcaveQuadratic(scip, cons) ) )
1836 SCIPdebugMsg(scip, "quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is not \
1848 SCIP_CALL( checkConsQuadraticProblem(scip, quadconshdlr, cons, presoldata->addkktbinary, &objvar, &scale, &objrhs, &isqp) );
1888 ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
1891 SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> are \
1905 if( ( bilvar1 != objvar && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bilvar1)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bilvar1)) ) )
1906 || ( bilvar2 != objvar && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(bilvar2)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(bilvar2)) ) ) )
1908 SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> \
1921 && ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) )
1924 SCIPdebugMsg(scip, "failed adding the KKT conditions, since not all variables to quadratic constraint <%s> \
1934 SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip) + SCIPgetNFixedVars(scip)) );
1937 SCIP_CALL( SCIPallocBufferArray(scip, &dualconss, 2 * SCIPgetNVars(scip) + 2 * SCIPgetNFixedVars(scip)) ); /*lint !e647*/
1939 /* duplicate linconss for later use, since in the following, we create new linear constraints */
1946 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &objcons, "objcons", 0, NULL, NULL, objrhs, objrhs) );
1959 SCIP_CALL( presolveAddKKTLinearConss(scip, objcons, savelinconss, nlinconss, varhash, dualconss, &ndualconss,
1964 SCIP_CALL( presolveAddKKTSetppcConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1967 SCIP_CALL( presolveAddKKTKnapsackConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1970 SCIP_CALL( presolveAddKKTVarboundConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1973 SCIP_CALL( presolveAddKKTLogicorConss(scip, objcons, varhash, dualconss, &ndualconss, naddconss, ndelconss) );
1978 SCIP_CALL( presolveAddKKTAggregatedVars(scip, objcons, SCIPgetFixedVars(scip), SCIPgetNFixedVars(scip),
1983 SCIP_CALL( presolveAddKKTQuadBilinearTerms(scip, objcons, bilinterms, nbilinterms, varhash, scale, dualconss,
1987 SCIP_CALL( presolveAddKKTQuadQuadraticTerms(scip, objcons, quadterms, nquadterms, varhash, scale, dualconss,
1991 SCIP_CALL( presolveAddKKTQuadLinearTerms(scip, objcons, lintermvars, lintermcoefs, nlintermvars, quadterms, nquadterms,
2032 )
2041 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2055 "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a \
2060 "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite",
SCIP_VAR ** SCIPgetLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14865
static SCIP_RETCODE createKKTComplementarityLinear(SCIP *scip, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_VAR *dualvar, SCIP_Bool takelhs, int *naddconss)
Definition: presol_qpkktref.c:138
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:174
Definition: struct_presol.h:37
static SCIP_RETCODE presolveAddKKTQuadBilinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_BILINTERM *bilinterms, int nbilinterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1273
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:225
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:851
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
static SCIP_DECL_PRESOLCOPY(presolCopyQPKKTref)
Definition: presol_qpkktref.c:1749
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17135
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_linear.c:17751
Definition: struct_scip.h:58
Constraint handler for variable bound constraints .
public methods for memory management
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
static SCIP_RETCODE presolveAddKKTLogicorConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:1031
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5282
static SCIP_RETCODE presolveAddKKTKnapsackConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:757
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
Definition: cons_setppc.h:80
Definition: struct_var.h:198
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:940
static SCIP_RETCODE createKKTComplementarityBounds(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss)
Definition: presol_qpkktref.c:222
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:903
Definition: cons_quadratic.h:104
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4563
public methods for presolving plugins
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
Definition: presol_qpkktref.c:2032
SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
Definition: var.c:17180
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:184
static SCIP_RETCODE presolveAddKKTLinearCons(SCIP *scip, SCIP_CONS *objcons, const char *namepart, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:571
Definition: cons_setppc.h:79
public methods for problem variables
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13661
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2931
static SCIP_RETCODE createKKTDualCons(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR *var, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, SCIP_CONS **dualcons, int *naddconss)
Definition: presol_qpkktref.c:418
Constraint handler for the set partitioning / packing / covering constraints .
public methods for SCIP variables
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18168
SCIP_Real SCIPgetLhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14979
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:17900
public methods for numerical tolerances
int SCIPgetNQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14892
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3025
int SCIPgetNBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14953
static SCIP_DECL_PRESOLEXEC(presolExecQPKKTref)
Definition: presol_qpkktref.c:1781
Definition: struct_misc.h:121
SCIP_Bool SCIPisConcaveQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15071
public methods for managing constraints
Constraint handler for knapsack constraints of the form , x binary and .
static SCIP_RETCODE presolveAddKKTQuadLinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **lintermvars, SCIP_Real *lintermcoefs, int nlintermvars, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1406
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4929
Definition: struct_cons.h:37
Definition: struct_cons.h:117
static SCIP_RETCODE presolveAddKKTAggregatedVars(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **agrvars, int nagrvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1114
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4908
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
Definition: cons_sos1.c:10504
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
static SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_QUADVARTERM *quadterms, int nquadterms, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
Definition: presol_qpkktref.c:1347
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:512
SCIP_Real * SCIPgetCoefsLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14879
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4971
int SCIPgetLinvarMayDecreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15003
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5303
constraint handler for quadratic constraints
Definition: type_var.h:44
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4950
Definition: type_retcode.h:33
Definition: cons_setppc.h:78
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:17147
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:877
static SCIP_RETCODE presolveAddKKTLinearConss(SCIP *scip, SCIP_CONS *objcons, SCIP_CONS **savelinconss, int nlinconss, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:688
SCIP_BILINTERM * SCIPgetBilinTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14967
public methods for constraint handler plugins and constraints
Definition: type_retcode.h:34
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13587
SCIP_Real SCIPgetRhsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14991
public data structures and miscellaneous methods
static SCIP_RETCODE checkConsQuadraticProblem(SCIP *scip, SCIP_CONSHDLR *quadconshdlr, SCIP_CONS *cons, SCIP_Bool allowbinary, SCIP_VAR **objvar, SCIP_Real *scale, SCIP_Real *objrhs, SCIP_Bool *isqp)
Definition: presol_qpkktref.c:1527
static SCIP_RETCODE createKKTComplementarityBinary(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss)
Definition: presol_qpkktref.c:316
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9292
Definition: type_var.h:46
static SCIP_DECL_PRESOLFREE(presolFreeQPKKTref)
Definition: presol_qpkktref.c:1764
Definition: cons_quadratic.h:121
Definition: type_var.h:45
static SCIP_RETCODE presolveAddKKTSetppcConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:837
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition: cons_linear.c:18212
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12253
SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
Definition: cons_sos1.c:10488
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9271
SCIP_RETCODE SCIPcheckCurvatureQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15041
public methods for presolvers
int SCIPgetLinvarMayIncreaseQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15022
int SCIPgetNLinearVarsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14851
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18253
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:209
public methods for message output
Definition: type_var.h:84
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:928
constraint handler for SOS type 1 constraints
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13640
public methods for message handling
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18276
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition: cons_linear.c:18191
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2874
SCIP_QUADVARTERM * SCIPgetQuadVarTermsQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:14906
Definition: type_retcode.h:43
Definition: objbenders.h:33
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13682
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:4887
public methods for global and local (sub)problems
Definition: type_var.h:43
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18230
static SCIP_RETCODE presolveAddKKTVarboundConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
Definition: presol_qpkktref.c:943
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18145
SCIP_Bool SCIPisConvexQuadratic(SCIP *scip, SCIP_CONS *cons)
Definition: cons_quadratic.c:15054
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
qpkktref presolver
memory allocation routines
Definition: type_var.h:58