Detailed Description

gauge separator

Author: Felipe Serrano

Definition in file sepa_gauge.c.

#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "nlpi/nlpi_ipopt.h"
#include "nlpi/nlpioracle.h"
#include "nlpi/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/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_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/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 /* constraints regarded as violated when violation > VIOLATIONFACSCIPfeastol /

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

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	computeGradient (SCIP scip, SCIP_EXPRINT exprint, SCIP_SOL sol, SCIP_EXPRTREE exprtree, SCIP_Real *grad)

static SCIP_RETCODE	generateCut (SCIP scip, SCIP_SOL sol, SCIP_EXPRINT exprint, SCIP_NLROW nlrow, CONVEXSIDE convexside, 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 59 of file sepa_gauge.c.

Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGauge().

◆ SEPA_DESC

#define SEPA_DESC "gauge separator"

Definition at line 60 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 61 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 62 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 63 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 64 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 65 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ VIOLATIONFAC

#define VIOLATIONFAC 100 /* constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */

Definition at line 67 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 68 of file sepa_gauge.c.

Referenced by findBoundaryPoint().

◆ DEFAULT_NLPTIMELIMIT

#define DEFAULT_NLPTIMELIMIT 0.0

default time limit of NLP solver; 0.0 for no limit

Definition at line 70 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM 1000

default NLP iteration limit

Definition at line 71 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ NLPFEASFAC

#define NLPFEASFAC 1e-1

NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance

Definition at line 73 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

◆ NLPVERBOSITY

#define NLPVERBOSITY 0

NLP solver verbosity

Definition at line 74 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 76 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 87 of file sepa_gauge.c.

◆ POSITION

typedef enum Position POSITION

Definition at line 96 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 82 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 90 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 127 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(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), 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 186 of file sepa_gauge.c.

References FALSE, INTERIOROBJVARLB, MAX, NLPFEASFAC, NLPVERBOSITY, NULL, 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(), SCIPhashmapGetImageInt(), 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().

◆ 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 364 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 \) endpoint + (1 - \( lambda \)) startpoint = startpoint + \( \lambda \) (endpoint - tosepasol)

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 440 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 487 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().

◆ computeGradient()

static SCIP_RETCODE computeGradient	(	SCIP *	scip,
		SCIP_EXPRINT *	exprint,
		SCIP_SOL *	sol,
		SCIP_EXPRTREE *	exprtree,
		SCIP_Real *	grad
	)

static

computes gradient of exprtree at sol

Parameters

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 548 of file sepa_gauge.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 SCIP_RETCODE generateCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_EXPRINT *	exprint,
		SCIP_NLROW *	nlrow,
		CONVEXSIDE	convexside,
		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)
exprint	expression interpreter
nlrow	constraint
convexside	whether we use rhs or lhs of nlrow
row	storage for cut
success	buffer to store whether the gradient was finite

Definition at line 595 of file sepa_gauge.c.

References SCIP_QuadElement::coef, computeGradient(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, NULL, RHS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPdebug, SCIPdebugMsg, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetNlRowSolActivity(), SCIPgetSolVal(), SCIPisFinite, SCIPisInfinity(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), 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 727 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(), 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().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeGauge )

static

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

Definition at line 885 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 905 of file sepa_gauge.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintFree(), SCIPfreeBlockMemoryArray, SCIPfreeSol(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpGauge )

static

LP solution separation method of separator

Definition at line 942 of file sepa_gauge.c.

References computeInteriorPoint(), LHS, NULL, RHS, 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.

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_NLPTIMELIMIT

◆ DEFAULT_NLPITERLIM

◆ NLPFEASFAC

◆ NLPVERBOSITY

◆ INTERIOROBJVARLB

Typedef Documentation

◆ CONVEXSIDE

◆ POSITION

Enumeration Type Documentation

◆ ConvexSide

◆ Position

Function Documentation

◆ storeNonlinearConvexNlrows()

◆ computeInteriorPoint()

◆ findPointPosition()

◆ buildConvexCombination()

◆ findBoundaryPoint()

◆ computeGradient()

◆ generateCut()

◆ separateCuts()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()