Detailed Description
convexproj separator
Definition in file sepa_convexproj.c.
#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "nlpi/pub_expr.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_nonlinear.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 /* 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 } |
Macro Definition Documentation
◆ SEPA_NAME
#define SEPA_NAME "convexproj" |
Definition at line 58 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 59 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 0 |
Definition at line 60 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_FREQ
#define SEPA_FREQ -1 |
Definition at line 61 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 62 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 63 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 64 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 66 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ DEFAULT_NLPTIMELIMIT
#define DEFAULT_NLPTIMELIMIT 0.0 |
default time limit of NLP solver; 0.0 for no limit
Definition at line 67 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ DEFAULT_NLPITERLIM
#define DEFAULT_NLPITERLIM 250 |
default NLP iteration limit
Definition at line 68 of file sepa_convexproj.c.
Referenced by SCIPincludeSepaConvexproj().
◆ VIOLATIONFAC
#define VIOLATIONFAC 100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */ |
Definition at line 70 of file sepa_convexproj.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ NLPVERBOSITY
#define NLPVERBOSITY 0 |
Typedef Documentation
◆ CONVEXSIDE
typedef enum ConvexSide CONVEXSIDE |
Definition at line 84 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 79 of file sepa_convexproj.c.
Function Documentation
◆ sepadataClear()
|
static |
clears the sepadata data
- Parameters
-
scip SCIP data structure sepadata separator data
Definition at line 123 of file sepa_convexproj.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintFree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPnlpiFreeProblem().
Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), and SCIP_DECL_SEPAFREE().
◆ computeGradient()
|
static |
computes gradient of exprtree at projection
- Parameters
-
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 163 of file sepa_convexproj.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetSolVal(), TRUE, and x.
Referenced by generateCut().
◆ generateCut()
|
static |
computes gradient cut (linearization) of nlrow at projection
- Parameters
-
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 209 of file sepa_convexproj.c.
References SCIP_QuadElement::coef, computeGradient(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, NULL, 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().
◆ 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 329 of file sepa_convexproj.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPnlpiSetObjective().
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 373 of file sepa_convexproj.c.
References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, NLPVERBOSITY, NULL, 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(), SCIPhashmapGetImageInt(), 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().
◆ 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 626 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 684 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(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), 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 743 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 764 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 782 of file sepa_convexproj.c.
References computeMaxViolation(), FALSE, NULL, 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.