SCIP Doxygen Documentation
Loading...
Searching...
No Matches

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

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 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 55 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 56 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 57 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 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 65 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 67 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 68 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 69 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 70 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 71 of file sepa_eccuts.c.

Referenced by SCIPincludeSepaEccuts().

◆ SUBSCIP_NODELIMIT

#define SUBSCIP_NODELIMIT   100LL

node limit to solve the sub-SCIP

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

Referenced by checkRikun().

◆ USEDUALSIMPLEX

#define USEDUALSIMPLEX   TRUE

use dual or primal simplex algorithm?

Definition at line 76 of file sepa_eccuts.c.

Referenced by computeConvexEnvelopeFacet().

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

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

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

Referenced by nlrowaggrCreate().

◆ ecaggrFree()

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

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

Referenced by nlrowaggrFree().

◆ ecaggrAddQuadvar()

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

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

Referenced by nlrowaggrCreate().

◆ ecaggrAddBilinTerm()

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

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

Referenced by nlrowaggrCreate().

◆ nlrowaggrStoreLinearTerms()

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

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

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddLinearTerm()

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

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

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddQuadraticVar()

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

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

Referenced by nlrowaggrCreate().

◆ nlrowaggrAddRemBilinTerm()

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

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

Referenced by nlrowaggrCreate().

◆ nlrowaggrCreate()

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

References assert(), ecaggrAddBilinTerm(), ecaggrAddQuadvar(), ecaggrCreateEmpty(), i, nlrowaggrAddLinearTerm(), nlrowaggrAddQuadraticVar(), nlrowaggrAddRemBilinTerm(), nlrowaggrStoreLinearTerms(), NULL, SCIP_Bool, 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()

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

frees a nonlinear row aggregation

Parameters
scipSCIP data structure
nlrowaggrpointer to free the nonlinear row aggregation

Definition at line 652 of file sepa_eccuts.c.

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

Referenced by sepadataFreeNlrows().

◆ sepadataCreate()

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

creates separator data

Parameters
scipSCIP data structure
sepadatapointer to store separator data

Definition at line 728 of file sepa_eccuts.c.

References assert(), BMSclearMemory, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and sepadata.

Referenced by SCIPincludeSepaEccuts().

◆ sepadataFreeNlrows()

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

References assert(), i, nlrowaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and sepadata.

Referenced by SCIP_DECL_SEPAEXITSOL(), and sepadataFree().

◆ sepadataFree()

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

frees separator data

Parameters
scipSCIP data structure
sepadatapointer to store separator data

Definition at line 774 of file sepa_eccuts.c.

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

Referenced by SCIP_DECL_SEPAFREE().

◆ sepadataAddNlrowaggr()

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

References assert(), NlrowAggr::ecaggr, i, MAX, NlrowAggr::necaggr, NULL, EcAggr::nvars, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPreallocBlockMemoryArray, and sepadata.

Referenced by findAndStoreEcAggregations().

◆ phi()

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

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

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

◆ createMIP()

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

References assert(), i, narcs, nnodes, NULL, SCIP_Bool, 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(), sepadata, and TRUE.

Referenced by doSeachEcAggr().

◆ updateMIP()

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

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

Referenced by doSeachEcAggr().

◆ storeAggrFromMIP()

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

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

Referenced by doSeachEcAggr().

◆ searchEcAggrWithMIP()

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

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

Referenced by doSeachEcAggr().

◆ createTcliqueGraph()

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

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

Referenced by doSeachEcAggr().

◆ searchEcAggrWithCliques()

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

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

Referenced by doSeachEcAggr().

◆ doSeachEcAggr()

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

References assert(), createMIP(), createTcliqueGraph(), i, 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(), sepadata, sol, storeAggrFromMIP(), tcliqueFree(), updateMIP(), and var.

Referenced by searchEcAggr().

◆ searchEcAggr()

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

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

Referenced by findAndStoreEcAggregations().

◆ isCandidate()

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

References assert(), FALSE, i, 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(), sepadata, and TRUE.

Referenced by findAndStoreEcAggregations().

◆ findAndStoreEcAggregations()

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

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

Referenced by SCIP_DECL_SEPAEXECLP().

◆ checkRikun()

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

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

Referenced by computeConvexEnvelopeFacet().

◆ createLP()

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

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

Referenced by computeConvexEnvelopeFacet().

◆ evalCorner()

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

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

Referenced by computeConvexEnvelopeFacet().

◆ transformValue()

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

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

Referenced by computeConvexEnvelopeFacet().

◆ computeConvexEnvelopeFacet()

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

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

Referenced by computeCut().

◆ addFacetToCut()

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

References assert(), FALSE, i, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, TRUE, and vars.

Referenced by computeCut().

◆ addLinearTermToCut()

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

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

Referenced by computeCut().

◆ addBilinearTermToCut()

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

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

Referenced by computeCut().

◆ computeCut()

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

References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), assert(), computeConvexEnvelopeFacet(), NlrowAggr::constant, cutoff, NlrowAggr::ecaggr, FALSE, i, 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(), sepadata, sol, TRUE, var, EcAggr::vars, x, and y.

Referenced by separateCuts().

◆ isPossibleToComputeCut()

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

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

Referenced by separateCuts().

◆ separateCuts()

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

References assert(), computeCut(), cutoff, depth, i, isPossibleToComputeCut(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPisStopped(), sepadata, and sol.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPACOPY()

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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaEccuts(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), SCIPsepaSetData(), sepadata, and sepadataFree().

◆ SCIP_DECL_SEPAEXITSOL()

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 assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPsepaGetData(), SCIPstatisticMessage, sepadata, and sepadataFreeNlrows().

◆ SCIP_DECL_SEPAEXECLP()

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