gauge separator
Definition in file sepa_gauge.c.
#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "scip/scip_nlpi.h"
#include "scip/nlpi_ipopt.h"
#include "scip/nlpioracle.h"
#include "scip/scip_expr.h"
#include "scip/pub_expr.h"
#include "scip/pub_lp.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_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/sepa_gauge.h"
Go to the source code of this file.
Macros | |
#define | SEPA_NAME "gauge" |
#define | SEPA_DESC "gauge separator" |
#define | SEPA_PRIORITY 0 |
#define | SEPA_FREQ -1 |
#define | SEPA_MAXBOUNDDIST 1.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY FALSE |
#define | VIOLATIONFAC 100 |
#define | MAX_ITER 75 |
#define | DEFAULT_NLPITERLIM 1000 |
#define | NLPFEASFAC 1e- |
#define | INTERIOROBJVARLB -100 |
#define SEPA_NAME "gauge" |
Definition at line 68 of file sepa_gauge.c.
#define SEPA_DESC "gauge separator" |
Definition at line 69 of file sepa_gauge.c.
#define SEPA_PRIORITY 0 |
Definition at line 70 of file sepa_gauge.c.
#define SEPA_FREQ -1 |
Definition at line 71 of file sepa_gauge.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 72 of file sepa_gauge.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 73 of file sepa_gauge.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 74 of file sepa_gauge.c.
#define VIOLATIONFAC 100 |
constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol
Definition at line 76 of file sepa_gauge.c.
#define MAX_ITER 75 |
maximum number of iterations for the line search
Definition at line 77 of file sepa_gauge.c.
Referenced by findBoundaryPoint().
#define DEFAULT_NLPITERLIM 1000 |
default NLP iteration limit
Definition at line 79 of file sepa_gauge.c.
#define NLPFEASFAC 1e- |
NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance
Definition at line 81 of file sepa_gauge.c.
Referenced by computeInteriorPoint().
#define INTERIOROBJVARLB -100 |
lower bound of the objective variable when computing interior point
Definition at line 83 of file sepa_gauge.c.
Referenced by computeInteriorPoint().
Definition at line 104 of file sepa_gauge.c.
enum ConvexSide |
side that makes a nlrow convex
Enumerator | |
---|---|
LHS | left hand side |
RHS | right hand side |
Definition at line 90 of file sepa_gauge.c.
enum Position |
position of a point
Enumerator | |
---|---|
INTERIOR | point is in the interior of the region |
BOUNDARY | point is in the boundary of the region |
EXTERIOR | point is in the exterior of the region |
Definition at line 98 of file sepa_gauge.c.
|
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 132 of file sepa_gauge.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 |
computes an interior point of a convex NLP relaxation
builds the convex relaxation, modifies it to find an interior point, solves it and frees it; more details in sepa_gauge.h
scip | SCIP data structure |
sepadata | separator data |
Definition at line 192 of file sepa_gauge.c.
References assert(), FALSE, i, INTERIOROBJVARLB, MAX, SCIP_NlpStatistics::niterations, NLPFEASFAC, NULL, nvars, SCIP_CALL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProblemRows(), SCIPblkmem(), SCIPcreateNlpiProblemFromNlRows(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPfeastol(), SCIPgetCutoffbound(), SCIPgetLPRows(), SCIPgetNlpiOracleIpopt(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPnlpiGetName(), SCIPnlpiOracleGetNConstraints(), SCIPnlpiOracleGetNVars(), SCIPnlpiOracleIsConstraintNonlinear(), SCIPnlpiOraclePrintProblem(), SCIPsetSolVal(), SCIPsolveNlpi, sepadata, SCIP_NlpStatistics::totaltime, TRUE, and var.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
find whether point is in the interior, at the boundary, or in the exterior of the region described by the intersection of nlrows[i]
≤ rhs if convexsides[i]
= RHS or lhs ≤ nlrows[i]
if convexsides[i]
= LHS
scip | SCIP data structure |
nlrows | nlrows defining the region |
nlrowsidx | indices of nlrows defining the region |
nnlrowsidx | number of nlrows indices |
convexsides | sides of the nlrows involved in the region |
point | point for which we want to know its position |
position | buffer to store position of sol |
Definition at line 343 of file sepa_gauge.c.
References assert(), BOUNDARY, EXTERIOR, i, INTERIOR, LHS, NULL, RHS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMsg, SCIPgetNlRowSolActivity(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), and SCIPprintNlRow().
Referenced by findBoundaryPoint(), and separateCuts().
|
static |
returns, in convexcomb, the convex combination \( \lambda\, \text{endpoint} + (1 - \lambda) \text{startpoint} = \text{startpoint} + \lambda (\text{endpoint} - \text{startpoint})\)
scip | SCIP data structure |
lambda | convex combination multiplier |
startpoint | point corresponding to \( \lambda = 0 \) |
endpoint | point corresponding to \( \lambda = 1 \) |
convexcomb | solution to store convex combination of intsol and tosepasol |
Definition at line 420 of file sepa_gauge.c.
References assert(), i, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), SCIPsetSolVal(), var, and vars.
Referenced by findBoundaryPoint(), and separateCuts().
|
static |
performs binary search to find the point belonging to the segment [intsol
, tosepasol
] that intersects the boundary of the region described by the intersection of nlrows[i]
≤ rhs if convexsides[i] = RHS
or lhs ≤ nlrows[i]
if not, for i in nlrowsidx
scip | SCIP data structure |
nlrows | nlrows defining the region |
nlrowsidx | indices of nlrows defining the region |
nnlrowsidx | number of nlrows indices |
convexsides | sides of the nlrows involved in the region |
intsol | point acting as 'interior point' |
tosepasol | solution that should be separated |
sol | convex combination of intsol and lpsol |
position | buffer to store position of sol |
Definition at line 467 of file sepa_gauge.c.
References assert(), BOUNDARY, buildConvexCombination(), EXTERIOR, findPointPosition(), i, INTERIOR, MAX_ITER, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, and sol.
Referenced by separateCuts().
|
static |
computes gradient cut (linearization) of nlrow at sol
scip | SCIP data structure |
sol | point used to construct gradient cut (x_0) |
nlrow | constraint |
convexside | whether we use rhs or lhs of nlrow |
exprit | expression iterator that can be used |
row | storage for cut |
success | buffer to store whether the gradient was finite |
Definition at line 528 of file sepa_gauge.c.
References assert(), FALSE, i, LHS, NULL, RHS, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPdebug, SCIPdebugMsg, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexprGetEvalValue(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisFinite, SCIPisInfinity(), SCIPnlrowGetConstant(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), sol, TRUE, and var.
Referenced by separateCuts().
|
static |
tries to generate gradient cuts at the point on the segment [intsol
, tosepasol
] that intersecs the boundary of the convex relaxation
intsol
is not necessarily an interior point)scip | SCIP data structure |
sepa | the cut separator itself |
tosepasol | solution that should be separated |
result | pointer to store the result of the separation call |
Definition at line 636 of file sepa_gauge.c.
References assert(), BOUNDARY, buildConvexCombination(), EXTERIOR, FALSE, findBoundaryPoint(), findPointPosition(), generateCut(), i, INTERIOR, LHS, NULL, result, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPcreateEmptyRowSepa(), SCIPcreateExpriter(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPfeastol(), SCIPfreeExpriter(), SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNlRowSolActivity(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasEQ(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), SCIPprintSol(), SCIPreleaseRow(), SCIProwGetName(), SCIPsepaGetData(), SCIPsnprintf(), sepadata, sol, TRUE, and VIOLATIONFAC.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 800 of file sepa_gauge.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 820 of file sepa_gauge.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeSol(), SCIPsepaGetData(), and sepadata.
|
static |
LP solution separation method of separator
Definition at line 856 of file sepa_gauge.c.
References assert(), computeInteriorPoint(), i, LHS, NULL, result, RHS, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPcreateCurrentSol(), SCIPcreateNLPSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetNLPNlRows(), SCIPgetNlRowSolActivity(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPnlpGetSolstat(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPsepaGetData(), sepadata, separateCuts(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.