31#ifdef SCIP_SIGCUT_DEBUG
50#define NLHDLR_NAME "signomial"
51#define NLHDLR_DESC "handler for signomial expressions"
52#define NLHDLR_DETECTPRIORITY 30
53#define NLHDLR_ENFOPRIORITY 30
56#define NLHDLR_MAXNUNDERVARS 14
57#define NLHDLR_MINCUTSCALE 1e-5
73struct SCIP_NlhdlrExprData
116#ifdef SCIP_SIGCUT_DEBUG
129 SCIPdebugMsg(
scip,
" #all variables: %d, #positive exponent variables: %d, #negative exponent variables: %d, auxvar: %s \n expr: ",
134 if( !nlhdlrexprdata->isstorecapture )
142 for(
int i = 0;
i < nlhdlrexprdata->nvars - 1;
i++ )
150 if( nlhdlrexprdata->nposvars == 0 )
156 for(
int i = 0;
i < nlhdlrexprdata->nvars;
i++ )
157 if( nlhdlrexprdata->signs[
i] )
163 if( nlhdlrexprdata->nnegvars == 0 )
169 for(
int i = 0;
i < nlhdlrexprdata->nvars;
i++ )
171 if( !nlhdlrexprdata->signs[
i] )
173 if(
i == nlhdlrexprdata->nvars - 1 )
203 int nvars = (*nlhdlrexprdata)->nvars;
213 *nlhdlrexprdata =
NULL;
255 auxvar = nlhdlrexprdata->vars[nlhdlrexprdata->nfactors];
259 if(
vars[
i] == auxvar )
261 coefauxvar = coefs[
i];
275 scale = -1.0 / coefauxvar;
278 if(
vars[
i] == auxvar )
299 assert(!nlhdlrexprdata->isstorecapture);
302 for(
c = 0;
c < nlhdlrexprdata->nfactors; ++
c )
315 nlhdlrexprdata->isstorecapture =
TRUE;
334 assert(nlhdlrexprdata->isstorecapture);
336 *isboxsignomial =
FALSE;
339 for(
c = 0;
c < nlhdlrexprdata->nfactors;
c++ )
348 nlhdlrexprdata->intervals[
c].inf = inf;
349 nlhdlrexprdata->intervals[
c].sup =
MAX(sup, inf + 0.1);
350 powinf = pow(inf, nlhdlrexprdata->exponents[
c]);
351 powsup = pow(sup, nlhdlrexprdata->exponents[
c]);
352 productinf *=
MIN(powinf, powsup);
353 productsup *=
MAX(powinf, powsup);
357 nlhdlrexprdata->intervals[
c].inf = productinf;
358 nlhdlrexprdata->intervals[
c].sup = productsup;
360 *isboxsignomial =
TRUE;
382#ifdef SCIP_MORE_DEBUG
386 for(
i = 0, j = 0;
i < nlhdlrexprdata->nvars; ++
i )
388 if( nlhdlrexprdata->signs[
i] != evaldata->
sign )
391 val *= pow(args[j], nlhdlrexprdata->refexponents[
i]);
428 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
430 if( nlhdlrexprdata->signs[
i] != sign )
433 if( !
SCIPisRelEQ(
scip, nlhdlrexprdata->intervals[
i].inf, nlhdlrexprdata->intervals[
i].sup) )
448 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
450 if( nlhdlrexprdata->signs[
i] != sign )
453 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
455 funcval *= pow(val, nlhdlrexprdata->refexponents[
i]);
464 nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
467 *isspecial = ( nsignvars <= 1 ) || ( nsignvars == 2 && !overestimate );
477 else if( nsignvars == 1 )
480 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
482 if( nlhdlrexprdata->signs[
i] == sign )
485 SCIP_Real scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
487 SCIP_Real refexponent = nlhdlrexprdata->refexponents[
i];
488 if( refexponent == 1.0 )
501 SCIPestimateRoot(
scip, refexponent, overestimate, nlhdlrexprdata->intervals[
i].inf, nlhdlrexprdata->intervals[
i].sup,
502 val, &facetconstant, &facetcoef, &islocal, success);
510 else if( nsignvars == 2 && !overestimate )
533 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
535 if( nlhdlrexprdata->signs[
i] != sign )
537 box[2 * j] = nlhdlrexprdata->intervals[
i].inf;
538 box[2 * j + 1] = nlhdlrexprdata->intervals[
i].sup;
539 refexponents[j] = nlhdlrexprdata->refexponents[
i];
540 scale[j] =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
541 vars[j] = nlhdlrexprdata->vars[
i];
547 dw0 = box[1] - box[0];
548 dw1 = box[3] - box[2];
553 isupperright = ( (xstar[0] - box[0]) * dw1 + (xstar[1] - box[3]) * dw0 ) > 0.0;
556 f0w0l = pow(box[0], refexponents[0]);
557 f0w0u = pow(box[1], refexponents[0]);
558 f1w1l = pow(box[2], refexponents[1]);
559 f1w1u = pow(box[3], refexponents[1]);
560 fw0lw1u = f0w0l * f1w1u;
561 fw0uw1l = f0w0u * f1w1l;
566 facetcoefs[0] = (fw0uw1u - fw0lw1u) / dw0;
567 facetcoefs[1] = (fw0uw1u - fw0uw1l) / dw1;
568 facetconstant = fw0uw1u - facetcoefs[0] * box[1] - facetcoefs[1] * box[3];
574 facetcoefs[0] = (fw0uw1l - fw0lw1l) / dw0;
575 facetcoefs[1] = (fw0lw1u - fw0lw1l) / dw1;
576 facetconstant = fw0lw1l - facetcoefs[0] * box[0] - facetcoefs[1] * box[2];
626 nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
630 evaldata.
sign = sign;
635 xstar = nlhdlrexprdata->xstar;
636 box = nlhdlrexprdata->box;
638 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
640 if( nlhdlrexprdata->signs[
i] != sign )
643 box[2 * j] = nlhdlrexprdata->intervals[
i].inf;
644 box[2 * j + 1] = nlhdlrexprdata->intervals[
i].sup;
645 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
651 facetcoefs = nlhdlrexprdata->facetcoefs;
653 nsignvars, targetvalue, success, facetcoefs, &facetconstant) );
664 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
666 if( nlhdlrexprdata->signs[
i] != sign )
668 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
710 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
712 if( nlhdlrexprdata->signs[
i] != sign )
714 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
717 refexponent = nlhdlrexprdata->refexponents[
i];
718 sumrefexponents += refexponent;
719 funcval *= pow(val, refexponent);
723 facetconstant = (1 - sumrefexponents) * funcval;
725 for(
i = 0;
i < nlhdlrexprdata->nvars; ++
i )
727 if( nlhdlrexprdata->signs[
i] != sign )
729 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
730 var = nlhdlrexprdata->vars[
i];
733 facetcoef = nlhdlrexprdata->refexponents[
i] * funcval / val;
769 *addedbranchscores =
FALSE;
772 if( !nlhdlrexprdata->isstorecapture )
779 isboxsignomial =
FALSE;
782 if( !isboxsignomial )
793 overmultiplier = 1.0;
794 undermultiplier = -1.0;
795 nundervars = nlhdlrexprdata->nnegvars;
802 overmultiplier = -1.0;
803 undermultiplier = 1.0;
804 nundervars = nlhdlrexprdata->nposvars;
809 for(
i = 0;
i < nlhdlrexprdata->nvars;
i++ )
811 if( nlhdlrexprdata->signs[
i] == oversign )
813 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
814 targetunder *= pow(
SCIPgetSolVal(
scip,
sol, nlhdlrexprdata->vars[
i]) / scale, nlhdlrexprdata->refexponents[
i]);
818#ifdef SCIP_SIGCUT_DEBUG
823 SCIPinfoMessage(
scip,
NULL,
" Auxvalue: %f, targetvalue: %f, %sestimate.", auxvalue, targetvalue, overestimate ?
"over" :
"under");
826 for(
i = 0;
i < nlhdlrexprdata->nvars;
i++ )
828 if( nlhdlrexprdata->signs[
i] == undersign )
830 scale =
i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
831 targetover *= pow(
SCIPgetSolVal(
scip,
sol, nlhdlrexprdata->vars[
i]) / scale, nlhdlrexprdata->refexponents[
i]);
835 undersign ?
"positive" :
"negative", oversign ?
"positive" :
"negative");
836 SCIPinfoMessage(
scip,
NULL,
" Undervalue (targetover): %f, overvalue (targetunder): %f.", targetover, targetunder);
844 if( nundervars <= nlhdlrdata->maxnundervars )
907 (*nlhdlrexprdata)->nfactors = nf;
908 (*nlhdlrexprdata)->nvars =
nvars;
918 for(
c = 0;
c < nf;
c++ )
922 ismultilinear =
FALSE;
949 (*nlhdlrexprdata)->isstorecapture =
FALSE;
954 for(
c = 0;
c < nf;
c++ )
958 if( (*nlhdlrexprdata)->exponents[
c] > 0.0 )
961 sumlexponents += (*nlhdlrexprdata)->exponents[
c];
962 (*nlhdlrexprdata)->signs[
c] =
TRUE;
968 sumrexponents -= (*nlhdlrexprdata)->exponents[
c];
969 (*nlhdlrexprdata)->signs[
c] =
FALSE;
973 (*nlhdlrexprdata)->signs[nf] =
FALSE;
974 (*nlhdlrexprdata)->nposvars = nposvars;
975 (*nlhdlrexprdata)->nnegvars = nf - nposvars + 1;
978 normalize =
MAX(sumlexponents, sumrexponents);
980 for(
c = 0;
c < nf;
c++ )
982 if( (*nlhdlrexprdata)->signs[
c] )
983 (*nlhdlrexprdata)->refexponents[
c] = (*nlhdlrexprdata)->exponents[
c] / normalize;
985 (*nlhdlrexprdata)->refexponents[
c] = -(*nlhdlrexprdata)->exponents[
c] / normalize;
987 (*nlhdlrexprdata)->refexponents[nf] = 1.0 / normalize;
990 for(
c = 0;
c < nf;
c++ )
997 if( *nlhdlrexprdata !=
NULL )
1002#ifdef SCIP_SIGCUT_DEBUG
1003 if( *participating )
1005 SCIPdebugMsg(
scip,
"scip depth: %d, step: %d, expr pointer: %p, expr data pointer: %p, detected expr: total vars (exps) %d ",
1022 *auxvalue = nlhdlrexprdata->coef;
1023 for(
c = 0;
c < nlhdlrexprdata->nfactors; ++
c )
1033 *auxvalue *= pow(val, nlhdlrexprdata->exponents[
c]);
1076 for(
c = 0;
c < (*nlhdlrexprdata)->nfactors;
c++ )
1082 if( (*nlhdlrexprdata)->isstorecapture )
1084 for(
c = 0;
c < (*nlhdlrexprdata)->nvars;
c++ )
1086 if( (*nlhdlrexprdata)->vars[
c] !=
NULL )
1130 "maximum number of variables when underestimating a concave power function",
1133 "minimum scale factor when scaling a cut",
constraint handler for nonlinear constraints specified by algebraic expressions
void SCIPestimateRoot(SCIP *scip, SCIP_Real exponent, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *success)
power and signed power expression handlers
variable expression handler
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_RETCODE SCIPcomputeFacetVertexPolyhedralNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool overestimate, SCIP_DECL_VERTEXPOLYFUN((*function)), void *fundata, SCIP_Real *xstar, SCIP_Real *box, int nallvars, SCIP_Real targetvalue, SCIP_Bool *success, SCIP_Real *facetcoefs, SCIP_Real *facetconstant)
#define SCIP_DECL_VERTEXPOLYFUN(f)
int SCIPgetSubscipDepth(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPincludeNlhdlrSignomial(SCIP *scip)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPgetExprMonomialData(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
void SCIPcaptureExpr(SCIP_EXPR *expr)
struct SCIP_Interval SCIP_INTERVAL
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemory(scip, ptr)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr,)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)),)
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr,)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr,)
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
#define NLHDLR_DETECTPRIORITY
#define NLHDLR_ENFOPRIORITY
#define NLHDLR_MAXNUNDERVARS
static void reformRowprep(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_ROWPREP *rowprep, SCIP_Real mincutscale, SCIP_Bool *success)
static SCIP_RETCODE estimateSpecialPower(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_Bool overestimate, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *isspecial, SCIP_Bool *success)
static void checkSignomialBounds(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool *isboxsignomial)
static SCIP_RETCODE overEstimatePower(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
static SCIP_RETCODE underEstimatePower(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_Real targetvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
static SCIP_RETCODE storeCaptureVars(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static void freeExprDataMem(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool ispartial)
#define NLHDLR_MINCUTSCALE
signomial nonlinear handler
preparation of a linear inequality to become a SCIP_ROW
public functions of nonlinear handlers of nonlinear constraints
static void printSignomial(SCIP *scip, FILE *file, char *linebuffer, int *linecnt, SCIP_EXPR *expr, SCIP_Real coef, SCIP_Bool needsign)
public functions to work with algebraic expressions
SCIP_NLHDLREXPRDATA * nlhdlrexprdata
struct SCIP_Conshdlr SCIP_CONSHDLR
struct SCIP_Expr SCIP_EXPR
struct SCIP_RowPrep SCIP_ROWPREP
#define SCIP_DECL_NLHDLREVALAUX(x)
#define SCIP_DECL_NLHDLRESTIMATE(x)
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
#define SCIP_NLHDLR_METHOD_SEPABOTH
#define SCIP_DECL_NLHDLRCOPYHDLR(x)
#define SCIP_DECL_NLHDLRFREEEXPRDATA(x)
#define SCIP_DECL_NLHDLRDETECT(x)
struct SCIP_Nlhdlr SCIP_NLHDLR
#define SCIP_DECL_NLHDLRFREEHDLRDATA(x)
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
enum SCIP_Retcode SCIP_RETCODE