Detailed Description
convexproj separator
Definition in file sepa_convexproj.c.
#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "scip/scip_expr.h"
#include "scip/scip_nlpi.h"
#include "scip/expr_varidx.h"
#include "scip/expr_pow.h"
#include "scip/expr_sum.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_nlp.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/sepa_convexproj.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 |
#define | DEFAULT_NLPITERLIM 250 |
#define | VIOLATIONFAC 100 |
Typedefs | |
typedef enum ConvexSide | CONVEXSIDE |
Enumerations | |
enum | ConvexSide { LHS = 0, RHS = 1, LHS = 0, RHS = 1 } |
Functions | |
static SCIP_RETCODE | sepadataClear (SCIP *scip, SCIP_SEPADATA *sepadata) |
static SCIP_RETCODE | generateCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *projection, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_Real activity, SCIP_EXPRITER *exprit, SCIP_ROW **row) |
static SCIP_RETCODE | setQuadraticObj (SCIP *scip, SCIP_SEPADATA *sepadata) |
static SCIP_RETCODE | separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result) |
static SCIP_RETCODE | computeMaxViolation (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *maxviolation) |
static SCIP_RETCODE | storeNonlinearConvexNlrows (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows) |
static | SCIP_DECL_SEPAFREE (sepaFreeConvexproj) |
static | SCIP_DECL_SEPAEXITSOL (sepaExitsolConvexproj) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpConvexproj) |
SCIP_RETCODE | SCIPincludeSepaConvexproj (SCIP *scip) |
Macro Definition Documentation
◆ SEPA_NAME
#define SEPA_NAME "convexproj" |
Definition at line 68 of file sepa_convexproj.c.
Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaConvexproj().
◆ SEPA_DESC
#define SEPA_DESC "separate at projection of point onto convex region" |
Definition at line 69 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 0 |
Definition at line 70 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_FREQ
#define SEPA_FREQ -1 |
Definition at line 71 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 72 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 73 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_DELAY
#define SEPA_DELAY TRUE |
should separation method be delayed, if other separators found cuts?
Definition at line 74 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ DEFAULT_MAXDEPTH
#define DEFAULT_MAXDEPTH -1 |
maximum depth at which the separator is applied; -1 means no limit
Definition at line 76 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ DEFAULT_NLPITERLIM
#define DEFAULT_NLPITERLIM 250 |
default NLP iteration limit
Definition at line 77 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ VIOLATIONFAC
#define VIOLATIONFAC 100 |
points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol()
Definition at line 79 of file sepa_convexproj.c.
Referenced by SCIP_DECL_SEPAEXECLP().
Typedef Documentation
◆ CONVEXSIDE
typedef enum ConvexSide CONVEXSIDE |
Definition at line 91 of file sepa_convexproj.c.
Enumeration Type Documentation
◆ ConvexSide
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 86 of file sepa_convexproj.c.
Function Documentation
◆ sepadataClear()
|
static |
clears the sepadata data
- Parameters
-
scip SCIP data structure sepadata separator data
Definition at line 127 of file sepa_convexproj.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().
Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), and SCIP_DECL_SEPAFREE().
◆ generateCut()
|
static |
computes gradient cut (linearization) of nlrow at projection
- Parameters
-
scip SCIP data structure sepa the cut separator itself 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 exprit expression iterator that can be used row storage for cut
Definition at line 166 of file sepa_convexproj.c.
References FALSE, LHS, NULL, RHS, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugPrintf, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfinity(), SCIPisExprVar(), SCIPisInfinity(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetName(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetRhs(), SCIPprintRow(), SCIPsepaGetData(), SCIPsnprintf(), and TRUE.
Referenced by separateCuts().
◆ setQuadraticObj()
|
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()
- Parameters
-
scip SCIP data structure sepadata the cut separator data
Definition at line 268 of file sepa_convexproj.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateExprPow(), SCIPcreateExprSum(), SCIPcreateExprVaridx(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPreleaseExpr().
Referenced by SCIP_DECL_SEPAEXECLP().
◆ separateCuts()
|
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).
- Parameters
-
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 321 of file sepa_convexproj.c.
References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, NULL, REALABS, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, 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, SCIPcreateExpriter(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNLPObjval(), SCIPgetNLPVars(), SCIPgetNlRowSolActivity(), SCIPgetNNLPVars(), SCIPgetSolVal(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsetSolVal(), SCIPsolveNlpi, SCIPvarGetLbLocal(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ computeMaxViolation()
|
static |
computes the violation and maximum violation of the convex nlrows stored in sepadata wrt sol
- Parameters
-
scip SCIP data structure sepadata separator data sol solution that should be separated maxviolation buffer to store maximum violation
Definition at line 557 of file sepa_convexproj.c.
References LHS, MAX, NULL, 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().
◆ storeNonlinearConvexNlrows()
|
static |
stores, from the constraints represented by nlrows, the nonlinear convex ones in sepadata
- Parameters
-
scip SCIP data structure sepadata separator data nlrows nlrows from which to store convex ones nnlrows number of nlrows
Definition at line 615 of file sepa_convexproj.c.
References LHS, NULL, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().
Referenced by SCIP_DECL_SEPAEXECLP().
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 673 of file sepa_convexproj.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadataClear().
◆ SCIP_DECL_SEPAEXITSOL()
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 694 of file sepa_convexproj.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and sepadataClear().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 712 of file sepa_convexproj.c.
References computeMaxViolation(), FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProblemRows(), SCIPblkmem(), SCIPcreateCurrentSol(), SCIPcreateNlpiProblemFromNlRows(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPfeastol(), SCIPfreeSol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPsepaGetData(), SCIPupdateNlpiProblem(), sepadataClear(), separateCuts(), setQuadraticObj(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.