convexproj separator
Definition in file sepa_convexproj.c.
#include <assert.h>
#include <string.h>
#include "scip/sepa_convexproj.h"
#include "scip/nlp.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
Go to the source code of this file.
Macros | |
#define | SEPA_NAME "convexproj" |
#define | SEPA_DESC "separate at projection of point onto convex region" |
#define | SEPA_PRIORITY 0 |
#define | SEPA_FREQ -1 |
#define | SEPA_MAXBOUNDDIST 1.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY TRUE |
#define | DEFAULT_MAXDEPTH -1 /* maximum depth at which the separator is applied; -1 means no limit */ |
#define | DEFAULT_NLPTIMELIMIT 0.0 |
#define | DEFAULT_NLPITERLIM 250 |
#define | VIOLATIONFAC 100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */ |
#define | NLPVERBOSITY 0 |
Typedefs | |
typedef enum ConvexSide | CONVEXSIDE |
Enumerations | |
enum | ConvexSide { LHS = 0, RHS = 1, LHS = 0, RHS = 1 } |
#define SEPA_NAME "convexproj" |
Definition at line 35 of file sepa_convexproj.c.
Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaConvexproj().
#define SEPA_DESC "separate at projection of point onto convex region" |
Definition at line 36 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define SEPA_PRIORITY 0 |
Definition at line 37 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define SEPA_FREQ -1 |
Definition at line 38 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 39 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 40 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define SEPA_DELAY TRUE |
should separation method be delayed, if other separators found cuts?
Definition at line 41 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define DEFAULT_MAXDEPTH -1 /* maximum depth at which the separator is applied; -1 means no limit */ |
Definition at line 43 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define DEFAULT_NLPTIMELIMIT 0.0 |
default time limit of NLP solver; 0.0 for no limit
Definition at line 44 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define DEFAULT_NLPITERLIM 250 |
default NLP iteration limit
Definition at line 45 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
#define VIOLATIONFAC 100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */ |
Definition at line 47 of file sepa_convexproj.c.
Referenced by SCIP_DECL_SEPAEXECLP().
#define NLPVERBOSITY 0 |
typedef enum ConvexSide CONVEXSIDE |
Definition at line 61 of file sepa_convexproj.c.
enum ConvexSide |
side that makes an nlrow convex
Enumerator | |
---|---|
LHS | left hand side |
RHS | right hand side |
LHS | left hand side |
RHS | right hand side |
Definition at line 56 of file sepa_convexproj.c.
|
static |
clears the sepadata data
scip | SCIP data structure |
sepadata | separator data |
Definition at line 100 of file sepa_convexproj.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPexprintFree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPnlpiFreeProblem().
Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), and SCIP_DECL_SEPAFREE().
|
static |
computes gradient of exprtree at projection
scip | SCIP data structure |
exprint | expressions interpreter |
projection | point where we compute gradient |
exprtree | exprtree for which we compute the gradient |
grad | buffer to store the gradient |
Definition at line 140 of file sepa_convexproj.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetSolVal(), and TRUE.
Referenced by generateCut().
|
static |
computes gradient cut (linearization) of nlrow at projection
scip | SCIP data structure |
sepa | the cut separator itself |
exprint | expression interpreter |
projection | point where we compute gradient cut |
nlrow | constraint for which we generate gradient cut |
convexside | which side makes the nlrow convex |
activity | activity of constraint at projection |
row | storage for cut |
Definition at line 186 of file sepa_convexproj.c.
References SCIP_QuadElement::coef, computeGradient(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, RHS, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugPrintf, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetName(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPprintRow(), SCIPsepaGetData(), SCIPsnprintf(), and TRUE.
Referenced by separateCuts().
|
static |
set quadratic part of objective function: \( \sum_i x_i^2 \); the objective function is \( ||x - x_0||^2 \), where \( x_0 \) is the point to separate; the only part that changes is the term \( -2 \langle x_0, x \rangle \) which is linear and is set every time we want to separate a point, see separateCuts
scip | SCIP data structure |
sepadata | the cut separator data |
Definition at line 306 of file sepa_convexproj.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImage(), and SCIPnlpiSetObjective().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
projects sol onto convex relaxation (stored in sepadata) and tries to generate gradient cuts at the projection it generates cuts only for the constraints that were violated by the LP solution and are now active or still violated (in case we don't solve to optimality).
scip | SCIP data structure |
sepa | the cut separator itself |
sol | solution that should be separated |
result | pointer to store the result of the separation call |
Definition at line 350 of file sepa_convexproj.c.
References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, NLPVERBOSITY, REALABS, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBINFEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_NLPSOLSTAT_LOCOPT, SCIP_NLPSOLSTAT_UNBOUNDED, SCIP_NLPSOLSTAT_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPABORT, SCIPaddRow(), SCIPallocBufferArray, SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNLPObjval(), SCIPgetNLPVars(), SCIPgetNlRowSolActivity(), SCIPgetNNLPVars(), SCIPgetRealParam(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisInfinity(), SCIPnlpiChgLinearCoefs(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
computes the violation and maximum violation of the convex nlrows stored in sepadata wrt sol
scip | SCIP data structure |
sepadata | separator data |
sol | solution that should be separated |
maxviolation | buffer to store maximum violation |
Definition at line 604 of file sepa_convexproj.c.
References LHS, MAX, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetNlRowSolActivity(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
stores, from the constraints represented by nlrows, the nonlinear convex ones in sepadata
scip | SCIP data structure |
sepadata | separator data |
nlrows | nlrows from which to store convex ones |
nnlrows | number of nlrows |
Definition at line 662 of file sepa_convexproj.c.
References LHS, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), and SCIPnlrowGetRhs().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 721 of file sepa_convexproj.c.
References SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadataClear().
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 742 of file sepa_convexproj.c.
References SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and sepadataClear().
|
static |
LP solution separation method of separator
Definition at line 760 of file sepa_convexproj.c.
References computeMaxViolation(), FALSE, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProbRows(), SCIPblkmem(), SCIPcreateCurrentSol(), SCIPcreateNlpiProb(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPexprintCreate(), SCIPfeastol(), SCIPfreeSol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPnlpiCreateProblem(), SCIPsepaGetData(), SCIPupdateNlpiProb(), sepadataClear(), separateCuts(), setQuadraticObj(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.