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 |
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_SEPACOPY (sepaCopyConvexproj) |
static | SCIP_DECL_SEPAFREE (sepaFreeConvexproj) |
static | SCIP_DECL_SEPAEXITSOL (sepaExitsolConvexproj) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpConvexproj) |
SCIP_RETCODE | SCIPincludeSepaConvexproj (SCIP *scip) |
#define SEPA_NAME "convexproj" |
Definition at line 68 of file sepa_convexproj.c.
#define SEPA_DESC "separate at projection of point onto convex region" |
Definition at line 69 of file sepa_convexproj.c.
#define SEPA_PRIORITY 0 |
Definition at line 70 of file sepa_convexproj.c.
#define SEPA_FREQ -1 |
Definition at line 71 of file sepa_convexproj.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 72 of file sepa_convexproj.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 73 of file sepa_convexproj.c.
#define SEPA_DELAY TRUE |
should separation method be delayed, if other separators found cuts?
Definition at line 74 of file sepa_convexproj.c.
#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.
#define DEFAULT_NLPITERLIM 250 |
default NLP iteration limit
Definition at line 77 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj(), and SCIPincludeSepaGauge().
#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(), SCIP_DECL_SEPAEXECLP(), and separateCuts().
typedef enum ConvexSide CONVEXSIDE |
Definition at line 91 of file sepa_convexproj.c.
enum ConvexSide |
side that makes an nlrow convex
Enumerator | |
---|---|
LHS | left hand side |
RHS | right hand side |
Definition at line 86 of file sepa_convexproj.c.
|
static |
clears the sepadata data
scip | SCIP data structure |
sepadata | separator data |
Definition at line 127 of file sepa_convexproj.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and sepadata.
Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), and SCIP_DECL_SEPAFREE().
|
static |
computes gradient cut (linearization) of nlrow at projection
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 assert(), FALSE, i, 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(), sepadata, TRUE, and var.
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 268 of file sepa_convexproj.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateExprPow(), SCIPcreateExprSum(), SCIPcreateExprVaridx(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPreleaseExpr(), sepadata, and var.
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 321 of file sepa_convexproj.c.
References assert(), BMSclearMemoryArray, FALSE, generateCut(), i, LHS, MAX, NULL, REALABS, result, 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(), sepadata, sol, SQR, TRUE, and var.
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 557 of file sepa_convexproj.c.
References assert(), i, LHS, MAX, NULL, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetNlRowSolActivity(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), sepadata, and sol.
Referenced by mod2matrixPreprocessRows(), and 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 615 of file sepa_convexproj.c.
References assert(), i, LHS, NULL, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), and sepadata.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 671 of file sepa_convexproj.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaConvexproj(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 685 of file sepa_convexproj.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, sepadata, and sepadataClear().
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 706 of file sepa_convexproj.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), sepadata, and sepadataClear().
|
static |
LP solution separation method of separator
Definition at line 724 of file sepa_convexproj.c.
References assert(), computeMaxViolation(), depth, FALSE, NULL, result, 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(), sepadata, sepadataClear(), separateCuts(), setQuadraticObj(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.