35 #define SEPA_NAME "convexproj" 36 #define SEPA_DESC "separate at projection of point onto convex region" 37 #define SEPA_PRIORITY 0 39 #define SEPA_MAXBOUNDDIST 1.0 40 #define SEPA_USESSUBSCIP FALSE 41 #define SEPA_DELAY TRUE 43 #define DEFAULT_MAXDEPTH -1 44 #define DEFAULT_NLPTIMELIMIT 0.0 45 #define DEFAULT_NLPITERLIM 250 47 #define VIOLATIONFAC 100 49 #define NLPVERBOSITY 0 105 assert(sepadata !=
NULL);
108 if( sepadata->nlrowssize > 0 )
113 sepadata->nlrowssize = 0;
116 if( sepadata->nlpiprob !=
NULL )
118 assert(sepadata->nlpi !=
NULL);
126 sepadata->nlpinvars = 0;
127 sepadata->nnlrows = 0;
129 assert(sepadata->nlpinvars == 0);
130 assert(sepadata->nnlrows == 0);
131 assert(sepadata->nlrowssize == 0);
133 sepadata->skipsepa =
FALSE;
153 assert(scip !=
NULL);
154 assert(exprint !=
NULL);
155 assert(projection !=
NULL);
156 assert(exprtree !=
NULL);
157 assert(grad !=
NULL);
170 for( i = 0; i < nvars; ++i )
202 assert(scip !=
NULL);
203 assert(sepa !=
NULL);
204 assert(exprint !=
NULL);
205 assert(nlrow !=
NULL);
210 assert(sepadata !=
NULL);
283 if( convexside ==
RHS )
290 assert(convexside ==
LHS);
314 assert(scip !=
NULL);
315 assert(sepadata !=
NULL);
316 assert(sepadata->nlpi !=
NULL);
317 assert(sepadata->nlpiprob !=
NULL);
318 assert(sepadata->var2nlpiidx !=
NULL);
319 assert(sepadata->nlpinvars > 0);
322 for( i = 0; i < sepadata->nlpinvars; i++ )
326 var = sepadata->nlpivars[i];
330 quadelems[i].
idx2 = quadelems[i].
idx1;
331 quadelems[i].
coef = 1.0;
370 assert(sepa !=
NULL);
374 assert(result !=
NULL);
375 assert(sepadata !=
NULL);
376 assert(sepadata->nnlrows > 0);
377 assert(sepadata->nlpi !=
NULL);
378 assert(sepadata->nlpinvars > 0);
379 assert(sepadata->nlrows !=
NULL);
380 assert(sepadata->nlpiprob !=
NULL);
381 assert(sepadata->var2nlpiidx !=
NULL);
382 assert(sepadata->convexsides !=
NULL);
383 assert(sepadata->constraintviolation !=
NULL);
385 nlpinvars = sepadata->nlpinvars;
391 for( i = 0; i < nlpinvars; i++ )
395 var = sepadata->nlpivars[i];
406 SCIPdebugMsg(scip,
"Don't separate points too close to infinity\n");
423 if( timelimit <= 1.0 )
429 if( sepadata->nlptimelimit > 0.0 )
430 timelimit =
MIN(sepadata->nlptimelimit, timelimit);
433 iterlimit = sepadata->nlpiterlimit > 0 ? sepadata->nlpiterlimit : INT_MAX;
458 assert(nlpisol !=
NULL);
461 for( i = 0; i < nlpinvars; i++ )
465 var = sepadata->nlpivars[i];
474 for( i = 0; i < sepadata->nnlrows; ++i )
484 convexside = sepadata->convexsides[i];
485 nlrow = sepadata->nlrows[i];
486 assert(nlrow !=
NULL);
500 SCIP_CALL(
generateCut(scip, sepa, sepadata->exprinterpreter, projection, nlrow, convexside, activity,
503 SCIPdebugMsg(scip,
"active or violated nlrow: (sols vio: %e)\n", sepadata->constraintviolation[i]);
577 SCIPerrorMessage(
"Projection NLP is not unbounded by construction, should not get here!\n");
589 sepadata->skipsepa =
TRUE;
615 assert(sepadata !=
NULL);
616 assert(sepadata->nnlrows > 0);
617 assert(sepadata->nlrows !=
NULL);
618 assert(sepadata->convexsides !=
NULL);
619 assert(sepadata->constraintviolation !=
NULL);
622 for( i = 0; i < sepadata->nnlrows; i++ )
627 nlrow = sepadata->nlrows[i];
633 if( sepadata->convexsides[i] ==
RHS )
639 sepadata->constraintviolation[i] =
MAX(violation, 0.0);
641 if( sepadata->convexsides[i] ==
LHS )
647 sepadata->constraintviolation[i] =
MAX(violation, 0.0);
651 if( *maxviolation < sepadata->constraintviolation[i] )
652 *maxviolation = sepadata->constraintviolation[i];
655 SCIPdebugMsg(scip,
"Maximum violation %g\n", *maxviolation);
672 assert(scip !=
NULL);
673 assert(sepadata !=
NULL);
677 sepadata->nlrowssize = nnlrows;
683 sepadata->nnlrows = 0;
684 for( i = 0; i < nnlrows; ++i )
689 assert(nlrow !=
NULL);
699 sepadata->convexsides[sepadata->nnlrows] =
RHS;
700 sepadata->nlrows[sepadata->nnlrows] = nlrow;
701 ++(sepadata->nnlrows);
705 sepadata->convexsides[sepadata->nnlrows] =
LHS;
706 sepadata->nlrows[sepadata->nnlrows] = nlrow;
707 ++(sepadata->nnlrows);
730 assert(sepadata !=
NULL);
747 assert(sepa !=
NULL);
751 assert(sepadata !=
NULL);
771 assert(sepadata !=
NULL);
777 if( sepadata->skipsepa )
779 SCIPdebugMsg(
scip,
"not running because convex relaxation is uninteresting or numerically unstable\n");
798 SCIPdebugMsg(
scip,
"NLP not constructed, skipping convex projection separator\n");
807 assert(sepadata->nlpiprob ==
NULL);
811 if( sepadata->nlpiprob ==
NULL )
817 if( sepadata->nnlrows < 1 )
820 sepadata->skipsepa =
TRUE;
829 assert(sepadata->nlpi !=
NULL);
866 SCIPdebugMsg(
scip,
"solution doesn't violate constraints enough, do not separate\n");
905 sepaExeclpConvexproj,
NULL,
907 assert(sepa !=
NULL);
915 "maximal depth at which the separator is applied (-1: unlimited)",
919 "iteration limit of NLP solver; 0 for no limit",
923 "time limit of NLP solver; 0.0 for no limit",
enum SCIP_Result SCIP_RESULT
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
int SCIPgetNNLPNlRows(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPfeastol(SCIP *scip)
static SCIP_RETCODE storeNonlinearConvexNlrows(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
methods to interpret (evaluate) an expression tree "fast"
static SCIP_DECL_SEPAEXECLP(sepaExeclpConvexproj)
static SCIP_RETCODE computeMaxViolation(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *maxviolation)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
static SCIP_DECL_SEPAEXITSOL(sepaExitsolConvexproj)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
static SCIP_RETCODE setQuadraticObj(SCIP *scip, SCIP_SEPADATA *sepadata)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetNlRowSolActivity(SCIP *scip, SCIP_NLROW *nlrow, SCIP_SOL *sol, SCIP_Real *activity)
SCIP_EXPRCURV SCIPnlrowGetCurvature(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
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_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
int SCIPnlrowGetNQuadElems(SCIP_NLROW *nlrow)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
int SCIPgetNNLPVars(SCIP *scip)
SCIP_VAR ** SCIPnlrowGetQuadVars(SCIP_NLROW *nlrow)
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
SCIP_RETCODE SCIPincludeSepaConvexproj(SCIP *scip)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
internal methods for NLP management
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
int SCIPgetNNlpis(SCIP *scip)
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
int SCIPgetNLPRows(SCIP *scip)
SCIP_QUADELEM * SCIPnlrowGetQuadElems(SCIP_NLROW *nlrow)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
SCIP_RETCODE SCIPnlpiSetObjective(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, int nlins, const int *lininds, const SCIP_Real *linvals, int nquadelems, const SCIP_QUADELEM *quadelems, const int *exprvaridxs, const SCIP_EXPRTREE *exprtree, const SCIP_Real constant)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
static SCIP_RETCODE computeGradient(SCIP *scip, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_EXPRTREE *exprtree, SCIP_Real *grad)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
SCIP_EXPRINTDATA * SCIPexprtreeGetInterpreterData(SCIP_EXPRTREE *tree)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
SCIP_RETCODE SCIPexprintGrad(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool new_varvals, SCIP_Real *val, SCIP_Real *gradient)
int SCIPgetNVars(SCIP *scip)
SCIP_EXPRTREE * SCIPnlrowGetExprtree(SCIP_NLROW *nlrow)
static SCIP_RETCODE generateCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_Real activity, SCIP_ROW **row)
#define DEFAULT_NLPITERLIM
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
static SCIP_DECL_SEPAFREE(sepaFreeConvexproj)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPprintNlRow(SCIP *scip, SCIP_NLROW *nlrow, FILE *file)
SCIP_RETCODE SCIPcreateCurrentSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPnlpiChgLinearCoefs(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, const int idx, int nvals, const int *varidxs, const SCIP_Real *vals)
SCIP_Real SCIPgetNLPObjval(SCIP *scip)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
#define SEPA_MAXBOUNDDIST
#define BMSclearMemoryArray(ptr, num)
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
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)
enum ConvexSide CONVEXSIDE
#define DEFAULT_NLPTIMELIMIT
struct SCIP_SepaData SCIP_SEPADATA
static SCIP_RETCODE sepadataClear(SCIP *scip, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)