Detailed Description

gauge separator

Author: Felipe Serrano

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-1

#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 }

Functions
static SCIP_RETCODE	storeNonlinearConvexNlrows (SCIP scip, SCIP_SEPADATA sepadata, SCIP_NLROW **nlrows, int nnlrows)

static SCIP_RETCODE	computeInteriorPoint (SCIP scip, SCIP_SEPADATA sepadata)

static SCIP_RETCODE	findPointPosition (SCIP scip, SCIP_NLROW nlrows, int nlrowsidx, int nnlrowsidx, CONVEXSIDE convexsides, SCIP_SOL point, POSITION *position)

static SCIP_RETCODE	buildConvexCombination (SCIP scip, SCIP_Real lambda, SCIP_SOL startpoint, SCIP_SOL endpoint, SCIP_SOL convexcomb)

static SCIP_RETCODE	findBoundaryPoint (SCIP scip, SCIP_NLROW nlrows, int nlrowsidx, int nnlrowsidx, CONVEXSIDE convexsides, SCIP_SOL intsol, SCIP_SOL tosepasol, SCIP_SOL sol, POSITION *position)

static SCIP_RETCODE	generateCut (SCIP scip, SCIP_SOL sol, SCIP_NLROW nlrow, CONVEXSIDE convexside, SCIP_EXPRITER exprit, SCIP_ROW row, SCIP_Bool success)

static SCIP_RETCODE	separateCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SOL tosepasol, SCIP_RESULT result)

static	SCIP_DECL_SEPAFREE (sepaFreeGauge)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolGauge)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpGauge)

SCIP_RETCODE	SCIPincludeSepaGauge (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "gauge"

Definition at line 68 of file sepa_gauge.c.

Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGauge().

◆ SEPA_DESC

#define SEPA_DESC "gauge separator"

Definition at line 69 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 70 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 71 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 72 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 73 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 74 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ VIOLATIONFAC

#define VIOLATIONFAC 100

constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol

Definition at line 76 of file sepa_gauge.c.

Referenced by SCIP_DECL_SEPAEXECLP(), and separateCuts().

◆ MAX_ITER

#define MAX_ITER 75

maximum number of iterations for the line search

Definition at line 77 of file sepa_gauge.c.

Referenced by findBoundaryPoint().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM 1000

default NLP iteration limit

Definition at line 79 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ NLPFEASFAC

#define NLPFEASFAC 1e-1

NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance

Definition at line 81 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

◆ INTERIOROBJVARLB

#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().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 95 of file sepa_gauge.c.

◆ POSITION

typedef enum Position POSITION

Definition at line 104 of file sepa_gauge.c.

Enumeration Type Documentation

◆ ConvexSide

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 90 of file sepa_gauge.c.

◆ Position

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.

Function Documentation

◆ storeNonlinearConvexNlrows()

static SCIP_RETCODE storeNonlinearConvexNlrows	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW **	nlrows,
		int	nnlrows
	)

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 132 of file sepa_gauge.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().

◆ computeInteriorPoint()

static SCIP_RETCODE computeInteriorPoint	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

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

Note: the method also counts the number of nonlinear convex constraints and if there are < 2, then the convex relaxation is not interesting and the separator will not run again

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 192 of file sepa_gauge.c.

References FALSE, INTERIOROBJVARLB, MAX, SCIP_NlpStatistics::niterations, NLPFEASFAC, NULL, 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, SCIP_NlpStatistics::totaltime, and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ findPointPosition()

static SCIP_RETCODE findPointPosition	(	SCIP *	scip,
		SCIP_NLROW **	nlrows,
		int *	nlrowsidx,
		int	nnlrowsidx,
		CONVEXSIDE *	convexsides,
		SCIP_SOL *	point,
		POSITION *	position
	)

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

Note: point corresponds to a convex combination between the LP solution and the interior point

Parameters

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 BOUNDARY, EXTERIOR, 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().

◆ buildConvexCombination()

static SCIP_RETCODE buildConvexCombination	(	SCIP *	scip,
		SCIP_Real	lambda,
		SCIP_SOL *	startpoint,
		SCIP_SOL *	endpoint,
		SCIP_SOL *	convexcomb
	)

static

returns, in convexcomb, the convex combination \( \lambda\, \text{endpoint} + (1 - \lambda) \text{startpoint} = \text{startpoint} + \lambda (\text{endpoint} - \text{startpoint})\)

Parameters

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 NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), and SCIPsetSolVal().

Referenced by findBoundaryPoint(), and separateCuts().

◆ findBoundaryPoint()

static SCIP_RETCODE findBoundaryPoint	(	SCIP *	scip,
		SCIP_NLROW **	nlrows,
		int *	nlrowsidx,
		int	nnlrowsidx,
		CONVEXSIDE *	convexsides,
		SCIP_SOL *	intsol,
		SCIP_SOL *	tosepasol,
		SCIP_SOL *	sol,
		POSITION *	position
	)

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

Parameters

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 BOUNDARY, buildConvexCombination(), EXTERIOR, findPointPosition(), INTERIOR, MAX_ITER, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPdebugMsg.

Referenced by separateCuts().

◆ generateCut()

static SCIP_RETCODE generateCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_NLROW *	nlrow,
		CONVEXSIDE	convexside,
		SCIP_EXPRITER *	exprit,
		SCIP_ROW *	row,
		SCIP_Bool *	success
	)

static

computes gradient cut (linearization) of nlrow at sol

Parameters

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 FALSE, LHS, NULL, RHS, 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(), and TRUE.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	tosepasol,
		SCIP_RESULT *	result
	)

static

tries to generate gradient cuts at the point on the segment [intsol, tosepasol] that intersecs the boundary of the convex relaxation

checks that the relative interior of the segment actually intersects the boundary (this check is needed since intsol is not necessarily an interior point)
finds point on the boundary
generates gradient cut at point on the boundary

Parameters

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 BOUNDARY, buildConvexCombination(), EXTERIOR, FALSE, findBoundaryPoint(), findPointPosition(), generateCut(), INTERIOR, LHS, NULL, 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(), TRUE, and VIOLATIONFAC.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeGauge )

static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 800 of file sepa_gauge.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolGauge )

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 FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeSol(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpGauge )

static

LP solution separation method of separator

Definition at line 856 of file sepa_gauge.c.

References computeInteriorPoint(), LHS, NULL, 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(), separateCuts(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ VIOLATIONFAC

◆ MAX_ITER

◆ DEFAULT_NLPITERLIM

◆ NLPFEASFAC

◆ INTERIOROBJVARLB

Typedef Documentation

◆ CONVEXSIDE

◆ POSITION

Enumeration Type Documentation

◆ ConvexSide

◆ Position

Function Documentation

◆ storeNonlinearConvexNlrows()

◆ computeInteriorPoint()

◆ findPointPosition()

◆ buildConvexCombination()

◆ findBoundaryPoint()

◆ generateCut()

◆ separateCuts()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()