gauge separator
Definition in file sepa_gauge.c.
#include <assert.h>
#include <string.h>
#include "scip/sepa_gauge.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "nlpi/nlpioracle.h"
#include "nlpi/nlpi_ipopt.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 /* constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */ |
#define | MAX_ITER 75 /* maximum number of iterations for the line search */ |
#define | DEFAULT_NLPTIMELIMIT 0.0 |
#define | DEFAULT_NLPITERLIM 1000 |
#define | NLPFEASFAC 1e-1 |
#define | NLPVERBOSITY 0 |
#define | INTERIOROBJVARLB -100 |
Typedefs | |
typedef enum ConvexSide | CONVEXSIDE |
typedef enum Position | POSITION |
Enumerations | |
enum | ConvexSide { LHS = 0, RHS = 1, LHS = 0, RHS = 1 } |
enum | Position { INTERIOR = 0, BOUNDARY = 1, EXTERIOR = 2 } |
#define SEPA_NAME "gauge" |
Definition at line 37 of file sepa_gauge.c.
Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGauge().
#define SEPA_DESC "gauge separator" |
Definition at line 38 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define SEPA_PRIORITY 0 |
Definition at line 39 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define SEPA_FREQ -1 |
Definition at line 40 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 41 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 42 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 43 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define VIOLATIONFAC 100 /* constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */ |
Definition at line 45 of file sepa_gauge.c.
Referenced by SCIP_DECL_SEPAEXECLP(), and separateCuts().
#define MAX_ITER 75 /* maximum number of iterations for the line search */ |
Definition at line 46 of file sepa_gauge.c.
Referenced by findBoundaryPoint().
#define DEFAULT_NLPTIMELIMIT 0.0 |
default time limit of NLP solver; 0.0 for no limit
Definition at line 48 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define DEFAULT_NLPITERLIM 1000 |
default NLP iteration limit
Definition at line 49 of file sepa_gauge.c.
Referenced by SCIPincludeSepaGauge().
#define NLPFEASFAC 1e-1 |
NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance
Definition at line 51 of file sepa_gauge.c.
Referenced by computeInteriorPoint().
#define NLPVERBOSITY 0 |
NLP solver verbosity
Definition at line 52 of file sepa_gauge.c.
Referenced by computeInteriorPoint().
#define INTERIOROBJVARLB -100 |
lower bound of the objective variable when computing interior point
Definition at line 54 of file sepa_gauge.c.
Referenced by computeInteriorPoint().
typedef enum ConvexSide CONVEXSIDE |
Definition at line 65 of file sepa_gauge.c.
Definition at line 74 of file sepa_gauge.c.
enum ConvexSide |
side that makes a nlrow convex
Enumerator | |
---|---|
LHS | left hand side |
RHS | right hand side |
LHS | left hand side |
RHS | right hand side |
Definition at line 60 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 68 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 105 of file sepa_gauge.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 |
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 164 of file sepa_gauge.c.
References FALSE, INTERIOROBJVARLB, MAX, NLPFEASFAC, NLPVERBOSITY, SCIP_CALL, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProbRows(), SCIPblkmem(), SCIPcreateNlpiProb(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPfeastol(), SCIPgetCutoffbound(), SCIPgetLPRows(), SCIPgetMessagehdlr(), SCIPgetNlpiOracleIpopt(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPnlpiAddVars(), SCIPnlpiChgLinearCoefs(), SCIPnlpiCreateProblem(), SCIPnlpiFreeProblem(), SCIPnlpiGetName(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiGetStatistics(), SCIPnlpiOracleGetConstraintDegree(), SCIPnlpiOracleGetNConstraints(), SCIPnlpiOracleGetNVars(), SCIPnlpiOraclePrintProblem(), SCIPnlpiSetIntPar(), SCIPnlpiSetObjective(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlpStatisticsCreate(), SCIPnlpStatisticsFree(), SCIPnlpStatisticsGetNIterations(), SCIPnlpStatisticsGetTotalTime(), SCIPsetSolVal(), and TRUE.
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 342 of file sepa_gauge.c.
References BOUNDARY, EXTERIOR, INTERIOR, LHS, 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 \) endpoint + (1 - \( lambda \)) startpoint = startpoint + \( \lambda \) (endpoint - tosepasol)
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 418 of file sepa_gauge.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), and SCIPsetSolVal().
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 465 of file sepa_gauge.c.
References BOUNDARY, buildConvexCombination(), EXTERIOR, findPointPosition(), INTERIOR, MAX_ITER, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPdebugMsg.
Referenced by separateCuts().
|
static |
computes gradient of exprtree at sol
scip | SCIP data structure |
exprint | expressions interpreter |
sol | point where we compute gradient |
exprtree | exprtree for which we compute the gradient |
grad | buffer to store the gradient |
Definition at line 526 of file sepa_gauge.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 sol
scip | SCIP data structure |
sol | point used to construct gradient cut (x_0) |
exprint | expression interpreter |
nlrow | constraint |
convexside | whether we use rhs or lhs of nlrow |
row | storage for cut |
Definition at line 573 of file sepa_gauge.c.
References SCIP_QuadElement::coef, computeGradient(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, RHS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPdebug, SCIPdebugMsg, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetNlRowSolActivity(), SCIPgetSolVal(), SCIPisInfinity(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), and SCIPprintRow().
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
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 692 of file sepa_gauge.c.
References BOUNDARY, buildConvexCombination(), EXTERIOR, FALSE, findBoundaryPoint(), findPointPosition(), generateCut(), INTERIOR, LHS, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPcreateEmptyRowSepa(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPfeastol(), SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNlRowSolActivity(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasEQ(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), SCIPprintSol(), SCIPreleaseRow(), SCIProwGetName(), SCIPsepaGetData(), SCIPsnprintf(), TRUE, and VIOLATIONFAC.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 849 of file sepa_gauge.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 869 of file sepa_gauge.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPexprintFree(), SCIPfreeBlockMemoryArray, SCIPfreeSol(), and SCIPsepaGetData().
|
static |
LP solution separation method of separator
Definition at line 906 of file sepa_gauge.c.
References computeInteriorPoint(), FALSE, LHS, RHS, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPcreateCurrentSol(), SCIPcreateNLPSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPexprintCreate(), SCIPfeastol(), SCIPfreeSol(), SCIPgetBestSol(), SCIPgetNLPNlRows(), SCIPgetNlRowSolActivity(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNSols(), SCIPhasNLPSolution(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPsepaGetData(), separateCuts(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.