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 |
Variables | |
static const int | poweroftwo [] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 } |
#define SEPA_NAME "eccuts" |
Definition at line 45 of file sepa_eccuts.c.
#define SEPA_DESC "separator for edge-concave functions" |
Definition at line 46 of file sepa_eccuts.c.
#define SEPA_PRIORITY -13000 |
Definition at line 47 of file sepa_eccuts.c.
#define SEPA_FREQ -1 |
Definition at line 48 of file sepa_eccuts.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 49 of file sepa_eccuts.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 50 of file sepa_eccuts.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 51 of file sepa_eccuts.c.
#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().
#define CLIQUE_MINWEIGHT 0 |
lower bound for weight of generated cliques
Definition at line 55 of file sepa_eccuts.c.
Referenced by searchEcAggrWithCliques().
#define CLIQUE_MAXNTREENODES 10000 |
maximal number of nodes of b&b tree
Definition at line 56 of file sepa_eccuts.c.
Referenced by searchEcAggrWithCliques().
#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().
#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.
#define DEFAULT_MAXROUNDS 10 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 60 of file sepa_eccuts.c.
#define DEFAULT_MAXROUNDSROOT 250 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 61 of file sepa_eccuts.c.
#define DEFAULT_MAXDEPTH -1 |
maximal depth at which the separator is applied
Definition at line 62 of file sepa_eccuts.c.
#define DEFAULT_MAXSEPACUTS 10 |
maximal number of e.c. cuts separated per separation round
Definition at line 63 of file sepa_eccuts.c.
#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.
#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().
#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().
#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().
#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().
#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().
#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().
#define SUBSCIP_NODELIMIT 100LL |
node limit to solve the sub-SCIP
Definition at line 73 of file sepa_eccuts.c.
Referenced by searchEcAggrWithMIP().
#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().
#define USEDUALSIMPLEX TRUE |
use dual or primal simplex algorithm?
Definition at line 76 of file sepa_eccuts.c.
Referenced by computeConvexEnvelopeFacet().
typedef struct EcAggr SCIP_ECAGGR |
Definition at line 100 of file sepa_eccuts.c.
typedef struct NlrowAggr SCIP_NLROWAGGR |
Definition at line 132 of file sepa_eccuts.c.
|
static |
creates an empty edge-concave aggregation (without bilinear terms)
scip | SCIP data structure |
ecaggr | pointer to store the edge-concave aggregation |
nquadvars | number of quadratic variables |
nquadterms | number of bilinear terms |
Definition at line 175 of file sepa_eccuts.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPallocBlockMemoryArray.
Referenced by nlrowaggrCreate().
|
static |
frees an edge-concave aggregation
scip | SCIP data structure |
ecaggr | pointer 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().
|
static |
adds a quadratic variable to an edge-concave aggregation
ecaggr | pointer to store the edge-concave aggregation |
x | first variable |
Definition at line 226 of file sepa_eccuts.c.
References EcAggr::nvars, SCIP_OKAY, EcAggr::vars, and x.
Referenced by nlrowaggrCreate().
|
static |
adds a bilinear term to an edge-concave aggregation
scip | SCIP data structure |
ecaggr | pointer to store the edge-concave aggregation |
x | first variable |
y | second variable |
coef | bilinear coefficient |
Definition at line 237 of file sepa_eccuts.c.
References 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().
|
static |
stores linear terms in a given nonlinear row aggregation
scip | SCIP data structure |
nlrowaggr | nonlinear row aggregation |
linvars | linear variables |
lincoefs | linear coefficients |
nlinvars | number of linear variables |
Definition at line 311 of file sepa_eccuts.c.
References assert(), i, NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::linvarssize, NlrowAggr::nlinvars, NULL, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPduplicateBlockMemoryArray.
Referenced by nlrowaggrCreate().
|
static |
adds linear term to a given nonlinear row aggregation
scip | SCIP data structure |
nlrowaggr | nonlinear row aggregation |
linvar | linear variable |
lincoef | coefficient |
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().
|
static |
adds quadratic variable to a given nonlinear row aggregation
scip | SCIP data structure |
nlrowaggr | nonlinear row aggregation |
quadvar | quadratic 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().
|
static |
adds a remaining bilinear term to a given nonlinear row aggregation
nlrowaggr | nonlinear row aggregation |
x | first variable |
y | second variable |
coef | bilinear 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().
|
static |
creates a nonlinear row aggregation
scip | SCIP data structure |
nlrow | nonlinear row |
nlrowaggr | pointer to store the nonlinear row aggregation |
quadvar2aggr | mapping between quadratic variables and edge-concave aggregation stores a negative value if the quadratic variables does not belong to any aggregation |
nfound | number of edge-concave aggregations |
rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE) |
Definition at line 430 of file sepa_eccuts.c.
References 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().
|
static |
frees a nonlinear row aggregation
scip | SCIP data structure |
nlrowaggr | pointer 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().
|
static |
creates separator data
scip | SCIP data structure |
sepadata | pointer 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().
|
static |
frees all nonlinear row aggregations
scip | SCIP data structure |
sepadata | pointer 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().
|
static |
frees separator data
scip | SCIP data structure |
sepadata | pointer 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().
|
static |
adds a nonlinear row aggregation to the separator data
scip | SCIP data structure |
sepadata | separator data |
nlrowaggr | non-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().
returns min{val-lb,ub-val} / (ub-lb)
scip | SCIP data structure |
val | solution value |
lb | lower bound |
ub | upper bound |
Definition at line 844 of file sepa_eccuts.c.
References MAX, MIN, SCIP_Real, and SCIPisFeasEQ().
Referenced by createProbSimplified(), doSeachEcAggr(), getTempObj(), permuteStartSolution(), and visualizeSolutionAscii().
|
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.
scip | SCIP data structure |
subscip | auxiliary SCIP to search aggregations |
sepadata | separator data |
nlrow | nonlinear row |
rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE) |
forwardarcs | array to store all forward arc variables |
backwardarcs | array to store all backward arc variables |
nodeweights | weights for each node of the graph |
nedges | pointer to store the number of nonexcluded edges in the graph |
narcs | pointer to store the number of created arc variables (number of square and bilinear terms) |
Definition at line 869 of file sepa_eccuts.c.
References 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().
|
static |
fixed all arc variables (u,v) for which u or v is already in an edge-concave aggregation
subscip | auxiliary SCIP to search aggregations |
nlrow | nonlinear row |
forwardarcs | forward arc variables |
backwardarcs | backward arc variables |
quadvar2aggr | mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) |
nedges | pointer to store the number of nonexcluded edges |
Definition at line 1083 of file sepa_eccuts.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarUb(), SCIPexprGetQuadraticBilinTerm(), SCIPexprGetQuadraticData(), SCIPexprGetQuadraticQuadTerm(), SCIPfreeTransform(), SCIPisZero(), and SCIPnlrowGetExpr().
Referenced by doSeachEcAggr().
|
static |
stores the best edge-concave aggregation found by the MIP model
subscip | auxiliary SCIP to search aggregations |
nlrow | nonlinear row |
forwardarcs | forward arc variables |
backwardarcs | backward arc variables |
quadvar2aggr | mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) |
nfoundsofar | number of e.c. aggregation found so far |
Definition at line 1162 of file sepa_eccuts.c.
References 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().
|
static |
searches for edge-concave aggregations with a MIP model based on binary flow variables
subscip | SCIP data structure |
timelimit | time limit to solve the MIP |
nedges | number of nonexcluded undirected edges |
aggrleft | pointer to store if there might be a left aggregation |
found | pointer to store if we have found an aggregation |
Definition at line 1246 of file sepa_eccuts.c.
References 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().
|
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
nlrow | nonlinear row |
graph | TCLIQUE graph structure |
nodeweights | weights for each quadratic variable (nodes in the graph) |
Definition at line 1312 of file sepa_eccuts.c.
References 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().
|
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
scip | SCIP data structure |
graph | TCLIQUE graph structure |
sepadata | separator data |
nlrow | nonlinear row |
quadvar2aggr | mapping of quadvars to e.c. aggr. index (< 0: in no aggr.) |
nfoundsofar | number of e.c. aggregation found so far |
rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE) |
foundaggr | pointer to store if we have found an aggregation |
foundclique | pointer to store if we have found a clique |
Definition at line 1403 of file sepa_eccuts.c.
References 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().
|
static |
helper function for searchEcAggr()
scip | SCIP data structure |
subscip | sub-SCIP data structure |
sepadata | separator data |
nlrow | nonlinear row |
sol | current solution (might be NULL) |
rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE) |
quadvar2aggr | array to store for each quadratic variable in which edge-concave aggregation it is stored (< 0: in no aggregation); size has to be at least SCIPnlrowGetNQuadVars(nlrow) |
nfound | pointer to store the number of found e.c. aggregations |
Definition at line 1552 of file sepa_eccuts.c.
References 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().
|
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:
scip | SCIP data structure |
sepadata | separator data |
nlrow | nonlinear row |
sol | current solution (might be NULL) |
rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or g(x) >= lhs (FALSE) |
quadvar2aggr | array to store for each quadratic variable in which edge-concave aggregation it is stored (< 0: in no aggregation); size has to be at least SCIPnlrowGetNQuadVars(nlrow) |
nfound | pointer to store the number of found e.c. aggregations |
Definition at line 1749 of file sepa_eccuts.c.
References doSeachEcAggr(), SCIP_Bool, SCIP_CALL, SCIP_CALL_FINALLY, SCIP_OKAY, SCIPcreate(), SCIPfree(), sepadata, and sol.
Referenced by findAndStoreEcAggregations().
|
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.
scip | SCIP data structure |
sepadata | separator data |
nlrow | nonlinear row representation of a nonlinear constraint |
rhscandidate | pointer to store if we should compute edge-concave aggregations for the <= rhs case |
lhscandidate | pointer to store if we should compute edge-concave aggregations for the >= lhs case |
Definition at line 1782 of file sepa_eccuts.c.
References 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().
|
static |
finds and stores edge-concave aggregations for a given nonlinear row
scip | SCIP data structure |
sepadata | separator data |
nlrow | nonlinear row |
sol | current solution (might be NULL) |
Definition at line 1913 of file sepa_eccuts.c.
References 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().
|
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.
scip | SCIP data structure |
ecaggr | edge-concave aggregation data |
fvals | array containing all corner values of the aggregation |
facet | current facet candidate (of dimension ecaggr->nvars + 1) |
Definition at line 2018 of file sepa_eccuts.c.
References ADJUSTFACETTOL, assert(), FALSE, i, MAX, NULL, EcAggr::nvars, poweroftwo, SCIP_Bool, SCIP_Real, SCIPdebugMsg, SCIPisFeasEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and EcAggr::vars.
Referenced by computeConvexEnvelopeFacet().
|
static |
set up LP interface to solve LPs to compute the facet of the convex envelope
scip | SCIP data structure |
sepadata | separation 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().
|
static |
evaluates an edge-concave aggregation at a corner of the domain [l,u]
ecaggr | edge-concave aggregation data |
k | k-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().
returns (val - lb) / (ub - lb) for a in [lb, ub]
scip | SCIP data structure |
lb | lower bound |
ub | upper bound |
val | value in [lb,ub] |
Definition at line 2239 of file sepa_eccuts.c.
References assert(), MAX, MIN, NULL, REALABS, SCIP_Real, SCIPisFeasEQ(), and SCIPisInfinity().
Referenced by 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:
scip | SCIP data structure |
sepadata | separation data |
sol | solution (might be NULL) |
ecaggr | edge-concave aggregation data |
facet | array to store the coefficients of the resulting facet; size has to be at least (ecaggr->nvars + 1) |
facetval | pointer to store the value of the facet evaluated at the current solution |
success | pointer to store if we have found a facet |
Definition at line 2283 of file sepa_eccuts.c.
References 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().
|
static |
method to add a facet of the convex envelope of an edge-concave aggregation to a given cut
scip | SCIP data structure |
sol | current solution (might be NULL) |
cut | current cut (modifiable) |
facet | coefficient of the facet (dimension nvars + 1) |
vars | variables of the facet |
nvars | number of variables in the facet |
cutconstant | pointer to update the constant part of the facet |
cutactivity | pointer to update the activity of the cut |
success | pointer to store if everything went fine |
Definition at line 2491 of file sepa_eccuts.c.
References 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().
|
static |
method to add a linear term to a given cut
scip | SCIP data structure |
sol | current solution (might be NULL) |
cut | current cut (modifiable) |
x | linear variable |
coeff | coefficient |
cutconstant | pointer to update the constant part of the facet |
cutactivity | pointer to update the activity of the cut |
success | pointer to store if everything went fine |
Definition at line 2549 of file sepa_eccuts.c.
References 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().
|
static |
method to add an underestimate of a bilinear term to a given cut
scip | SCIP data structure |
sol | current solution (might be NULL) |
cut | current cut (modifiable) |
x | first bilinear variable |
y | seconds bilinear variable |
coeff | coefficient |
cutconstant | pointer to update the constant part of the facet |
cutactivity | pointer to update the activity of the cut |
success | pointer to store if everything went fine |
Definition at line 2600 of file sepa_eccuts.c.
References 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().
|
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
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
nlrowaggr | nonlinear row aggregation |
sol | current solution (might be NULL) |
separated | pointer to store if we could separate the current solution |
cutoff | pointer to store if the current node gets cut off |
Definition at line 2714 of file sepa_eccuts.c.
References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), 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().
|
static |
returns whether it is possible to compute a cut for a given nonlinear row aggregation
scip | SCIP data structure |
sol | current solution (might be NULL) |
nlrowaggr | nonlinear 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().
|
static |
searches and tries to add edge-concave cuts
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
depth | current depth |
sol | current solution |
result | pointer to store the result of the separation call |
Definition at line 2932 of file sepa_eccuts.c.
References 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().
|
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.
|
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().
|
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().
|
static |
LP solution separation method of separator
Definition at line 3064 of file sepa_eccuts.c.
References assert(), depth, findAndStoreEcAggregations(), i, ncalls, NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIPdebugMsg, SCIPgetNLPNlRows(), SCIPgetNNLPNlRows(), SCIPgetTotalTime(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), SCIPstatistic, sepadata, separateCuts(), and TRUE.
|
static |
first values for \(2^n\)
Definition at line 79 of file sepa_eccuts.c.
Referenced by checkRikun(), computeConvexEnvelopeFacet(), createLP(), and evalCorner().