113#define PRESOL_NAME "qpkktref"
114#define PRESOL_DESC "adds KKT conditions to (mixed-binary) quadratic programs"
115#define PRESOL_PRIORITY -1
117#define PRESOL_MAXROUNDS 0
119#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM
127struct SCIP_PresolData
129 SCIP_Bool addkktbinary;
130 SCIP_Bool updatequadbounded;
133 SCIP_Bool updatequadindef;
214 *naddconss = *naddconss + 2;
310 *naddconss = *naddconss + 2;
608 for(
i = 0;
i < 2; ++
i )
719 for(
c = 0;
c < nlinconss; ++
c )
744 for(
c = nlinconss-1;
c >= 0; --
c )
789 if( conshdlr ==
NULL )
796 for(
c = 0;
c < nconss; ++
c )
800 SCIP_Longint* weights;
818 for( v = 0; v <
nvars; ++v )
819 vals[v] = (SCIP_Real) weights[v];
831 for(
c = nconss-1;
c >= 0; --
c )
869 if( conshdlr ==
NULL )
876 for(
c = 0;
c < nconss; ++
c )
917 for( v = 0; v <
nvars; ++v )
930 for(
c = nconss-1;
c >= 0; --
c )
975 if( conshdlr ==
NULL )
982 for(
c = 0;
c < nconss; ++
c )
1018 for(
c = nconss-1;
c >= 0; --
c )
1063 if( conshdlr ==
NULL )
1070 for(
c = 0;
c < nconss; ++
c )
1093 for( v = 0; v <
nvars; ++v )
1106 for(
c = nconss-1;
c >= 0; --
c )
1148 SCIP_Real* vals =
NULL;
1326 for(
i = 0;
i < 2; ++
i )
1384 for(
j = 0;
j < nquadexprs; ++
j )
1436 SCIP_Real* lincoefs;
1453 for(
j = 0;
j < nlinexprs; ++
j )
1486 for(
j = 0;
j < nquadexprs; ++
j )
1580 SCIP_Real* lincoefs;
1617 if( conshdlr !=
NULL )
1621 if( conshdlr !=
NULL )
1625 if( conshdlr !=
NULL )
1629 if( conshdlr !=
NULL )
1633 if( conshdlr !=
NULL )
1644 if( constant != 0.0 )
1722 *
objrhs = (*objrhs)/(*scale);
1887 SCIPdebugMsg(
scip,
"quadratic constraint update failed, since matrix associated to quadratic constraint <%s> is \
1918 if( presoldata->updatequadbounded )
1957 SCIPdebugMsg(
scip,
"failed adding the KKT conditions, since not all variables of <%s> have finite bounds.\n",
1992 naddconss, ndelconss) );
2047 SCIPdebugMsg(
scip,
"added the KKT conditions to the mixed-binary quadratic program\n");
2083 "if TRUE then allow binary variables for KKT update",
2087 "if TRUE then only apply the update to QPs with bounded variables; if the variables are not bounded then a "
2088 "finite optimal solution might not exist and the KKT conditions would then be invalid",
2092 "if TRUE then apply quadratic constraint update even if the quadratic constraint matrix is known to be indefinite",
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for nonlinear constraints specified by algebraic expressions
Constraint handler for the set partitioning / packing / covering constraints .
constraint handler for SOS type 1 constraints
Constraint handler for variable bound constraints .
SCIP_RETCODE SCIPcheckQuadraticNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *isquadratic)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddVarSOS1(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real weight)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicSOS1(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *weights)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
void SCIPgetLinvarMayIncreaseNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **var, SCIP_Real *coef)
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)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
enum SCIP_SetppcType SCIP_SETPPCTYPE
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
@ SCIP_SETPPCTYPE_COVERING
@ SCIP_SETPPCTYPE_PACKING
int SCIPgetNObjVars(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
int SCIPgetNFixedVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
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)
void SCIPswapPointers(void **pointer1, void **pointer2)
SCIP_RETCODE SCIPincludePresolQPKKTref(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
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)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
SCIP_Real SCIPvarGetNegationConstant(SCIP_VAR *var)
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbOriginal(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static const SCIP_Real scalars[]
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
static SCIP_RETCODE createKKTComplementarityBinary(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualbin1, SCIP_VAR *dualbin2, int *naddconss)
static SCIP_RETCODE presolveAddKKTKnapsackConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
static SCIP_RETCODE checkConsQuadraticProblem(SCIP *scip, SCIP_CONS *cons, SCIP_EXPR *quadexpr, SCIP_Bool allowbinary, SCIP_VAR **objvar, SCIP_Real *scale, SCIP_Real *objrhs, SCIP_Bool *isqp)
static SCIP_RETCODE createKKTComplementarityBounds(SCIP *scip, SCIP_VAR *var, SCIP_VAR *dualvar, SCIP_Bool takelb, int *naddconss)
static SCIP_RETCODE presolveAddKKTQuadQuadraticTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
static SCIP_RETCODE presolveAddKKTAggregatedVars(SCIP *scip, SCIP_CONS *objcons, SCIP_VAR **agrvars, int nagrvars, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
static SCIP_RETCODE presolveAddKKTSetppcConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
static SCIP_RETCODE presolveAddKKTVarboundConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
static SCIP_RETCODE presolveAddKKTQuadLinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_VAR *objvar, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
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)
static SCIP_RETCODE presolveAddKKTLogicorConss(SCIP *scip, SCIP_CONS *objcons, SCIP_HASHMAP *varhash, SCIP_CONS **dualconss, int *ndualconss, int *naddconss, int *ndelconss)
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)
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)
static SCIP_RETCODE presolveAddKKTQuadBilinearTerms(SCIP *scip, SCIP_CONS *objcons, SCIP_EXPR *quadexpr, SCIP_HASHMAP *varhash, SCIP_Real scale, SCIP_CONS **dualconss, int *ndualconss, int *naddconss)
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)
public methods for managing constraints
public methods for message output
public data structures and miscellaneous methods
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED