SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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.
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 } |
| #define SEPA_NAME "eccuts" |
Definition at line 35 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_DESC "separator for edge-concave functions" |
Definition at line 36 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_PRIORITY -13000 |
Definition at line 37 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_FREQ -1 |
Definition at line 38 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 39 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 40 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 41 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define CLIQUE_MAXFIRSTNODEWEIGHT 1000 |
maximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node)
Definition at line 43 of file sepa_eccuts.c.
Referenced by searchEcAggrWithCliques().
| #define CLIQUE_MINWEIGHT 0 |
lower bound for weight of generated cliques
Definition at line 46 of file sepa_eccuts.c.
Referenced by searchEcAggrWithCliques().
| #define CLIQUE_MAXNTREENODES 10000 |
maximal number of nodes of b&b tree
Definition at line 47 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 48 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 50 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXROUNDS 10 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 51 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXROUNDSROOT 250 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 52 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXDEPTH -1 |
maximal depth at which the separator is applied
Definition at line 53 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXSEPACUTS 10 |
maximal number of e.c. cuts separated per separation round
Definition at line 54 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXSEPACUTSROOT 50 |
maximal number of e.c. cuts separated per separation round in root node
Definition at line 55 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_CUTMAXRANGE 1e+7 |
maximal coefficient range of a cut (maximal coefficient divided by minimal coefficient) in order to be added to LP relaxation
Definition at line 56 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MINVIOLATION 0.3 |
minimal violation of an e.c. cut to be separated
Definition at line 59 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MINAGGRSIZE 3 |
search for e.c. aggregation of at least this size (has to be >= 3)
Definition at line 60 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXAGGRSIZE 4 |
search for e.c. aggregation of at most this size (has to be >= minaggrsize)
Definition at line 61 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXBILINTERMS 500 |
maximum number of bilinear terms allowed to be in a quadratic constraint
Definition at line 62 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define DEFAULT_MAXSTALLROUNDS 5 |
maximum number of unsuccessful rounds in the e.c. aggregation search
Definition at line 63 of file sepa_eccuts.c.
Referenced by SCIPincludeSepaEccuts().
| #define SUBSCIP_NODELIMIT 100LL |
node limit to solve the sub-SCIP
Definition at line 65 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 67 of file sepa_eccuts.c.
Referenced by checkRikun().
| #define USEDUALSIMPLEX TRUE |
use dual or primal simplex algorithm?
Definition at line 68 of file sepa_eccuts.c.
Referenced by SCIPcomputeConvexEnvelopeFacet().
| typedef struct EcAggr SCIP_ECAGGR |
Definition at line 92 of file sepa_eccuts.c.
| typedef struct NlrowAggr SCIP_NLROWAGGR |
Definition at line 122 of file sepa_eccuts.c.
|
static |
creates and 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 165 of file sepa_eccuts.c.
References ecaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPallocBlockMemoryArray.
Referenced by nlrowaggrCreate().
|
static |
frees and edge-concave aggregation
| scip | SCIP data structure |
| ecaggr | pointer to store the edge-concave aggregation |
Definition at line 195 of file sepa_eccuts.c.
References ecaggrAddQuadvar(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by ecaggrCreateEmpty(), and nlrowaggrFree().
|
static |
adds a quadratic variable to an edge-concave aggregation
| ecaggr | pointer to store the edge-concave aggregation |
| x | first variable |
Definition at line 216 of file sepa_eccuts.c.
References ecaggrAddBilinTerm(), EcAggr::nvars, SCIP_OKAY, and EcAggr::vars.
Referenced by ecaggrFree(), and 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 227 of file sepa_eccuts.c.
References nlrowaggrStoreLinearTerms(), EcAggr::nterms, NULL, EcAggr::nvars, SCIP_OKAY, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPisZero(), SCIPvarGetName(), EcAggr::termcoefs, EcAggr::termvars1, EcAggr::termvars2, and EcAggr::vars.
Referenced by ecaggrAddQuadvar(), and 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 301 of file sepa_eccuts.c.
References BMScopyMemoryArray, NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::nlinvars, nlrowaggrStoreQuadraticVars(), NULL, NlrowAggr::rhsaggr, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.
Referenced by ecaggrAddBilinTerm(), and nlrowaggrCreate().
|
static |
stores quadratic variables in a given nonlinear row aggregation
| scip | SCIP data structure |
| nlrowaggr | nonlinear row aggregation |
| quadvars | quadratic variables |
| nquadvars | number of quadratic variables |
Definition at line 341 of file sepa_eccuts.c.
References BMScopyMemoryArray, nlrowaggrAddRemBilinTerm(), NlrowAggr::nquadvars, NULL, NlrowAggr::quadvars, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.
Referenced by nlrowaggrCreate(), and nlrowaggrStoreLinearTerms().
|
static |
adds a remaining bilinear term to a given nonlinear row aggregation
| scip | SCIP data structure |
| nlrowaggr | nonlinear row aggregation |
| x | first variable |
| y | second variable |
| coef | bilinear coefficient |
Definition at line 362 of file sepa_eccuts.c.
References nlrowaggrCreate(), NlrowAggr::nremterms, NULL, NlrowAggr::remtermcoefs, NlrowAggr::remtermvars1, NlrowAggr::remtermvars2, and SCIP_OKAY.
Referenced by nlrowaggrCreate(), and nlrowaggrStoreQuadraticVars().
|
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 385 of file sepa_eccuts.c.
References BMScopyMemoryArray, SCIP_QuadElement::coef, ecaggrAddBilinTerm(), ecaggrAddQuadvar(), ecaggrCreateEmpty(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, nlrowaggrAddRemBilinTerm(), nlrowaggrFree(), nlrowaggrStoreLinearTerms(), nlrowaggrStoreQuadraticVars(), SCIP_NlRow::nquadvars, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisNegative(), SCIPnlrowGetConstant(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), and SCIPnlrowGetRhs().
Referenced by findAndStoreEcAggregations(), and nlrowaggrAddRemBilinTerm().
|
static |
frees a nonlinear row aggregation
| scip | SCIP data structure |
| nlrowaggr | pointer to free the nonlinear row aggregation |
Definition at line 546 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().
|
static |
creates separator data
| scip | SCIP data structure |
| sepadata | pointer to store separator data |
Definition at line 628 of file sepa_eccuts.c.
References BMSclearMemory, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and sepadataFreeNlrows().
Referenced by nlrowaggrFree(), and SCIPincludeSepaEccuts().
|
static |
frees all nonlinear row aggregations
| scip | SCIP data structure |
| sepadata | pointer to store separator data |
Definition at line 644 of file sepa_eccuts.c.
References nlrowaggrFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and sepadataFree().
Referenced by sepadataCreate(), and sepadataFree().
|
static |
frees separator data
| scip | SCIP data structure |
| sepadata | pointer to store separator data |
Definition at line 674 of file sepa_eccuts.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPlpiFree(), sepadataAddNlrowaggr(), and sepadataFreeNlrows().
Referenced by sepadataFreeNlrows().
|
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 700 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().
returns min{val-lb,ub-val} / (ub-lb)
| scip | SCIP data structure |
| val | solution value |
| lb | lower bound |
| ub | upper bound |
Definition at line 744 of file sepa_eccuts.c.
References createMIP(), MAX, MIN, and SCIPisFeasEQ().
Referenced by searchEcAggr(), and sepadataAddNlrowaggr().
|
static |
creates an MIP to search for cycles with an odd number of positive edges in the graph representation of a nonlinear row; the model uses directed binary arc flow variables; we introduce for all quadratic elements a forward and backward edge; if the term is quadratic (e.g., loop in the graph) we fix the corresponding variables to zero; this leads to an easy mapping of quadratic elements and the variables of the MIP
| scip | SCIP data structure |
| subscip | auxiliary SCIP to search aggregations |
| sepadata | separator data |
| nlrow | nonlinear row |
| rhsaggr | consider nonlinear row aggregation for g(x) <= rhs (TRUE) or lhs <= g(x) (FALSE) |
| forwardarcs | array to store all forward arc variables |
| backwardarcs | array to store all backward arc variables |
| nodeweights | weights for each node of the graph |
| nedges | pointer to store the number of nonexcluded edges in the graph |
Definition at line 767 of file sepa_eccuts.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, narcs, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsBasicLinear(), SCIPcreateConsBasicXor(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPincludeDefaultPlugins(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPreleaseCons(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetName(), TRUE, and updateMIP().
Referenced by phi(), and searchEcAggr().
|
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 924 of file sepa_eccuts.c.
References SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPfreeTransform(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), and storeAggrFromMIP().
Referenced by createMIP(), and searchEcAggr().
|
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 968 of file sepa_eccuts.c.
References SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_OKAY, SCIP_STATUS_INFEASIBLE, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetSolVal(), SCIPgetStatus(), SCIPisGT(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), and searchEcAggrWithMIP().
Referenced by searchEcAggr(), and updateMIP().
|
static |
searches for edge-concave aggregations with an 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 1014 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 searchEcAggr(), and storeAggrFromMIP().
|
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
| scip | SCIP data structure |
| nlrow | nonlinear row |
| graph | TCLIQUE graph structure |
| nodeweights | weights for each quadratic variable (nodes in the graph) |
Definition at line 1080 of file sepa_eccuts.c.
References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMsg, SCIPerrorMessage, SCIPisZero(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPvarGetIndex(), SCIPvarGetName(), searchEcAggrWithCliques(), tcliqueAddEdge(), tcliqueAddNode(), tcliqueCreate(), and tcliqueFlush().
Referenced by searchEcAggr(), and searchEcAggrWithMIP().
|
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 1165 of file sepa_eccuts.c.
References BMSclearMemoryArray, CLIQUE_BACKTRACKFREQ, CLIQUE_MAXFIRSTNODEWEIGHT, CLIQUE_MAXNTREENODES, CLIQUE_MINWEIGHT, SCIP_QuadElement::coef, FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPblkmem(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), searchEcAggr(), TCLIQUE_OPTIMAL, tcliqueChangeWeight(), tcliqueMaxClique(), and TRUE.
Referenced by createTcliqueGraph(), and 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 1295 of file sepa_eccuts.c.
References createMIP(), createTcliqueGraph(), isCandidate(), NULL, phi(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPisStopped(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadVars(), SCIPreleaseVar(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), searchEcAggrWithCliques(), searchEcAggrWithMIP(), storeAggrFromMIP(), tcliqueFree(), and updateMIP().
Referenced by findAndStoreEcAggregations(), and searchEcAggrWithCliques().
|
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 1481 of file sepa_eccuts.c.
References BMSclearMemoryArray, SCIP_QuadElement::coef, FALSE, findAndStoreEcAggregations(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPnlrowIsInNLP(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by findAndStoreEcAggregations(), and searchEcAggr().
|
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 1578 of file sepa_eccuts.c.
References checkRikun(), FALSE, isCandidate(), nlrowaggrCreate(), NULL, EcAggr::nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPgetMessagehdlr(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadVars(), SCIPnlrowGetRhs(), SCIPnlrowPrint(), SCIPvarGetName(), searchEcAggr(), sepadataAddNlrowaggr(), TRUE, and EcAggr::vars.
Referenced by isCandidate().
|
static |
checks if a facet is really an underestimate for all corners of the domain [l,u]; because of numerics it can happen that a facet violates a corner of the domain; to make the facet valid we subtract the maximum violation from the constant part of the facet; its a good excersise to write a comment describing the gray code...
| 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 1677 of file sepa_eccuts.c.
References ADJUSTFACETTOL, createLP(), FALSE, MAX, NULL, EcAggr::nvars, poweroftwo, SCIP_Real, SCIPdebugMsg, SCIPisFeasEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and EcAggr::vars.
Referenced by findAndStoreEcAggregations(), and SCIPcomputeConvexEnvelopeFacet().
|
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 1749 of file sepa_eccuts.c.
References evalCorner(), NULL, poweroftwo, SCIP_CALL, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMessagehdlr(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), and SCIPlpiFree().
Referenced by checkRikun(), and SCIPcomputeConvexEnvelopeFacet().
|
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 1861 of file sepa_eccuts.c.
References EcAggr::nterms, NULL, EcAggr::nvars, poweroftwo, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), EcAggr::termcoefs, EcAggr::termvars1, EcAggr::termvars2, transformValue(), and EcAggr::vars.
Referenced by createLP(), and SCIPcomputeConvexEnvelopeFacet().
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 1899 of file sepa_eccuts.c.
References MAX, MIN, NULL, REALABS, SCIPcomputeConvexEnvelopeFacet(), SCIPisFeasEQ(), and SCIPisInfinity().
Referenced by evalCorner(), and SCIPcomputeConvexEnvelopeFacet().
|
static |
computes a facet of the convex envelope of an edge concave aggregation
The algorithm solves the following LP:
\begin{eqnarray} min & \sum_i \lambda_i f(v_i)\\ s.t. & \sum_i \lambda_i v_i = x\\ & \sum_i \lambda_i = 1\\ & \lambda_i \geq 0 \end{eqnarray}
where f is an edge concave function, \(x\) in \([l,u]\) is a solution of the current relaxation, and \(v_i\) are the vertices of \([l,u]\); the method transforms the problem to the domain \([0,1]^n\), computes a facet, and transforms this facet to the original space; the dual solution of the LP above are the coefficients of the facet
The complete algorithm works as follows:
| 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 1944 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, and EcAggr::vars.
Referenced by computeCut(), and transformValue().
|
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 2152 of file sepa_eccuts.c.
References addLinearTermToCut(), FALSE, NULL, EcAggr::nvars, REALABS, SCIP_CALL, SCIP_OKAY, SCIPaddVarToRow(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by computeCut(), and SCIPcomputeConvexEnvelopeFacet().
|
static |
method to add an 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 2210 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().
|
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 2261 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().
|
static |
method to compute and and a cut for a nonlinear row aggregation and a given solution; we compute for each edge concave aggregation one facet; the remaining bilinear terms will be underestimated with McCormick, secants or linearizations; constant and linear terms will be added to the cut directly
| 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 2373 of file sepa_eccuts.c.
References addBilinearTermToCut(), addFacetToCut(), addLinearTermToCut(), NlrowAggr::constant, NlrowAggr::ecaggr, FALSE, isPossibleToComputeCut(), NlrowAggr::lincoefs, NlrowAggr::linvars, NlrowAggr::necaggr, NlrowAggr::nlinvars, NlrowAggr::nlrow, NlrowAggr::nremterms, NULL, EcAggr::nvars, NlrowAggr::remtermcoefs, NlrowAggr::remtermvars1, NlrowAggr::remtermvars2, NlrowAggr::rhs, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowRhs(), SCIPcomputeConvexEnvelopeFacet(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetDepth(), SCIPgetMessagehdlr(), SCIPgetNVars(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetRowSolActivity(), SCIPgetSolVal(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisGE(), SCIPisInfinity(), SCIPnlrowIsInNLP(), SCIPnlrowPrint(), SCIPprintRow(), SCIPreleaseRow(), SCIProwGetName(), SCIProwGetRank(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and EcAggr::vars.
Referenced by addBilinearTermToCut(), and 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 2547 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().
|
static |
searches and tries to add edge-concave cuts
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data |
| sol | current solution |
| result | pointer to store the result of the separation call |
Definition at line 2590 of file sepa_eccuts.c.
References computeCut(), isPossibleToComputeCut(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_SEPACOPY(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetDepth(), and SCIPisStopped().
Referenced by isPossibleToComputeCut().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 2665 of file sepa_eccuts.c.
Referenced by separateCuts().
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 2679 of file sepa_eccuts.c.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 2694 of file sepa_eccuts.c.
|
static |
LP solution separation method of separator
Definition at line 2721 of file sepa_eccuts.c.
|
static |
first values for 2^n
Definition at line 71 of file sepa_eccuts.c.
Referenced by checkRikun(), createLP(), evalCorner(), and SCIPcomputeConvexEnvelopeFacet().