Scippy

SCIP

Solving Constraint Integer Programs

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.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_DESC

#define SEPA_DESC   "separator for edge-concave functions"

Definition at line 46 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -13000

Definition at line 47 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 48 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 49 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 50 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 51 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 53 of file sepa_eccuts.c.

Referenced by searchEcAggrWithCliques().

◆ CLIQUE_MINWEIGHT

#define CLIQUE_MINWEIGHT   0

lower bound for weight of generated cliques

Definition at line 56 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 57 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 58 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 60 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 61 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 62 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 63 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 64 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 65 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 66 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 69 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 70 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 71 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 72 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 73 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SUBSCIP_NODELIMIT

#define SUBSCIP_NODELIMIT   100LL

node limit to solve the sub-SCIP

Definition at line 75 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 77 of file sepa_eccuts.c.

Referenced by checkRikun().

◆ USEDUALSIMPLEX

#define USEDUALSIMPLEX   TRUE

use dual or primal simplex algorithm?

Definition at line 78 of file sepa_eccuts.c.

Referenced by computeConvexEnvelopeFacet().

Typedef Documentation

◆ SCIP_ECAGGR

typedef struct EcAggr SCIP_ECAGGR

Definition at line 102 of file sepa_eccuts.c.

◆ SCIP_NLROWAGGR

typedef struct NlrowAggr SCIP_NLROWAGGR

Definition at line 134 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
scipSCIP data structure
ecaggrpointer to store the edge-concave aggregation
nquadvarsnumber of quadratic variables
nquadtermsnumber of bilinear terms

Definition at line 177 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 an edge-concave aggregation

Parameters
scipSCIP data structure
ecaggrpointer to store the edge-concave aggregation

Definition at line 207 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
ecaggrpointer to store the edge-concave aggregation
xfirst variable

Definition at line 228 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
scipSCIP data structure
ecaggrpointer to store the edge-concave aggregation
xfirst variable
ysecond variable
coefbilinear coefficient

Definition at line 239 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
scipSCIP data structure
nlrowaggrnonlinear row aggregation
linvarslinear variables
lincoefslinear coefficients
nlinvarsnumber of linear variables

Definition at line 313 of file sepa_eccuts.c.

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

Referenced by ecaggrAddBilinTerm(), and 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
scipSCIP data structure
nlrowaggrnonlinear row aggregation
linvarlinear variable
lincoefcoefficient

Definition at line 354 of file sepa_eccuts.c.

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

Referenced by nlrowaggrCreate(), and nlrowaggrStoreLinearTerms().

◆ nlrowaggrAddQuadraticVar()

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

adds quadratic variable to a given nonlinear row aggregation

Parameters
scipSCIP data structure
nlrowaggrnonlinear row aggregation
quadvarquadratic variable

Definition at line 387 of file sepa_eccuts.c.

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

Referenced by nlrowaggrAddLinearTerm(), and 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
nlrowaggrnonlinear row aggregation
xfirst variable
ysecond variable
coefbilinear coefficient

Definition at line 407 of file sepa_eccuts.c.

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

Referenced by nlrowaggrAddQuadraticVar(), and 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
scipSCIP data structure
nlrownonlinear row
nlrowaggrpointer to store the nonlinear row aggregation
quadvar2aggrmapping between quadratic variables and edge-concave aggregation stores a negative value if the quadratic variables does not belong to any aggregation
nfoundnumber of edge-concave aggregations
rhsaggrconsider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)

Definition at line 432 of file sepa_eccuts.c.

References ecaggrAddBilinTerm(), ecaggrAddQuadvar(), ecaggrCreateEmpty(), nlrowaggrAddLinearTerm(), nlrowaggrAddQuadraticVar(), nlrowaggrAddRemBilinTerm(), nlrowaggrFree(), 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(), and nlrowaggrAddRemBilinTerm().

◆ nlrowaggrFree()

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

◆ sepadataCreate()

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

creates separator data

Parameters
scipSCIP data structure
sepadatapointer to store separator data

Definition at line 730 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
scipSCIP data structure
sepadatapointer to store separator data

Definition at line 746 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
scipSCIP data structure
sepadatapointer to store separator data

Definition at line 776 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
scipSCIP data structure
sepadataseparator data
nlrowaggrnon-linear row aggregation

Definition at line 802 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
scipSCIP data structure
valsolution value
lblower bound
ubupper bound

Definition at line 846 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,
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
scipSCIP data structure
subscipauxiliary SCIP to search aggregations
sepadataseparator data
nlrownonlinear row
rhsaggrconsider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)
forwardarcsarray to store all forward arc variables
backwardarcsarray to store all backward arc variables
nodeweightsweights for each node of the graph
nedgespointer to store the number of nonexcluded edges in the graph
narcspointer to store the number of created arc variables (number of square and bilinear terms)

Definition at line 871 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(), 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
subscipauxiliary SCIP to search aggregations
nlrownonlinear row
forwardarcsforward arc variables
backwardarcsbackward arc variables
quadvar2aggrmapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nedgespointer to store the number of nonexcluded edges

Definition at line 1085 of file sepa_eccuts.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarUb(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeTransform(), SCIPisZero(), SCIPnlrowGetExpr(), 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
subscipauxiliary SCIP to search aggregations
nlrownonlinear row
forwardarcsforward arc variables
backwardarcsbackward arc variables
quadvar2aggrmapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nfoundsofarnumber of e.c. aggregation found so far

Definition at line 1164 of file sepa_eccuts.c.

References NULL, SCIP_OKAY, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolVal(), SCIPgetStatus(), SCIPisGT(), SCIPisZero(), SCIPnlrowGetExpr(), 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 a MIP model based on binary flow variables

Parameters
subscipSCIP data structure
timelimittime limit to solve the MIP
nedgesnumber of nonexcluded undirected edges
aggrleftpointer to store if there might be a left aggregation
foundpointer to store if we have found an aggregation

Definition at line 1248 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_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
nlrownonlinear row
graphTCLIQUE graph structure
nodeweightsweights for each quadratic variable (nodes in the graph)

Definition at line 1314 of file sepa_eccuts.c.

References NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPgetVarExprVar(), SCIPnlrowGetExpr(), 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
scipSCIP data structure
graphTCLIQUE graph structure
sepadataseparator data
nlrownonlinear row
quadvar2aggrmapping of quadvars to e.c. aggr. index (< 0: in no aggr.)
nfoundsofarnumber of e.c. aggregation found so far
rhsaggrconsider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE)
foundaggrpointer to store if we have found an aggregation
foundcliquepointer to store if we have found a clique

Definition at line 1405 of file sepa_eccuts.c.

References BMSclearMemoryArray, CLIQUE_BACKTRACKFREQ, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MAXNTREENODES, CLIQUE_MINWEIGHT, doSeachEcAggr(), 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 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
scipSCIP data structure
subscipsub-SCIP data structure
sepadataseparator data
nlrownonlinear row
solcurrent solution (might be NULL)
rhsaggrconsider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE)
quadvar2aggrarray 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)
nfoundpointer to store the number of found e.c. aggregations

Definition at line 1554 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(), 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:

  1. 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
  2. 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
scipSCIP data structure
sepadataseparator data
nlrownonlinear row
solcurrent solution (might be NULL)
rhsaggrconsider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE)
quadvar2aggrarray 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)
nfoundpointer to store the number of found e.c. aggregations

Definition at line 1751 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
scipSCIP data structure
sepadataseparator data
nlrownonlinear row representation of a nonlinear constraint
rhscandidatepointer to store if we should compute edge-concave aggregations for the <= rhs case
lhscandidatepointer to store if we should compute edge-concave aggregations for the >= lhs case

Definition at line 1784 of file sepa_eccuts.c.

References FALSE, findAndStoreEcAggregations(), 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(), 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
scipSCIP data structure
sepadataseparator data
nlrownonlinear row
solcurrent solution (might be NULL)

Definition at line 1915 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, SCIPexprGetQuadraticData(), SCIPfreeBufferArray, SCIPisInfinity(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), 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.

Parameters
scipSCIP data structure
ecaggredge-concave aggregation data
fvalsarray containing all corner values of the aggregation
facetcurrent facet candidate (of dimension ecaggr->nvars + 1)

Definition at line 2020 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 computeConvexEnvelopeFacet(), and findAndStoreEcAggregations().

◆ 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
scipSCIP data structure
sepadataseparation data

Definition at line 2091 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 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
ecaggredge-concave aggregation data
kk-th corner

Definition at line 2203 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 computeConvexEnvelopeFacet(), and createLP().

◆ 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
scipSCIP data structure
lblower bound
ubupper bound
valvalue in [lb,ub]

Definition at line 2241 of file sepa_eccuts.c.

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

Referenced by computeConvexEnvelopeFacet(), and evalCorner().

◆ 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:

  1. compute \(f(v_i)\) for each corner \(v_i\) of \([l,u]\)
  2. set up the described LP for the transformed space
  3. solve the LP and store the resulting facet for the transformed space
  4. transform the facet to original space
  5. adjust and check facet with the algorithm of Rikun et al.
Parameters
scipSCIP data structure
sepadataseparation data
solsolution (might be NULL)
ecaggredge-concave aggregation data
facetarray to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1)
facetvalpointer to store the value of the facet evaluated at the current solution
successpointer to store if we have found a facet

Definition at line 2285 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
scipSCIP data structure
solcurrent solution (might be NULL)
cutcurrent cut (modifiable)
facetcoefficient of the facet (dimension nvars + 1)
varsvariables of the facet
nvarsnumber of variables in the facet
cutconstantpointer to update the constant part of the facet
cutactivitypointer to update the activity of the cut
successpointer to store if everything went fine

Definition at line 2493 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 computeConvexEnvelopeFacet(), and 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
scipSCIP data structure
solcurrent solution (might be NULL)
cutcurrent cut (modifiable)
xlinear variable
coeffcoefficient
cutconstantpointer to update the constant part of the facet
cutactivitypointer to update the activity of the cut
successpointer to store if everything went fine

Definition at line 2551 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
scipSCIP data structure
solcurrent solution (might be NULL)
cutcurrent cut (modifiable)
xfirst bilinear variable
yseconds bilinear variable
coeffcoefficient
cutconstantpointer to update the constant part of the facet
cutactivitypointer to update the activity of the cut
successpointer to store if everything went fine

Definition at line 2602 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 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
scipSCIP data structure
sepaseparator
sepadataseparator data
nlrowaggrnonlinear row aggregation
solcurrent solution (might be NULL)
separatedpointer to store if we could separate the current solution
cutoffpointer to store if the current node gets cut off

Definition at line 2716 of file sepa_eccuts.c.

References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), computeConvexEnvelopeFacet(), 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(), 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 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
scipSCIP data structure
solcurrent solution (might be NULL)
nlrowaggrnonlinear row aggregation

Definition at line 2891 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,
int  depth,
SCIP_SOL sol,
SCIP_RESULT result 
)
static

searches and tries to add edge-concave cuts

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
depthcurrent depth
solcurrent solution
resultpointer to store the result of the separation call

Definition at line 2934 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, 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 3010 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 3024 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 3039 of file sepa_eccuts.c.

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpEccuts  )
static

LP solution separation method of separator

Definition at line 3066 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 81 of file sepa_eccuts.c.

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