Detailed Description

edge concave cut separator

Author: Benjamin Müller

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	nlrowaggrStoreQuadraticVars (SCIP scip, SCIP_NLROWAGGR nlrowaggr, SCIP_VAR **quadvars, int nquadvars)

static SCIP_RETCODE	nlrowaggrAddRemBilinTerm (SCIP scip, 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)

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 scip, 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	SCIPcomputeConvexEnvelopeFacet (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, 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 35 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_DESC

#define SEPA_DESC "separator for edge-concave functions"

Definition at line 36 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -13000

Definition at line 37 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 38 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 39 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 40 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 41 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ 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 43 of file sepa_eccuts.c.

Referenced by searchEcAggrWithCliques().

◆ CLIQUE_MINWEIGHT

#define CLIQUE_MINWEIGHT 0

lower bound for weight of generated cliques

Definition at line 46 of file sepa_eccuts.c.

Referenced by searchEcAggrWithCliques().

◆ CLIQUE_MAXNTREENODES

#define CLIQUE_MAXNTREENODES 10000

maximal number of nodes of b&b tree

Definition at line 47 of file sepa_eccuts.c.

Referenced by searchEcAggrWithCliques().

◆ CLIQUE_BACKTRACKFREQ

#define CLIQUE_BACKTRACKFREQ 10000

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

Definition at line 48 of file sepa_eccuts.c.

Referenced by searchEcAggrWithCliques().

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS TRUE

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

Definition at line 50 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 10

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

Definition at line 51 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT 250

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

Definition at line 52 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH -1

maximal depth at which the separator is applied

Definition at line 53 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 10

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

Definition at line 54 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT 50

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

Definition at line 55 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ 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 56 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MINVIOLATION

#define DEFAULT_MINVIOLATION 0.3

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

Definition at line 59 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MINAGGRSIZE

#define DEFAULT_MINAGGRSIZE 3

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

Definition at line 60 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXAGGRSIZE

#define DEFAULT_MAXAGGRSIZE 4

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

Definition at line 61 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXBILINTERMS

#define DEFAULT_MAXBILINTERMS 500

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

Definition at line 62 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ DEFAULT_MAXSTALLROUNDS

#define DEFAULT_MAXSTALLROUNDS 5

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

Definition at line 63 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SUBSCIP_NODELIMIT

#define SUBSCIP_NODELIMIT 100LL

node limit to solve the sub-SCIP

Definition at line 65 of file sepa_eccuts.c.

Referenced by searchEcAggrWithMIP().

◆ ADJUSTFACETTOL

#define ADJUSTFACETTOL 1e-6

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

Definition at line 67 of file sepa_eccuts.c.

Referenced by checkRikun().

◆ USEDUALSIMPLEX

#define USEDUALSIMPLEX TRUE

use dual or primal simplex algorithm?

Definition at line 68 of file sepa_eccuts.c.

Referenced by SCIPcomputeConvexEnvelopeFacet().

Typedef Documentation

◆ SCIP_ECAGGR

typedef struct EcAggr SCIP_ECAGGR

Definition at line 92 of file sepa_eccuts.c.

◆ SCIP_NLROWAGGR

typedef struct NlrowAggr SCIP_NLROWAGGR

Definition at line 122 of file sepa_eccuts.c.

Function Documentation

◆ ecaggrCreateEmpty()

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

static

creates and 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 165 of file sepa_eccuts.c.

References ecaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPallocBlockMemoryArray.

Referenced by nlrowaggrCreate().

◆ ecaggrFree()

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

static

frees and edge-concave aggregation

Parameters

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

Definition at line 195 of file sepa_eccuts.c.

References ecaggrAddQuadvar(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by ecaggrCreateEmpty(), and 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 216 of file sepa_eccuts.c.

References ecaggrAddBilinTerm(), EcAggr::nvars, SCIP_OKAY, EcAggr::vars, and x.

Referenced by ecaggrFree(), and 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 227 of file sepa_eccuts.c.

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

Referenced by ecaggrAddQuadvar(), and 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 301 of file sepa_eccuts.c.

References BMScopyMemoryArray, NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::nlinvars, nlrowaggrStoreQuadraticVars(), NULL, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.

Referenced by ecaggrAddBilinTerm(), and nlrowaggrCreate().

◆ nlrowaggrStoreQuadraticVars()

static SCIP_RETCODE nlrowaggrStoreQuadraticVars	(	SCIP *	scip,
		SCIP_NLROWAGGR *	nlrowaggr,
		SCIP_VAR **	quadvars,
		int	nquadvars
	)

static

stores quadratic variables in a given nonlinear row aggregation

Parameters

scip	SCIP data structure
nlrowaggr	nonlinear row aggregation
quadvars	quadratic variables
nquadvars	number of quadratic variables

Definition at line 341 of file sepa_eccuts.c.

References BMScopyMemoryArray, nlrowaggrAddRemBilinTerm(), NlrowAggr::nquadvars, NULL, NlrowAggr::quadvars, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.

Referenced by nlrowaggrCreate(), and nlrowaggrStoreLinearTerms().

◆ nlrowaggrAddRemBilinTerm()

static SCIP_RETCODE nlrowaggrAddRemBilinTerm	(	SCIP *	scip,
		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

scip	SCIP data structure
nlrowaggr	nonlinear row aggregation
x	first variable
y	second variable
coef	bilinear coefficient

Definition at line 362 of file sepa_eccuts.c.

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

Referenced by nlrowaggrCreate(), and nlrowaggrStoreQuadraticVars().

◆ 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 388 of file sepa_eccuts.c.

References BMScopyMemoryArray, SCIP_QuadElement::coef, ecaggrAddBilinTerm(), ecaggrAddQuadvar(), ecaggrCreateEmpty(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, nlrowaggrAddRemBilinTerm(), nlrowaggrFree(), nlrowaggrStoreLinearTerms(), nlrowaggrStoreQuadraticVars(), SCIP_NlRow::nquadvars, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisNegative(), SCIPnlrowGetConstant(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), x, and y.

Referenced by findAndStoreEcAggregations(), and nlrowaggrAddRemBilinTerm().

◆ 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 549 of file sepa_eccuts.c.

References NlrowAggr::ecaggr, ecaggrFree(), NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::necaggr, NlrowAggr::nlinvars, NlrowAggr::nremterms, NULL, NlrowAggr::remtermcoefs, NlrowAggr::remtermvars1, NlrowAggr::remtermvars2, NlrowAggr::rhs, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPvarGetName(), and sepadataCreate().

Referenced by nlrowaggrCreate(), and 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 631 of file sepa_eccuts.c.

References BMSclearMemory, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and sepadataFreeNlrows().

Referenced by nlrowaggrFree(), and 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 647 of file sepa_eccuts.c.

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

Referenced by sepadataCreate(), 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 677 of file sepa_eccuts.c.

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

Referenced by sepadataFreeNlrows().

◆ 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 703 of file sepa_eccuts.c.

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

Referenced by findAndStoreEcAggregations(), and sepadataFree().

◆ 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 747 of file sepa_eccuts.c.

References createMIP(), MAX, MIN, and SCIPisFeasEQ().

Referenced by doSeachEcAggr(), getTempObj(), permuteStartSolution(), sepadataAddNlrowaggr(), 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
	)

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

Definition at line 770 of file sepa_eccuts.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, 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, SCIPfreeBufferArray, SCIPincludeDefaultPlugins(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPreleaseCons(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetName(), TRUE, and updateMIP().

Referenced by doSeachEcAggr(), and phi().

◆ 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 927 of file sepa_eccuts.c.

References SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPfreeTransform(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), and storeAggrFromMIP().

Referenced by createMIP(), and 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 971 of file sepa_eccuts.c.

References SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_OKAY, SCIP_STATUS_INFEASIBLE, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolVal(), SCIPgetStatus(), SCIPisGT(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), and searchEcAggrWithMIP().

Referenced by doSeachEcAggr(), and updateMIP().

◆ 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 an 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 1017 of file sepa_eccuts.c.

References createTcliqueGraph(), 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(), and storeAggrFromMIP().

◆ createTcliqueGraph()

static SCIP_RETCODE createTcliqueGraph	(	SCIP *	scip,
		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

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

Definition at line 1083 of file sepa_eccuts.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPisZero(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPvarGetIndex(), SCIPvarGetName(), searchEcAggrWithCliques(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().

Referenced by doSeachEcAggr(), and searchEcAggrWithMIP().

◆ 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 1168 of file sepa_eccuts.c.

References BMSclearMemoryArray, CLIQUE_BACKTRACKFREQ, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MAXNTREENODES, CLIQUE_MINWEIGHT, SCIP_QuadElement::coef, doSeachEcAggr(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), TCLIQUE_OPTIMAL, tcliqueChangeWeight(), tcliqueMaxClique(), and TRUE.

Referenced by createTcliqueGraph(), and 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 1287 of file sepa_eccuts.c.

References createMIP(), createTcliqueGraph(), NULL, phi(), SCIP_Bool, SCIP_CALL, SCIP_CALL_FINALLY, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPisStopped(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadVars(), SCIPreleaseVar(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), searchEcAggr(), searchEcAggrWithCliques(), searchEcAggrWithMIP(), storeAggrFromMIP(), tcliqueFree(), and updateMIP().

Referenced by searchEcAggr(), and searchEcAggrWithCliques().

◆ 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 1476 of file sepa_eccuts.c.

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

Referenced by doSeachEcAggr(), and 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 1507 of file sepa_eccuts.c.

References BMSclearMemoryArray, SCIP_QuadElement::coef, FALSE, findAndStoreEcAggregations(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPnlrowIsInNLP(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, x, and y.

Referenced by findAndStoreEcAggregations(), and searchEcAggr().

◆ 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 1604 of file sepa_eccuts.c.

References checkRikun(), FALSE, isCandidate(), nlrowaggrCreate(), NULL, EcAggr::nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPgetMessagehdlr(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetRhs(), SCIPnlrowPrint(), SCIPvarGetName(), searchEcAggr(), sepadataAddNlrowaggr(), TRUE, and EcAggr::vars.

Referenced by isCandidate().

◆ 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; its a good excersise to write a comment describing the gray code...

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 1703 of file sepa_eccuts.c.

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

Referenced by findAndStoreEcAggregations(), and SCIPcomputeConvexEnvelopeFacet().

◆ 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 1774 of file sepa_eccuts.c.

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

Referenced by checkRikun(), and SCIPcomputeConvexEnvelopeFacet().

◆ 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 1886 of file sepa_eccuts.c.

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

Referenced by createLP(), and SCIPcomputeConvexEnvelopeFacet().

◆ 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 1924 of file sepa_eccuts.c.

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

Referenced by evalCorner(), and SCIPcomputeConvexEnvelopeFacet().

◆ SCIPcomputeConvexEnvelopeFacet()

static SCIP_RETCODE SCIPcomputeConvexEnvelopeFacet	(	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{eqnarray} min & \sum_i \lambda_i f(v_i)\\ s.t. & \sum_i \lambda_i v_i = x\\ & \sum_i \lambda_i = 1\\ & \lambda_i \geq 0 \end{eqnarray}

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 1969 of file sepa_eccuts.c.

References addFacetToCut(), 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(), and transformValue().

◆ 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 2177 of file sepa_eccuts.c.

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

Referenced by computeCut(), and SCIPcomputeConvexEnvelopeFacet().

◆ 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 an 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 2235 of file sepa_eccuts.c.

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

Referenced by addFacetToCut(), and 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 2286 of file sepa_eccuts.c.

References computeCut(), 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(), and TRUE.

Referenced by addLinearTermToCut(), and 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 and 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 2398 of file sepa_eccuts.c.

References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), NlrowAggr::constant, NlrowAggr::ecaggr, FALSE, isPossibleToComputeCut(), 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(), SCIPcomputeConvexEnvelopeFacet(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetDepth(), SCIPgetMessagehdlr(), SCIPgetNVars(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowIsInNLP(), SCIPnlrowPrint(), SCIPprintRow(), SCIPreleaseRow(), SCIProwGetName(), SCIProwGetRank(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, EcAggr::vars, x, and y.

Referenced by addBilinearTermToCut(), and 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 2572 of file sepa_eccuts.c.

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

Referenced by computeCut(), and separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		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
sol	current solution
result	pointer to store the result of the separation call

Definition at line 2615 of file sepa_eccuts.c.

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

Referenced by isPossibleToComputeCut().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyEccuts )

static

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

Definition at line 2690 of file sepa_eccuts.c.

Referenced by separateCuts().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeEccuts )

static

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

Definition at line 2704 of file sepa_eccuts.c.

◆ 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 2719 of file sepa_eccuts.c.

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpEccuts )

static

LP solution separation method of separator

Definition at line 2746 of file sepa_eccuts.c.

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 71 of file sepa_eccuts.c.

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

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

◆ nlrowaggrStoreQuadraticVars()

◆ nlrowaggrAddRemBilinTerm()

◆ nlrowaggrCreate()

◆ nlrowaggrFree()

◆ sepadataCreate()

◆ sepadataFreeNlrows()

◆ sepadataFree()

◆ sepadataAddNlrowaggr()

◆ phi()

◆ createMIP()

◆ updateMIP()

◆ storeAggrFromMIP()

◆ searchEcAggrWithMIP()

◆ createTcliqueGraph()

◆ searchEcAggrWithCliques()

◆ doSeachEcAggr()

◆ searchEcAggr()

◆ isCandidate()

◆ findAndStoreEcAggregations()

◆ checkRikun()

◆ createLP()

◆ evalCorner()

◆ transformValue()

◆ SCIPcomputeConvexEnvelopeFacet()

◆ addFacetToCut()

◆ addLinearTermToCut()

◆ addBilinearTermToCut()

◆ computeCut()

◆ isPossibleToComputeCut()

◆ separateCuts()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()

Variable Documentation

◆ poweroftwo