Detailed Description
edge concave cut separator
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 |
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 |
creates an empty edge-concave aggregation (without bilinear terms)
- Parameters
-
scip SCIP data structure ecaggr pointer to store the edge-concave aggregation nquadvars number of quadratic variables nquadterms number of bilinear terms
Definition at line 177 of file sepa_eccuts.c.
References ecaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPallocBlockMemoryArray.
Referenced by nlrowaggrCreate().
◆ ecaggrFree()
|
static |
frees an edge-concave aggregation
- Parameters
-
scip SCIP data structure ecaggr pointer 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 |
adds a quadratic variable to an edge-concave aggregation
- Parameters
-
ecaggr pointer to store the edge-concave aggregation x first 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 |
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 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 |
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 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 |
adds linear term to a given nonlinear row aggregation
- Parameters
-
scip SCIP data structure nlrowaggr nonlinear row aggregation linvar linear variable lincoef coefficient
Definition at line 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 |
adds quadratic variable to a given nonlinear row aggregation
- Parameters
-
scip SCIP data structure nlrowaggr nonlinear row aggregation quadvar quadratic 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 |
adds a remaining bilinear term to a given nonlinear row aggregation
- Parameters
-
nlrowaggr nonlinear row aggregation x first variable y second variable coef bilinear coefficient
Definition at line 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 |
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 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 |
frees a nonlinear row aggregation
- Parameters
-
scip SCIP data structure nlrowaggr pointer to free the nonlinear row aggregation
Definition at line 654 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 |
creates separator data
- Parameters
-
scip SCIP data structure sepadata pointer 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 |
frees all nonlinear row aggregations
- Parameters
-
scip SCIP data structure sepadata pointer 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 |
frees separator data
- Parameters
-
scip SCIP data structure sepadata pointer 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 |
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 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()
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 846 of file sepa_eccuts.c.
References createMIP(), MAX, and SCIPisFeasEQ().
Referenced by doSeachEcAggr(), getTempObj(), permuteStartSolution(), sepadataAddNlrowaggr(), and visualizeSolutionAscii().
◆ createMIP()
|
static |
creates an MIP to search for cycles with an odd number of positive edges in the graph representation of a nonlinear row
The model uses directed binary arc flow variables. We introduce for all quadratic elements a forward and backward edge. If the term is quadratic (e.g., loop in the graph) we fix the corresponding variables to zero. This leads to an easy mapping between quadratic elements and the variables of the MIP.
- Parameters
-
scip SCIP data structure subscip auxiliary SCIP to search aggregations sepadata separator data nlrow nonlinear row rhsaggr consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE) forwardarcs array to store all forward arc variables backwardarcs array to store all backward arc variables nodeweights weights for each node of the graph nedges pointer to store the number of nonexcluded edges in the graph narcs pointer to store the number of created arc variables (number of square and bilinear terms)
Definition at line 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 |
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 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 |
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 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 |
searches for edge-concave aggregations with a MIP model based on binary flow variables
- Parameters
-
subscip SCIP data structure timelimit time limit to solve the MIP nedges number of nonexcluded undirected edges aggrleft pointer to store if there might be a left aggregation found pointer to store if we have found an aggregation
Definition at line 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 |
creates a tclique graph from a given nonlinear row
SCIP's clique code can only handle integer node weights; all node weights are scaled by a factor of 100; since the clique code ignores nodes with weight of zero, we add an offset of 100 to each weight
- Parameters
-
nlrow nonlinear row graph TCLIQUE graph structure nodeweights weights for each quadratic variable (nodes in the graph)
Definition at line 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 |
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 1405 of file sepa_eccuts.c.
References BMSclearMemoryArray, CLIQUE_BACKTRACKFREQ, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MAXNTREENODES, CLIQUE_MINWEIGHT, doSeachEcAggr(), FALSE, 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 |
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 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 |
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.
- if we find a good cycle, store the implied subgraph, delete it from the graph representation and go to 1)
- 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)
- if we find a good cycle in C, store the implied subgraph of C, delete it from the graph representation and go to 1)
- 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 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 |
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 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 |
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 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 |
checks if a facet is really an underestimate for all corners of the domain [l,u]
Because of numerics it can happen that a facet violates a corner of the domain. To make the facet valid we subtract the maximum violation from the constant part of the facet.
- Parameters
-
scip SCIP data structure ecaggr edge-concave aggregation data fvals array containing all corner values of the aggregation facet current facet candidate (of dimension ecaggr->nvars + 1)
Definition at line 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 |
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 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 |
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 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()
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 2241 of file sepa_eccuts.c.
References computeConvexEnvelopeFacet(), MAX, NULL, REALABS, SCIPisFeasEQ(), and SCIPisInfinity().
Referenced by computeConvexEnvelopeFacet(), and evalCorner().
◆ computeConvexEnvelopeFacet()
|
static |
computes a facet of the convex envelope of an edge concave aggregation
The algorithm solves the following LP:
\begin{align} \min & \sum_i \lambda_i f(v_i)\\ s.t. & \sum_i \lambda_i v_i = x\\ & \sum_i \lambda_i = 1\\ & \lambda \geq 0 \end{align}
where \(f\) is an edge concave function, \(x\in [l,u]\) is a solution of the current relaxation, and \(v_i\) are the vertices of \([l,u]\). The method transforms the problem to the domain \([0,1]^n\), computes a facet, and transforms this facet to the original space. The dual solution of the LP above are the coefficients of the facet.
The complete algorithm works as follows:
- compute \(f(v_i)\) for each corner \(v_i\) of \([l,u]\)
- set up the described LP for the transformed space
- solve the LP and store the resulting facet for the transformed space
- transform the facet to original space
- adjust and check facet with the algorithm of Rikun et al.
- Parameters
-
scip SCIP data structure sepadata separation data sol solution (might be NULL) ecaggr edge-concave aggregation data facet array to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1) facetval pointer to store the value of the facet evaluated at the current solution success pointer to store if we have found a facet
Definition at line 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 |
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 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 |
method to add a linear term to a given cut
- Parameters
-
scip SCIP data structure sol current solution (might be NULL) cut current cut (modifiable) x linear variable coeff coefficient cutconstant pointer to update the constant part of the facet cutactivity pointer to update the activity of the cut success pointer to store if everything went fine
Definition at line 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 |
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 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 |
method to compute and add a cut for a nonlinear row aggregation and a given solution
we compute for each edge concave aggregation one facet; the remaining bilinear terms will be underestimated with McCormick, secants or linearizations; constant and linear terms will be added to the cut directly
- Parameters
-
scip SCIP data structure sepa separator sepadata separator data nlrowaggr nonlinear row aggregation sol current solution (might be NULL) separated pointer to store if we could separate the current solution cutoff pointer to store if the current node gets cut off
Definition at line 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 |
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 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 |
searches and tries to add edge-concave cuts
- Parameters
-
scip SCIP data structure sepa separator sepadata separator data depth current depth sol current solution result pointer to store the result of the separation call
Definition at line 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 |
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 |
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 |
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 |
LP solution separation method of separator
Definition at line 3066 of file sepa_eccuts.c.
Variable Documentation
◆ poweroftwo
|
static |
first values for \(2^n\)
Definition at line 81 of file sepa_eccuts.c.
Referenced by checkRikun(), computeConvexEnvelopeFacet(), createLP(), and evalCorner().