Detailed Description

edge concave cut separator

Author: Benjamin Mueller

Definition in file sepa_eccuts.c.

#include <assert.h>
#include <string.h>
#include "scip/scipdefplugins.h"
#include "scip/sepa_eccuts.h"
#include "scip/cons_xor.h"
#include "scip/nlp.h"
#include "tclique/tclique.h"

Go to the source code of this file.

Data Structures
struct	EcAggr

struct	NlrowAggr

Macros
#define	SEPA_NAME "eccuts"

#define	SEPA_DESC "separator for edge-concave functions"

#define	SEPA_PRIORITY -13000

#define	SEPA_FREQ -1

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	CLIQUE_MAXFIRSTNODEWEIGHT 1000

#define	CLIQUE_MINWEIGHT 0

#define	CLIQUE_MAXNTREENODES 10000

#define	CLIQUE_BACKTRACKFREQ 10000

#define	DEFAULT_DYNAMICCUTS TRUE

#define	DEFAULT_MAXROUNDS 10

#define	DEFAULT_MAXROUNDSROOT 250

#define	DEFAULT_MAXDEPTH -1

#define	DEFAULT_MAXSEPACUTS 10

#define	DEFAULT_MAXSEPACUTSROOT 50

#define	DEFAULT_CUTMAXRANGE 1e+7

#define	DEFAULT_MINVIOLATION 0.3

#define	DEFAULT_MINAGGRSIZE 3

#define	DEFAULT_MAXAGGRSIZE 4

#define	DEFAULT_MAXBILINTERMS 500

#define	DEFAULT_MAXSTALLROUNDS 5

#define	SUBSCIP_NODELIMIT 100LL

#define	ADJUSTFACETTOL 1e-6

#define	USEDUALSIMPLEX TRUE

Typedefs
typedef struct EcAggr	SCIP_ECAGGR

typedef struct NlrowAggr	SCIP_NLROWAGGR

Functions
static SCIP_RETCODE	ecaggrCreateEmpty (SCIP scip, SCIP_ECAGGR *ecaggr, int nquadvars, int nquadterms)

static SCIP_RETCODE	ecaggrFree (SCIP scip, SCIP_ECAGGR *ecaggr)

static SCIP_RETCODE	ecaggrAddQuadvar (SCIP_ECAGGR ecaggr, SCIP_VAR x)

static SCIP_RETCODE	ecaggrAddBilinTerm (SCIP scip, SCIP_ECAGGR ecaggr, SCIP_VAR x, SCIP_VAR y, SCIP_Real coef)

static SCIP_RETCODE	nlrowaggrStoreLinearTerms (SCIP scip, SCIP_NLROWAGGR nlrowaggr, SCIP_VAR *linvars, SCIP_Real lincoefs, int nlinvars)

static SCIP_RETCODE	nlrowaggrAddLinearTerm (SCIP scip, SCIP_NLROWAGGR nlrowaggr, SCIP_VAR *linvar, SCIP_Real lincoef)

static SCIP_RETCODE	nlrowaggrAddQuadraticVar (SCIP scip, SCIP_NLROWAGGR nlrowaggr, SCIP_VAR *quadvar)

static SCIP_RETCODE	nlrowaggrAddRemBilinTerm (SCIP_NLROWAGGR nlrowaggr, SCIP_VAR x, SCIP_VAR *y, SCIP_Real coef)

static SCIP_RETCODE	nlrowaggrCreate (SCIP scip, SCIP_NLROW nlrow, SCIP_NLROWAGGR *nlrowaggr, int quadvar2aggr, int nfound, SCIP_Bool rhsaggr)

static SCIP_RETCODE	nlrowaggrFree (SCIP scip, SCIP_NLROWAGGR *nlrowaggr)

static SCIP_RETCODE	sepadataCreate (SCIP scip, SCIP_SEPADATA *sepadata)

static SCIP_RETCODE	sepadataFreeNlrows (SCIP scip, SCIP_SEPADATA sepadata)

static SCIP_RETCODE	sepadataFree (SCIP scip, SCIP_SEPADATA *sepadata)

static SCIP_RETCODE	sepadataAddNlrowaggr (SCIP scip, SCIP_SEPADATA sepadata, SCIP_NLROWAGGR *nlrowaggr)

static SCIP_Real	phi (SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)

static SCIP_RETCODE	createMIP (SCIP scip, SCIP subscip, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, SCIP_Bool rhsaggr, SCIP_VAR forwardarcs, SCIP_VAR backwardarcs, SCIP_Real nodeweights, int nedges, int *narcs)

static SCIP_RETCODE	updateMIP (SCIP subscip, SCIP_NLROW nlrow, SCIP_VAR forwardarcs, SCIP_VAR backwardarcs, int quadvar2aggr, int nedges)

static SCIP_RETCODE	storeAggrFromMIP (SCIP subscip, SCIP_NLROW nlrow, SCIP_VAR forwardarcs, SCIP_VAR backwardarcs, int *quadvar2aggr, int nfoundsofar)

static SCIP_RETCODE	searchEcAggrWithMIP (SCIP subscip, SCIP_Real timelimit, int nedges, SCIP_Bool aggrleft, SCIP_Bool *found)

static SCIP_RETCODE	createTcliqueGraph (SCIP_NLROW nlrow, TCLIQUE_GRAPH graph, SCIP_Real nodeweights)

static SCIP_RETCODE	searchEcAggrWithCliques (SCIP scip, TCLIQUE_GRAPH graph, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, int quadvar2aggr, int nfoundsofar, SCIP_Bool rhsaggr, SCIP_Bool foundaggr, SCIP_Bool *foundclique)

static SCIP_RETCODE	doSeachEcAggr (SCIP scip, SCIP subscip, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, SCIP_SOL sol, SCIP_Bool rhsaggr, int quadvar2aggr, int *nfound)

static SCIP_RETCODE	searchEcAggr (SCIP scip, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, SCIP_SOL sol, SCIP_Bool rhsaggr, int quadvar2aggr, int nfound)

static SCIP_RETCODE	isCandidate (SCIP scip, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, SCIP_Bool rhscandidate, SCIP_Bool *lhscandidate)

static SCIP_RETCODE	findAndStoreEcAggregations (SCIP scip, SCIP_SEPADATA sepadata, SCIP_NLROW nlrow, SCIP_SOL sol)

static SCIP_Bool	checkRikun (SCIP scip, SCIP_ECAGGR ecaggr, SCIP_Real fvals, SCIP_Real facet)

static SCIP_RETCODE	createLP (SCIP scip, SCIP_SEPADATA sepadata)

static SCIP_Real	evalCorner (SCIP_ECAGGR *ecaggr, int k)

static SCIP_Real	transformValue (SCIP *scip, SCIP_Real lb, SCIP_Real ub, SCIP_Real val)

static SCIP_RETCODE	computeConvexEnvelopeFacet (SCIP scip, SCIP_SEPADATA sepadata, SCIP_SOL sol, SCIP_ECAGGR ecaggr, SCIP_Real facet, SCIP_Real facetval, SCIP_Bool *success)

static SCIP_RETCODE	addFacetToCut (SCIP scip, SCIP_SOL sol, SCIP_ROW cut, SCIP_Real facet, SCIP_VAR *vars, int nvars, SCIP_Real cutconstant, SCIP_Real cutactivity, SCIP_Bool success)

static SCIP_RETCODE	addLinearTermToCut (SCIP scip, SCIP_SOL sol, SCIP_ROW cut, SCIP_VAR x, SCIP_Real coeff, SCIP_Real cutconstant, SCIP_Real cutactivity, SCIP_Bool *success)

static SCIP_RETCODE	addBilinearTermToCut (SCIP scip, SCIP_SOL sol, SCIP_ROW cut, SCIP_VAR x, SCIP_VAR y, SCIP_Real coeff, SCIP_Real cutconstant, SCIP_Real cutactivity, SCIP_Bool success)

static SCIP_RETCODE	computeCut (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, SCIP_NLROWAGGR nlrowaggr, SCIP_SOL sol, SCIP_Bool separated, SCIP_Bool *cutoff)

static SCIP_Bool	isPossibleToComputeCut (SCIP scip, SCIP_SOL sol, SCIP_NLROWAGGR *nlrowaggr)

static SCIP_RETCODE	separateCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, int depth, SCIP_SOL sol, SCIP_RESULT *result)

static	SCIP_DECL_SEPACOPY (sepaCopyEccuts)

static	SCIP_DECL_SEPAFREE (sepaFreeEccuts)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolEccuts)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpEccuts)

SCIP_RETCODE	SCIPincludeSepaEccuts (SCIP *scip)

Variables
static const int	poweroftwo [] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 }

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "eccuts"

Definition at line 45 of file sepa_eccuts.c.

◆ SEPA_DESC

#define SEPA_DESC "separator for edge-concave functions"

Definition at line 46 of file sepa_eccuts.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -13000

Definition at line 47 of file sepa_eccuts.c.

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 48 of file sepa_eccuts.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 49 of file sepa_eccuts.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 50 of file sepa_eccuts.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 51 of file sepa_eccuts.c.

◆ CLIQUE_MAXFIRSTNODEWEIGHT

#define CLIQUE_MAXFIRSTNODEWEIGHT 1000

maximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node)

Definition at line 54 of file sepa_eccuts.c.

◆ CLIQUE_MINWEIGHT

#define CLIQUE_MINWEIGHT 0

lower bound for weight of generated cliques

Definition at line 55 of file sepa_eccuts.c.

◆ CLIQUE_MAXNTREENODES

#define CLIQUE_MAXNTREENODES 10000

maximal number of nodes of b&b tree

Definition at line 56 of file sepa_eccuts.c.

◆ CLIQUE_BACKTRACKFREQ

#define CLIQUE_BACKTRACKFREQ 10000

frequency to backtrack to first level of tree (0: no premature backtracking)

Definition at line 57 of file sepa_eccuts.c.

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 59 of file sepa_eccuts.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 10

maximal number of separation rounds per node (-1: unlimited)

Definition at line 60 of file sepa_eccuts.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT 250

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 61 of file sepa_eccuts.c.

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH -1

maximal depth at which the separator is applied

Definition at line 62 of file sepa_eccuts.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 10

maximal number of e.c. cuts separated per separation round

Definition at line 63 of file sepa_eccuts.c.

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT 50

maximal number of e.c. cuts separated per separation round in root node

Definition at line 64 of file sepa_eccuts.c.

◆ DEFAULT_CUTMAXRANGE

#define DEFAULT_CUTMAXRANGE 1e+7

maximal coefficient range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation

Definition at line 66 of file sepa_eccuts.c.

◆ DEFAULT_MINVIOLATION

#define DEFAULT_MINVIOLATION 0.3

minimal violation of an e.c. cut to be separated

Definition at line 67 of file sepa_eccuts.c.

◆ DEFAULT_MINAGGRSIZE

#define DEFAULT_MINAGGRSIZE 3

search for e.c. aggregation of at least this size (has to be >= 3)

Definition at line 68 of file sepa_eccuts.c.

◆ DEFAULT_MAXAGGRSIZE

#define DEFAULT_MAXAGGRSIZE 4

search for e.c. aggregation of at most this size (has to be >= minaggrsize)

Definition at line 69 of file sepa_eccuts.c.

◆ DEFAULT_MAXBILINTERMS

#define DEFAULT_MAXBILINTERMS 500

maximum number of bilinear terms allowed to be in a quadratic constraint

Definition at line 70 of file sepa_eccuts.c.

◆ DEFAULT_MAXSTALLROUNDS

#define DEFAULT_MAXSTALLROUNDS 5

maximum number of unsuccessful rounds in the e.c. aggregation search

Definition at line 71 of file sepa_eccuts.c.

◆ SUBSCIP_NODELIMIT

#define SUBSCIP_NODELIMIT 100LL

node limit to solve the sub-SCIP

Definition at line 73 of file sepa_eccuts.c.

◆ ADJUSTFACETTOL

#define ADJUSTFACETTOL 1e-6

adjust resulting facets in checkRikun() up to a violation of this value

Definition at line 75 of file sepa_eccuts.c.

◆ USEDUALSIMPLEX

#define USEDUALSIMPLEX TRUE

use dual or primal simplex algorithm?

Definition at line 76 of file sepa_eccuts.c.

Typedef Documentation

◆ SCIP_ECAGGR

typedef struct EcAggr SCIP_ECAGGR

Definition at line 100 of file sepa_eccuts.c.

◆ SCIP_NLROWAGGR

typedef struct NlrowAggr SCIP_NLROWAGGR

Definition at line 132 of file sepa_eccuts.c.

Function Documentation

◆ ecaggrCreateEmpty()

static SCIP_RETCODE ecaggrCreateEmpty	(	SCIP *	scip,
		SCIP_ECAGGR **	ecaggr,
		int	nquadvars,
		int	nquadterms
	)

static

creates an empty edge-concave aggregation (without bilinear terms)

Parameters

scip	SCIP data structure
ecaggr	pointer to store the edge-concave aggregation
nquadvars	number of quadratic variables
nquadterms	number of bilinear terms

Definition at line 175 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPallocBlockMemoryArray.

Referenced by nlrowaggrCreate().

◆ ecaggrFree()

static SCIP_RETCODE ecaggrFree	(	SCIP *	scip,
		SCIP_ECAGGR **	ecaggr
	)

static

frees an edge-concave aggregation

Parameters

scip	SCIP data structure
ecaggr	pointer to store the edge-concave aggregation

Definition at line 205 of file sepa_eccuts.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by nlrowaggrFree().

◆ ecaggrAddQuadvar()

static SCIP_RETCODE ecaggrAddQuadvar	(	SCIP_ECAGGR *	ecaggr,
		SCIP_VAR *	x
	)

static

adds a quadratic variable to an edge-concave aggregation

Parameters

ecaggr	pointer to store the edge-concave aggregation
x	first variable

Definition at line 226 of file sepa_eccuts.c.

References EcAggr::nvars, SCIP_OKAY, EcAggr::vars, and x.

Referenced by nlrowaggrCreate().

◆ ecaggrAddBilinTerm()

static SCIP_RETCODE ecaggrAddBilinTerm	(	SCIP *	scip,
		SCIP_ECAGGR *	ecaggr,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_Real	coef
	)

static

adds a bilinear term to an edge-concave aggregation

Parameters

scip	SCIP data structure
ecaggr	pointer to store the edge-concave aggregation
x	first variable
y	second variable
coef	bilinear coefficient

Definition at line 237 of file sepa_eccuts.c.

References EcAggr::nterms, NULL, EcAggr::nvars, SCIP_OKAY, SCIPisZero(), EcAggr::termcoefs, EcAggr::termvars1, EcAggr::termvars2, EcAggr::vars, x, and y.

Referenced by nlrowaggrCreate().

◆ nlrowaggrStoreLinearTerms()

static SCIP_RETCODE nlrowaggrStoreLinearTerms	(	SCIP *	scip,
		SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_VAR **	linvars,
		SCIP_Real *	lincoefs,
		int	nlinvars
	)

static

stores linear terms in a given nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrowaggr	nonlinear row aggregation
linvars	linear variables
lincoefs	linear coefficients
nlinvars	number of linear variables

Definition at line 311 of file sepa_eccuts.c.

References NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::linvarssize, NlrowAggr::nlinvars, NULL, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, and SCIPduplicateBlockMemoryArray.

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddLinearTerm()

static SCIP_RETCODE nlrowaggrAddLinearTerm	(	SCIP *	scip,
		SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_VAR *	linvar,
		SCIP_Real	lincoef
	)

static

adds linear term to a given nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrowaggr	nonlinear row aggregation
linvar	linear variable
lincoef	coefficient

Definition at line 352 of file sepa_eccuts.c.

References NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::linvarssize, NlrowAggr::nlinvars, NULL, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddQuadraticVar()

static SCIP_RETCODE nlrowaggrAddQuadraticVar	(	SCIP *	scip,
		SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_VAR *	quadvar
	)

static

adds quadratic variable to a given nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrowaggr	nonlinear row aggregation
quadvar	quadratic variable

Definition at line 385 of file sepa_eccuts.c.

References NlrowAggr::nquadvars, NULL, NlrowAggr::quadvars, NlrowAggr::quadvarssize, SCIP_CALL, SCIP_OKAY, and SCIPensureBlockMemoryArray.

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddRemBilinTerm()

static SCIP_RETCODE nlrowaggrAddRemBilinTerm	(	SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_Real	coef
	)

static

adds a remaining bilinear term to a given nonlinear row aggregation

Parameters

nlrowaggr	nonlinear row aggregation
x	first variable
y	second variable
coef	bilinear coefficient

Definition at line 405 of file sepa_eccuts.c.

References NlrowAggr::nremterms, NULL, NlrowAggr::remtermcoefs, NlrowAggr::remtermvars1, NlrowAggr::remtermvars2, SCIP_OKAY, x, and y.

Referenced by nlrowaggrCreate().

◆ nlrowaggrCreate()

static SCIP_RETCODE nlrowaggrCreate	(	SCIP *	scip,
		SCIP_NLROW *	nlrow,
		SCIP_NLROWAGGR **	nlrowaggr,
		int *	quadvar2aggr,
		int	nfound,
		SCIP_Bool	rhsaggr
	)

static

creates a nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrow	nonlinear row
nlrowaggr	pointer to store the nonlinear row aggregation
quadvar2aggr	mapping between quadratic variables and edge-concave aggregation stores a negative value if the quadratic variables does not belong to any aggregation
nfound	number of edge-concave aggregations
rhsaggr	consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)

Definition at line 430 of file sepa_eccuts.c.

References ecaggrAddBilinTerm(), ecaggrAddQuadvar(), ecaggrCreateEmpty(), nlrowaggrAddLinearTerm(), nlrowaggrAddQuadraticVar(), nlrowaggrAddRemBilinTerm(), nlrowaggrStoreLinearTerms(), NULL, SCIP_NlRow::rhs, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocClearBufferArray, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisNegative(), SCIPnlrowGetConstant(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetRhs(), x, and y.

Referenced by findAndStoreEcAggregations().

◆ nlrowaggrFree()

static SCIP_RETCODE nlrowaggrFree	(	SCIP *	scip,
		SCIP_NLROWAGGR **	nlrowaggr
	)

static

frees a nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrowaggr	pointer to free the nonlinear row aggregation

Definition at line 652 of file sepa_eccuts.c.

References ecaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeBlockMemoryArrayNull.

Referenced by sepadataFreeNlrows().

◆ sepadataCreate()

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

static

creates separator data

Parameters

scip	SCIP data structure
sepadata	pointer to store separator data

Definition at line 728 of file sepa_eccuts.c.

References BMSclearMemory, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

Referenced by SCIPincludeSepaEccuts().

◆ sepadataFreeNlrows()

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

static

frees all nonlinear row aggregations

Parameters

scip	SCIP data structure
sepadata	pointer to store separator data

Definition at line 744 of file sepa_eccuts.c.

References nlrowaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_SEPAEXITSOL(), and sepadataFree().

◆ sepadataFree()

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

static

frees separator data

Parameters

scip	SCIP data structure
sepadata	pointer to store separator data

Definition at line 774 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPlpiFree(), and sepadataFreeNlrows().

Referenced by SCIP_DECL_SEPAFREE().

◆ sepadataAddNlrowaggr()

static SCIP_RETCODE sepadataAddNlrowaggr	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROWAGGR *	nlrowaggr
	)

static

adds a nonlinear row aggregation to the separator data

Parameters

scip	SCIP data structure
sepadata	separator data
nlrowaggr	non-linear row aggregation

Definition at line 800 of file sepa_eccuts.c.

References NlrowAggr::ecaggr, MAX, NlrowAggr::necaggr, NULL, EcAggr::nvars, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPreallocBlockMemoryArray.

Referenced by findAndStoreEcAggregations().

◆ phi()

static SCIP_Real phi	(	SCIP *	scip,
		SCIP_Real	val,
		SCIP_Real	lb,
		SCIP_Real	ub
	)

static

returns min{val-lb,ub-val} / (ub-lb)

Parameters

scip	SCIP data structure
val	solution value
lb	lower bound
ub	upper bound

Definition at line 844 of file sepa_eccuts.c.

References MAX, MIN, and SCIPisFeasEQ().

Referenced by doSeachEcAggr(), getTempObj(), permuteStartSolution(), and visualizeSolutionAscii().

◆ createMIP()

static SCIP_RETCODE createMIP	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		SCIP_Bool	rhsaggr,
		SCIP_VAR **	forwardarcs,
		SCIP_VAR **	backwardarcs,
		SCIP_Real *	nodeweights,
		int *	nedges,
		int *	narcs
	)

static

creates an MIP to search for cycles with an odd number of positive edges in the graph representation of a nonlinear row

The model uses directed binary arc flow variables. We introduce for all quadratic elements a forward and backward edge. If the term is quadratic (e.g., loop in the graph) we fix the corresponding variables to zero. This leads to an easy mapping between quadratic elements and the variables of the MIP.

Parameters

scip	SCIP data structure
subscip	auxiliary SCIP to search aggregations
sepadata	separator data
nlrow	nonlinear row
rhsaggr	consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)
forwardarcs	array to store all forward arc variables
backwardarcs	array to store all backward arc variables
nodeweights	weights for each node of the graph
nedges	pointer to store the number of nonexcluded edges in the graph
narcs	pointer to store the number of created arc variables (number of square and bilinear terms)

Definition at line 869 of file sepa_eccuts.c.

References narcs, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsBasicLinear(), SCIPcreateConsBasicXor(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetVarExprVar(), SCIPincludeDefaultPlugins(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPnlrowGetExpr(), SCIPreleaseCons(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetName(), and TRUE.

Referenced by doSeachEcAggr().

◆ updateMIP()

static SCIP_RETCODE updateMIP	(	SCIP *	subscip,
		SCIP_NLROW *	nlrow,
		SCIP_VAR **	forwardarcs,
		SCIP_VAR **	backwardarcs,
		int *	quadvar2aggr,
		int *	nedges
	)

static

fixed all arc variables (u,v) for which u or v is already in an edge-concave aggregation

Parameters

subscip	auxiliary SCIP to search aggregations
nlrow	nonlinear row
forwardarcs	forward arc variables
backwardarcs	backward arc variables
quadvar2aggr	mapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nedges	pointer to store the number of nonexcluded edges

Definition at line 1083 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarUb(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeTransform(), SCIPisZero(), and SCIPnlrowGetExpr().

Referenced by doSeachEcAggr().

◆ storeAggrFromMIP()

static SCIP_RETCODE storeAggrFromMIP	(	SCIP *	subscip,
		SCIP_NLROW *	nlrow,
		SCIP_VAR **	forwardarcs,
		SCIP_VAR **	backwardarcs,
		int *	quadvar2aggr,
		int	nfoundsofar
	)

static

stores the best edge-concave aggregation found by the MIP model

Parameters

subscip	auxiliary SCIP to search aggregations
nlrow	nonlinear row
forwardarcs	forward arc variables
backwardarcs	backward arc variables
quadvar2aggr	mapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nfoundsofar	number of e.c. aggregation found so far

Definition at line 1162 of file sepa_eccuts.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolVal(), SCIPgetStatus(), SCIPisGT(), SCIPisZero(), and SCIPnlrowGetExpr().

Referenced by doSeachEcAggr().

◆ searchEcAggrWithMIP()

static SCIP_RETCODE searchEcAggrWithMIP	(	SCIP *	subscip,
		SCIP_Real	timelimit,
		int	nedges,
		SCIP_Bool *	aggrleft,
		SCIP_Bool *	found
	)

static

searches for edge-concave aggregations with a MIP model based on binary flow variables

Parameters

subscip	SCIP data structure
timelimit	time limit to solve the MIP
nedges	number of nonexcluded undirected edges
aggrleft	pointer to store if there might be a left aggregation
found	pointer to store if we have found an aggregation

Definition at line 1246 of file sepa_eccuts.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_AGGRESSIVE, SCIP_STATUS_INFEASIBLE, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetStatus(), SCIPisLE(), SCIPprintSol(), SCIPsetHeuristics(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SUBSCIP_NODELIMIT, and TRUE.

Referenced by doSeachEcAggr().

◆ createTcliqueGraph()

static SCIP_RETCODE createTcliqueGraph	(	SCIP_NLROW *	nlrow,
		TCLIQUE_GRAPH **	graph,
		SCIP_Real *	nodeweights
	)

static

creates a tclique graph from a given nonlinear row

SCIP's clique code can only handle integer node weights; all node weights are scaled by a factor of 100; since the clique code ignores nodes with weight of zero, we add an offset of 100 to each weight

Parameters

nlrow	nonlinear row
graph	TCLIQUE graph structure
nodeweights	weights for each quadratic variable (nodes in the graph)

Definition at line 1312 of file sepa_eccuts.c.

References NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetVarExprVar(), SCIPnlrowGetExpr(), SCIPvarGetIndex(), SCIPvarGetName(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().

Referenced by doSeachEcAggr().

◆ searchEcAggrWithCliques()

static SCIP_RETCODE searchEcAggrWithCliques	(	SCIP *	scip,
		TCLIQUE_GRAPH *	graph,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		int *	quadvar2aggr,
		int	nfoundsofar,
		SCIP_Bool	rhsaggr,
		SCIP_Bool *	foundaggr,
		SCIP_Bool *	foundclique
	)

static

searches for edge-concave aggregations by computing cliques in the graph representation of a given nonlinear row

update graph, compute clique, store clique; after computing a clique we heuristically check if the clique contains at least one good cycle

Parameters

scip	SCIP data structure
graph	TCLIQUE graph structure
sepadata	separator data
nlrow	nonlinear row
quadvar2aggr	mapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nfoundsofar	number of e.c. aggregation found so far
rhsaggr	consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)
foundaggr	pointer to store if we have found an aggregation
foundclique	pointer to store if we have found a clique

Definition at line 1403 of file sepa_eccuts.c.

References BMSclearMemoryArray, CLIQUE_BACKTRACKFREQ, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MAXNTREENODES, CLIQUE_MINWEIGHT, FALSE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetExpr(), TCLIQUE_OPTIMAL, tcliqueChangeWeight(), tcliqueMaxClique(), and TRUE.

Referenced by doSeachEcAggr().

◆ doSeachEcAggr()

static SCIP_RETCODE doSeachEcAggr	(	SCIP *	scip,
		SCIP *	subscip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		SCIP_SOL *	sol,
		SCIP_Bool	rhsaggr,
		int *	quadvar2aggr,
		int *	nfound
	)

static

helper function for searchEcAggr()

Parameters

scip	SCIP data structure
subscip	sub-SCIP data structure
sepadata	separator data
nlrow	nonlinear row
sol	current solution (might be NULL)
rhsaggr	consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE)
quadvar2aggr	array to store for each quadratic variable in which edge-concave aggregation it is stored (< 0: in no aggregation); size has to be at least SCIPnlrowGetNQuadVars(nlrow)
nfound	pointer to store the number of found e.c. aggregations

Definition at line 1552 of file sepa_eccuts.c.

References createMIP(), createTcliqueGraph(), narcs, NULL, phi(), SCIP_Bool, SCIP_CALL, SCIP_CALL_FINALLY, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisInfinity(), SCIPisStopped(), SCIPnlrowGetExpr(), SCIPreleaseVar(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), searchEcAggrWithCliques(), searchEcAggrWithMIP(), storeAggrFromMIP(), tcliqueFree(), and updateMIP().

Referenced by searchEcAggr().

◆ searchEcAggr()

static SCIP_RETCODE searchEcAggr	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		SCIP_SOL *	sol,
		SCIP_Bool	rhsaggr,
		int *	quadvar2aggr,
		int *	nfound
	)

static

computes a partitioning into edge-concave aggregations for a given (quadratic) nonlinear row

Each aggregation has to contain a cycle with an odd number of positive weighted edges (good cycles) in the corresponding graph representation. For this we use the following algorithm:

use a MIP model based on binary flow variables to compute good cycles and store the implied subgraphs as an e.c. aggr.
1. if we find a good cycle, store the implied subgraph, delete it from the graph representation and go to 1)
2. if the MIP model is infeasible (there are no good cycles), STOP
we compute a large clique C if the MIP model fails (because of working limits, etc)
1. if we find a good cycle in C, store the implied subgraph of C, delete it from the graph representation and go to 1)
2. if C is not large enough, STOP

Parameters

scip	SCIP data structure
sepadata	separator data
nlrow	nonlinear row
sol	current solution (might be NULL)
rhsaggr	consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE)
quadvar2aggr	array to store for each quadratic variable in which edge-concave aggregation it is stored (< 0: in no aggregation); size has to be at least SCIPnlrowGetNQuadVars(nlrow)
nfound	pointer to store the number of found e.c. aggregations

Definition at line 1749 of file sepa_eccuts.c.

References doSeachEcAggr(), SCIP_CALL, SCIP_CALL_FINALLY, SCIP_OKAY, SCIPcreate(), and SCIPfree().

Referenced by findAndStoreEcAggregations().

◆ isCandidate()

static SCIP_RETCODE isCandidate	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		SCIP_Bool *	rhscandidate,
		SCIP_Bool *	lhscandidate
	)

static

returns whether a given nonlinear row can be used to compute edge-concave aggregations for which their convex envelope could dominate the termwise bilinear relaxation

This is the case if there exists at least one cycle with an odd number of positive edges in the corresponding graph representation of the nonlinear row.

Parameters

scip	SCIP data structure
sepadata	separator data
nlrow	nonlinear row representation of a nonlinear constraint
rhscandidate	pointer to store if we should compute edge-concave aggregations for the <= rhs case
lhscandidate	pointer to store if we should compute edge-concave aggregations for the >= lhs case

Definition at line 1782 of file sepa_eccuts.c.

References FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBufferArray, SCIPcheckExprQuadratic(), SCIPdebugMsg, SCIPexprAreQuadraticExprsVariables(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeBufferArray, SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprVar(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPnlrowIsInNLP(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by findAndStoreEcAggregations().

◆ findAndStoreEcAggregations()

static SCIP_RETCODE findAndStoreEcAggregations	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROW *	nlrow,
		SCIP_SOL *	sol
	)

static

finds and stores edge-concave aggregations for a given nonlinear row

Parameters

scip	SCIP data structure
sepadata	separator data
nlrow	nonlinear row
sol	current solution (might be NULL)

Definition at line 1913 of file sepa_eccuts.c.

References FALSE, isCandidate(), nlrowaggrCreate(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPisInfinity(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), searchEcAggr(), sepadataAddNlrowaggr(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ checkRikun()

static SCIP_Bool checkRikun	(	SCIP *	scip,
		SCIP_ECAGGR *	ecaggr,
		SCIP_Real *	fvals,
		SCIP_Real *	facet
	)

static

checks if a facet is really an underestimate for all corners of the domain [l,u]

Because of numerics it can happen that a facet violates a corner of the domain. To make the facet valid we subtract the maximum violation from the constant part of the facet.

Parameters

scip	SCIP data structure
ecaggr	edge-concave aggregation data
fvals	array containing all corner values of the aggregation
facet	current facet candidate (of dimension ecaggr->nvars + 1)

Definition at line 2018 of file sepa_eccuts.c.

References ADJUSTFACETTOL, FALSE, MAX, NULL, EcAggr::nvars, poweroftwo, SCIP_Real, SCIPdebugMsg, SCIPisFeasEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and EcAggr::vars.

Referenced by computeConvexEnvelopeFacet().

◆ createLP()

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

static

set up LP interface to solve LPs to compute the facet of the convex envelope

Parameters

scip	SCIP data structure
sepadata	separation data

Definition at line 2089 of file sepa_eccuts.c.

References a, NULL, poweroftwo, SCIP_CALL, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMessagehdlr(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), and SCIPlpiFree().

Referenced by computeConvexEnvelopeFacet().

◆ evalCorner()

static SCIP_Real evalCorner	(	SCIP_ECAGGR *	ecaggr,
		int	k
	)

static

evaluates an edge-concave aggregation at a corner of the domain [l,u]

Parameters

ecaggr	edge-concave aggregation data
k	k-th corner

Definition at line 2201 of file sepa_eccuts.c.

References EcAggr::nterms, NULL, EcAggr::nvars, poweroftwo, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), EcAggr::termcoefs, EcAggr::termvars1, EcAggr::termvars2, and EcAggr::vars.

Referenced by computeConvexEnvelopeFacet().

◆ transformValue()

static SCIP_Real transformValue	(	SCIP *	scip,
		SCIP_Real	lb,
		SCIP_Real	ub,
		SCIP_Real	val
	)

static

returns (val - lb) / (ub - lb) for a in [lb, ub]

Parameters

scip	SCIP data structure
lb	lower bound
ub	upper bound
val	value in [lb,ub]

Definition at line 2239 of file sepa_eccuts.c.

References MAX, MIN, NULL, REALABS, SCIPisFeasEQ(), and SCIPisInfinity().

Referenced by computeConvexEnvelopeFacet().

◆ computeConvexEnvelopeFacet()

static SCIP_RETCODE computeConvexEnvelopeFacet	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_SOL *	sol,
		SCIP_ECAGGR *	ecaggr,
		SCIP_Real *	facet,
		SCIP_Real *	facetval,
		SCIP_Bool *	success
	)

static

computes a facet of the convex envelope of an edge concave aggregation

The algorithm solves the following LP:

\begin{align} \min & \sum_i \lambda_i f(v_i)\\ s.t. & \sum_i \lambda_i v_i = x\\ & \sum_i \lambda_i = 1\\ & \lambda \geq 0 \end{align}

where \(f\) is an edge concave function, \(x\in [l,u]\) is a solution of the current relaxation, and \(v_i\) are the vertices of \([l,u]\). The method transforms the problem to the domain \([0,1]^n\), computes a facet, and transforms this facet to the original space. The dual solution of the LP above are the coefficients of the facet.

The complete algorithm works as follows:

compute \(f(v_i)\) for each corner \(v_i\) of \([l,u]\)
set up the described LP for the transformed space
solve the LP and store the resulting facet for the transformed space
transform the facet to original space
adjust and check facet with the algorithm of Rikun et al.

Parameters

scip	SCIP data structure
sepadata	separation data
sol	solution (might be NULL)
ecaggr	edge-concave aggregation data
facet	array to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1)
facetval	pointer to store the value of the facet evaluated at the current solution
success	pointer to store if we have found a facet

Definition at line 2283 of file sepa_eccuts.c.

References checkRikun(), createLP(), evalCorner(), FALSE, NULL, EcAggr::nvars, poweroftwo, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPlpiChgBounds(), SCIPlpiChgObj(), SCIPlpiChgSides(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiGetSol(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), transformValue(), TRUE, USEDUALSIMPLEX, EcAggr::vars, and x.

Referenced by computeCut().

◆ addFacetToCut()

static SCIP_RETCODE addFacetToCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_ROW *	cut,
		SCIP_Real *	facet,
		SCIP_VAR **	vars,
		int	nvars,
		SCIP_Real *	cutconstant,
		SCIP_Real *	cutactivity,
		SCIP_Bool *	success
	)

static

method to add a facet of the convex envelope of an edge-concave aggregation to a given cut

Parameters

scip	SCIP data structure
sol	current solution (might be NULL)
cut	current cut (modifiable)
facet	coefficient of the facet (dimension nvars + 1)
vars	variables of the facet
nvars	number of variables in the facet
cutconstant	pointer to update the constant part of the facet
cutactivity	pointer to update the activity of the cut
success	pointer to store if everything went fine

Definition at line 2491 of file sepa_eccuts.c.

References FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by computeCut().

◆ addLinearTermToCut()

static SCIP_RETCODE addLinearTermToCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_ROW *	cut,
		SCIP_VAR *	x,
		SCIP_Real	coeff,
		SCIP_Real *	cutconstant,
		SCIP_Real *	cutactivity,
		SCIP_Bool *	success
	)

static

method to add a linear term to a given cut

Parameters

scip	SCIP data structure
sol	current solution (might be NULL)
cut	current cut (modifiable)
x	linear variable
coeff	coefficient
cutconstant	pointer to update the constant part of the facet
cutactivity	pointer to update the activity of the cut
success	pointer to store if everything went fine

Definition at line 2549 of file sepa_eccuts.c.

References FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and x.

Referenced by computeCut().

◆ addBilinearTermToCut()

static SCIP_RETCODE addBilinearTermToCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_ROW *	cut,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_Real	coeff,
		SCIP_Real *	cutconstant,
		SCIP_Real *	cutactivity,
		SCIP_Bool *	success
	)

static

method to add an underestimate of a bilinear term to a given cut

Parameters

scip	SCIP data structure
sol	current solution (might be NULL)
cut	current cut (modifiable)
x	first bilinear variable
y	seconds bilinear variable
coeff	coefficient
cutconstant	pointer to update the constant part of the facet
cutactivity	pointer to update the activity of the cut
success	pointer to store if everything went fine

Definition at line 2600 of file sepa_eccuts.c.

References FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddBilinMcCormick(), SCIPaddSquareLinearization(), SCIPaddSquareSecant(), SCIPaddVarToRow(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, x, and y.

Referenced by computeCut().

◆ computeCut()

static SCIP_RETCODE computeCut	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_SOL *	sol,
		SCIP_Bool *	separated,
		SCIP_Bool *	cutoff
	)

static

method to compute and add a cut for a nonlinear row aggregation and a given solution

we compute for each edge concave aggregation one facet; the remaining bilinear terms will be underestimated with McCormick, secants or linearizations; constant and linear terms will be added to the cut directly

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
nlrowaggr	nonlinear row aggregation
sol	current solution (might be NULL)
separated	pointer to store if we could separate the current solution
cutoff	pointer to store if the current node gets cut off

Definition at line 2714 of file sepa_eccuts.c.

References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), computeConvexEnvelopeFacet(), NlrowAggr::constant, NlrowAggr::ecaggr, FALSE, NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::necaggr, NlrowAggr::nlinvars, NlrowAggr::nlrow, NlrowAggr::nremterms, NULL, EcAggr::nvars, NlrowAggr::remtermcoefs, NlrowAggr::remtermvars1, NlrowAggr::remtermvars2, NlrowAggr::rhs, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetDepth(), SCIPgetNVars(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowIsInNLP(), SCIPprintNlRow(), SCIPprintRow(), SCIPreleaseRow(), SCIProwGetName(), SCIProwGetRank(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, EcAggr::vars, x, and y.

Referenced by separateCuts().

◆ isPossibleToComputeCut()

static SCIP_Bool isPossibleToComputeCut	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_NLROWAGGR *	nlrowaggr
	)

static

returns whether it is possible to compute a cut for a given nonlinear row aggregation

Parameters

scip	SCIP data structure
sol	current solution (might be NULL)
nlrowaggr	nonlinear row aggregation

Definition at line 2889 of file sepa_eccuts.c.

References FALSE, NlrowAggr::nlrow, NlrowAggr::nquadvars, NULL, NlrowAggr::quadvar2aggr, NlrowAggr::quadvars, REALABS, SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPnlrowIsInNLP(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		int	depth,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

searches and tries to add edge-concave cuts

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
depth	current depth
sol	current solution
result	pointer to store the result of the separation call

Definition at line 2932 of file sepa_eccuts.c.

References computeCut(), isPossibleToComputeCut(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, and SCIPisStopped().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyEccuts )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 3008 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaEccuts(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeEccuts )

static

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

Definition at line 3022 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), SCIPsepaSetData(), and sepadataFree().

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolEccuts )

static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 3037 of file sepa_eccuts.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPsepaGetData(), SCIPstatisticMessage, and sepadataFreeNlrows().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpEccuts )

static

LP solution separation method of separator

Definition at line 3064 of file sepa_eccuts.c.

References findAndStoreEcAggregations(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetTotalTime(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPstatistic, separateCuts(), and TRUE.

Variable Documentation

◆ poweroftwo

const int poweroftwo[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 }

static

first values for \(2^n\)

Definition at line 79 of file sepa_eccuts.c.

Referenced by checkRikun(), computeConvexEnvelopeFacet(), createLP(), and evalCorner().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ CLIQUE_MAXFIRSTNODEWEIGHT

◆ CLIQUE_MINWEIGHT

◆ CLIQUE_MAXNTREENODES

◆ CLIQUE_BACKTRACKFREQ

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXDEPTH

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_CUTMAXRANGE

◆ DEFAULT_MINVIOLATION

◆ DEFAULT_MINAGGRSIZE

◆ DEFAULT_MAXAGGRSIZE

◆ DEFAULT_MAXBILINTERMS

◆ DEFAULT_MAXSTALLROUNDS

◆ SUBSCIP_NODELIMIT

◆ ADJUSTFACETTOL

◆ USEDUALSIMPLEX

Typedef Documentation

◆ SCIP_ECAGGR

◆ SCIP_NLROWAGGR

Function Documentation

◆ ecaggrCreateEmpty()

◆ ecaggrFree()

◆ ecaggrAddQuadvar()

◆ ecaggrAddBilinTerm()

◆ nlrowaggrStoreLinearTerms()

◆ nlrowaggrAddLinearTerm()

◆ nlrowaggrAddQuadraticVar()

◆ nlrowaggrAddRemBilinTerm()

◆ nlrowaggrCreate()

◆ nlrowaggrFree()

◆ sepadataCreate()

◆ sepadataFreeNlrows()

◆ sepadataFree()

◆ sepadataAddNlrowaggr()

◆ phi()

◆ createMIP()

◆ updateMIP()

◆ storeAggrFromMIP()

◆ searchEcAggrWithMIP()

◆ createTcliqueGraph()

◆ searchEcAggrWithCliques()

◆ doSeachEcAggr()

◆ searchEcAggr()

◆ isCandidate()

◆ findAndStoreEcAggregations()

◆ checkRikun()

◆ createLP()

◆ evalCorner()

◆ transformValue()

◆ computeConvexEnvelopeFacet()

◆ addFacetToCut()

◆ addLinearTermToCut()

◆ addBilinearTermToCut()

◆ computeCut()

◆ isPossibleToComputeCut()

◆ separateCuts()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()

Variable Documentation

◆ poweroftwo