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

Detailed Description

minor separator with intersection cuts

Author
Felipe Serrano
Antonia Chmiela

Let X be the matrix of auxiliary variables added for bilinear terms, X_{ij} = x_ix_j. The separator enforces quadratic constraints det(2x2 minor of X) = 0 via intersection cuts.

Definition in file sepa_interminor.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_interminor.h"
#include "scip/expr.h"
#include "scip/expr_var.h"
#include "scip/expr_pow.h"
#include "scip/expr_product.h"
#include "scip/nlpi_ipopt.h"
#include "scip/cons_nonlinear.h"

Go to the source code of this file.

Data Structures

struct  rowdata

Macros

#define SEPA_NAME   "interminor"
#define SEPA_DESC   "intersection cuts separator to ensure that 2x2 minors of X (= xx') have determinant 0"
#define SEPA_PRIORITY   0
#define SEPA_FREQ   -1
#define SEPA_MAXBOUNDDIST   1.0
#define SEPA_USESSUBSCIP   FALSE
#define SEPA_DELAY   FALSE
#define DEFAULT_MINCUTVIOL   1e-4
#define DEFAULT_RANDSEED   157
#define DEFAULT_MAXROUNDS   10
#define DEFAULT_MAXROUNDSROOT   -1
#define BINSEARCH_MAXITERS   120
#define DEFAULT_USESTRENGTHENING   FALSE
#define DEFAULT_USEBOUNDS   FALSE

Functions

static SCIP_RETCODE sepadataAddMinor (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_VAR *auxvarxik, SCIP_VAR *auxvarxil, SCIP_VAR *auxvarxjk, SCIP_VAR *auxvarxjl, SCIP_Bool isauxvarxikdiag, SCIP_Bool isauxvarxildiag, SCIP_Bool isauxvarxjkdiag, SCIP_Bool isauxvarxjldiag)
static SCIP_RETCODE sepadataClear (SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE getMinorVars (SCIP_SEPADATA *sepadata, int idx, SCIP_VAR **auxvarxik, SCIP_VAR **auxvarxil, SCIP_VAR **auxvarxjk, SCIP_VAR **auxvarxjl, SCIP_Bool *isauxvarxikdiag, SCIP_Bool *isauxvarxildiag, SCIP_Bool *isauxvarxjkdiag, SCIP_Bool *isauxvarxjldiag)
static SCIP_RETCODE insertIndex (SCIP *scip, SCIP_HASHMAP *rowmap, SCIP_VAR *row, SCIP_VAR *col, SCIP_VAR *auxvar, int *rowindices, int *nrows)
static SCIP_RETCODE detectMinors (SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE constructBasicVars2TableauRowMap (SCIP *scip, int *map)
static SCIP_RETCODE computeRestrictionToRay (SCIP *scip, SCIP_Real *ray, SCIP_VAR **vars, SCIP_Real *coefs, SCIP_Real *coefs4b, SCIP_Real *coefscondition, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_Real evalPhiAtRay (SCIP *scip, SCIP_Real t, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e)
static void doBinarySearch (SCIP *scip, SCIP_Real a, SCIP_Real b, SCIP_Real c, SCIP_Real d, SCIP_Real e, SCIP_Real *sol)
static SCIP_Real isCase4a (SCIP_Real tsol, SCIP_Real *coefs, SCIP_Real *coefscondition)
static SCIP_Real computeRoot (SCIP *scip, SCIP_Real *coefs)
static SCIP_Real computeIntersectionPoint (SCIP *scip, SCIP_Bool usebounds, SCIP_Real *coefs, SCIP_Real *coefs4b, SCIP_Real *coefscondition)
static SCIP_RETCODE addColToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_COL *col)
static SCIP_RETCODE addRowToCut (SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real cutcoef, SCIP_ROW *row, SCIP_Bool *success)
static SCIP_RETCODE getTableauRows (SCIP *scip, SCIP_VAR **vars, int *basicvarpos2tableaurow, SCIP_HASHMAP *tableau, SCIP_Real **tableaurows, SCIP_Bool *success)
static SCIP_RETCODE addCols (SCIP *scip, SCIP_VAR **vars, SCIP_Real **tableaurows, SCIP_ROWPREP *rowprep, SCIP_Real *rays, int *nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_RETCODE addRows (SCIP *scip, SCIP_VAR **vars, SCIP_Real **tableaurows, SCIP_ROWPREP *rowprep, SCIP_Real *rays, int *nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_Bool raysAreDependent (SCIP *scip, SCIP_Real *ray1, SCIP_Real *ray2, SCIP_Real *coef)
static SCIP_RETCODE findRho (SCIP *scip, SCIP_Real *rays, int nrays, int idx, SCIP_Real *interpoints, SCIP_VAR **vars, SCIP_Real *rho, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_RETCODE computeNegCutcoefs (SCIP *scip, SCIP_VAR **vars, SCIP_Real *rays, int nrays, int *rayslppos, SCIP_Real *interpoints, SCIP_ROWPREP *rowprep, SCIP_Bool usebounds, SCIP_Real *ad, SCIP_Bool *success)
static SCIP_RETCODE separateDeterminant (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_VAR *xik, SCIP_VAR *xil, SCIP_VAR *xjk, SCIP_VAR *xjl, SCIP_Bool *isxikdiag, SCIP_Bool *isxildiag, SCIP_Bool *isxjkdiag, SCIP_Bool *isxjldiag, int *basicvarpos2tableaurow, SCIP_HASHMAP *tableau, SCIP_RESULT *result)
static SCIP_RETCODE separatePoint (SCIP *scip, SCIP_SEPA *sepa, SCIP_RESULT *result)
static SCIP_DECL_SEPACOPY (sepaCopyMinor)
static SCIP_DECL_SEPAFREE (sepaFreeMinor)
static SCIP_DECL_SEPAINIT (sepaInitMinor)
static SCIP_DECL_SEPAEXIT (sepaExitMinor)
static SCIP_DECL_SEPAINITSOL (sepaInitsolMinor)
static SCIP_DECL_SEPAEXITSOL (sepaExitsolMinor)
static SCIP_DECL_SEPAEXECLP (sepaExeclpMinor)
SCIP_RETCODE SCIPincludeSepaInterminor (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "interminor"

Definition at line 50 of file sepa_interminor.c.

◆ SEPA_DESC

#define SEPA_DESC   "intersection cuts separator to ensure that 2x2 minors of X (= xx') have determinant 0"

Definition at line 51 of file sepa_interminor.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   0

Definition at line 52 of file sepa_interminor.c.

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 53 of file sepa_interminor.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 54 of file sepa_interminor.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 55 of file sepa_interminor.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 56 of file sepa_interminor.c.

◆ DEFAULT_MINCUTVIOL

#define DEFAULT_MINCUTVIOL   1e-4

default minimum required violation of a cut

Definition at line 58 of file sepa_interminor.c.

Referenced by SCIPincludeSepaInterminor(), and SCIPincludeSepaMinor().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   157

default random seed

Definition at line 59 of file sepa_interminor.c.

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS   10

maximal number of separation rounds per node (-1: unlimited)

Definition at line 60 of file sepa_interminor.c.

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT   -1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 61 of file sepa_interminor.c.

◆ BINSEARCH_MAXITERS

#define BINSEARCH_MAXITERS   120

default iteration limit for binary search

Definition at line 62 of file sepa_interminor.c.

◆ DEFAULT_USESTRENGTHENING

#define DEFAULT_USESTRENGTHENING   FALSE

default for using strengthend intersection cuts to separate

Definition at line 63 of file sepa_interminor.c.

Referenced by SCIPincludeSepaInterminor().

◆ DEFAULT_USEBOUNDS

#define DEFAULT_USEBOUNDS   FALSE

default for using nonnegativity bounds when separating

Definition at line 64 of file sepa_interminor.c.

Function Documentation

◆ sepadataAddMinor()

SCIP_RETCODE sepadataAddMinor ( SCIP * scip,
SCIP_SEPADATA * sepadata,
SCIP_VAR * auxvarxik,
SCIP_VAR * auxvarxil,
SCIP_VAR * auxvarxjk,
SCIP_VAR * auxvarxjl,
SCIP_Bool isauxvarxikdiag,
SCIP_Bool isauxvarxildiag,
SCIP_Bool isauxvarxjkdiag,
SCIP_Bool isauxvarxjldiag )
static

helper method to store a 2x2 minor in the separation data

Parameters
scipSCIP data structure
sepadataseparator data
auxvarxikauxiliary variable X_ik = x_i * x_k
auxvarxilauxiliary variable X_il = x_i * x_l
auxvarxjkauxiliary variable X_jk = x_j * x_k
auxvarxjlauxiliary variable X_jl = x_j * x_l
isauxvarxikdiagis X_ik diagonal? (i.e. i = k)
isauxvarxildiagis X_il diagonal? (i.e. i = l)
isauxvarxjkdiagis X_jk diagonal? (i.e. j = k)
isauxvarxjldiagis X_jl diagonal? (i.e. j = l)

Definition at line 102 of file sepa_interminor.c.

References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPdebugMsg, SCIPreallocBlockMemoryArray, SCIPvarGetName(), and sepadata.

Referenced by detectMinors().

◆ sepadataClear()

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

helper method to clear separation data

Parameters
scipSCIP data structure
sepadataseparator data

Definition at line 159 of file sepa_interminor.c.

References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPreleaseVar(), and sepadata.

Referenced by SCIP_DECL_SEPAEXITSOL().

◆ getMinorVars()

SCIP_RETCODE getMinorVars ( SCIP_SEPADATA * sepadata,
int idx,
SCIP_VAR ** auxvarxik,
SCIP_VAR ** auxvarxil,
SCIP_VAR ** auxvarxjk,
SCIP_VAR ** auxvarxjl,
SCIP_Bool * isauxvarxikdiag,
SCIP_Bool * isauxvarxildiag,
SCIP_Bool * isauxvarxjkdiag,
SCIP_Bool * isauxvarxjldiag )
static

helper method to get the variables associated to a minor

Parameters
sepadataseparator data
idxindex of the stored minor
auxvarxikauxiliary variable X_ik = x_i * x_k
auxvarxilauxiliary variable X_il = x_i * x_l
auxvarxjkauxiliary variable X_jk = x_j * x_k
auxvarxjlauxiliary variable X_jl = x_j * x_l
isauxvarxikdiagis X_ik diagonal? (i.e. i = k)
isauxvarxildiagis X_il diagonal? (i.e. i = l)
isauxvarxjkdiagis X_jk diagonal? (i.e. j = k)
isauxvarxjldiagis X_jl diagonal? (i.e. j = l)

Definition at line 190 of file sepa_interminor.c.

References assert(), NULL, SCIP_Bool, SCIP_OKAY, and sepadata.

Referenced by separatePoint().

◆ insertIndex()

SCIP_RETCODE insertIndex ( SCIP * scip,
SCIP_HASHMAP * rowmap,
SCIP_VAR * row,
SCIP_VAR * col,
SCIP_VAR * auxvar,
int * rowindices,
int * nrows )
static

adds a new entry (i.e., auxvar) of in (row, col) of matrix M.

we have a matrix, M, indexed by the variables M(xi, xk) is the auxiliary variable of xi * xk if it exists We store, for each row of the matrix, the indices of the nonzero column entries (assoc with the given row) and the auxiliary variable for xi * xk The nonzero column entries are stored as an array (struct rowdata) So we have a hashmap mapping each variable (row of the matrix) with its array representing the nonzero entries of the row.

Parameters
scipSCIP data structure
rowmaphashmap of the rows of the matrix
rowvariable corresponding to row of new entry
colvariable corresponding to column of new entry
auxvarauxvar to insert into the matrix
rowindicesarray of indices of all variables corresponding to a row
nrowsnumber of rows

Definition at line 231 of file sepa_interminor.c.

References assert(), rowdata::auxvars, rowdata::nvals, rowdata::rowidx, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreallocBufferArray, SCIPvarGetName(), SCIPvarGetProbindex(), rowdata::vals, and rowdata::valssize.

Referenced by detectMinors().

◆ detectMinors()

◆ constructBasicVars2TableauRowMap()

SCIP_RETCODE constructBasicVars2TableauRowMap ( SCIP * scip,
int * map )
static

constructs map between lp position of a basic variable and its row in the tableau

Parameters
scipSCIP data structure
mapbuffer to store the map

Definition at line 510 of file sepa_interminor.c.

References i, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetLPBasisInd(), and SCIPgetNLPRows().

Referenced by separatePoint().

◆ computeRestrictionToRay()

SCIP_RETCODE computeRestrictionToRay ( SCIP * scip,
SCIP_Real * ray,
SCIP_VAR ** vars,
SCIP_Real * coefs,
SCIP_Real * coefs4b,
SCIP_Real * coefscondition,
SCIP_Bool usebounds,
SCIP_Real * ad,
SCIP_Bool * success )
static

The restriction of the function representing the maximal S-free set to zlp + t * ray has the form sqrt(A t^2 + B t + C) - (D t + E). This function computes the coefficients A, B, C, D, E for the given ray.

Parameters
scipSCIP data structure
raycoefficients of ray
varsvariables
coefsbuffer to store A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4bbuffer to store A, B, C, D, and E of case 4b
coefsconditionbuffer to store coefs for checking whether we are in case 4a or 4b
useboundsTRUE if we want to separate non-negative bound
adcoefs a and d for the hyperplane aTx + dTy <= 0
successFALSE if we need to abort generation because of numerics

Definition at line 539 of file sepa_interminor.c.

References a, ABS, assert(), b, c, FALSE, i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPinfoMessage(), SCIPisHugeValue(), SCIPvarGetLPSol(), SQR, TRUE, and vars.

Referenced by addCols(), addRows(), and findRho().

◆ evalPhiAtRay()

SCIP_Real evalPhiAtRay ( SCIP * scip,
SCIP_Real t,
SCIP_Real a,
SCIP_Real b,
SCIP_Real c,
SCIP_Real d,
SCIP_Real e )
static

returns phi(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E)

Parameters
scipSCIP data structure
targument of phi restricted to ray
avalue of A
bvalue of B
cvalue of C
dvalue of D
evalue of E

Definition at line 700 of file sepa_interminor.c.

References a, assert(), b, c, QUAD, QUAD_ASSIGN, QUAD_SCALE, QUAD_TO_DBL, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSqrtQ, SCIPquadprecSquareD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

Referenced by computeRoot(), and doBinarySearch().

◆ doBinarySearch()

void doBinarySearch ( SCIP * scip,
SCIP_Real a,
SCIP_Real b,
SCIP_Real c,
SCIP_Real d,
SCIP_Real e,
SCIP_Real * sol )
static

helper function of computeRoot: we want phi to be <= 0

Parameters
scipSCIP data structure
avalue of A
bvalue of B
cvalue of C
dvalue of D
evalue of E
solbuffer to store solution; also gives initial point

Definition at line 757 of file sepa_interminor.c.

References a, b, BINSEARCH_MAXITERS, c, evalPhiAtRay(), i, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasZero(), and sol.

Referenced by computeRoot().

◆ isCase4a()

SCIP_Real isCase4a ( SCIP_Real tsol,
SCIP_Real * coefs,
SCIP_Real * coefscondition )
static

checks if we are in case 4a, i.e., if (num(xhat_{r+1}(zlp)) / E) * sqrt(A * tsol^2 + B * tsol + C) + w(ray) * tsol + num(yhat_{s+1}(zlp)) <= 0

Parameters
tsolt in the above formula
coefscoefficients A, B, C, D, and E of case 4a
coefsconditionextra coefficients needed for the evaluation of the condition: num(xhat_{r+1}(zlp)) / E; w(ray); num(yhat_{s+1}(zlp))

Definition at line 799 of file sepa_interminor.c.

References SCIP_Real, and SQR.

Referenced by computeIntersectionPoint().

◆ computeRoot()

SCIP_Real computeRoot ( SCIP * scip,
SCIP_Real * coefs )
static

finds smallest positive root phi by finding the smallest positive root of (A - D^2) t^2 + (B - 2 D*E) t + (C - E^2) = 0

However, we are conservative and want a solution such that phi is negative, but close to 0; thus we correct the result with a binary search

Parameters
scipSCIP data structure
coefsvalue of A

Definition at line 817 of file sepa_interminor.c.

References a, b, c, doBinarySearch(), evalPhiAtRay(), result, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), and sol.

Referenced by computeIntersectionPoint().

◆ computeIntersectionPoint()

SCIP_Real computeIntersectionPoint ( SCIP * scip,
SCIP_Bool usebounds,
SCIP_Real * coefs,
SCIP_Real * coefs4b,
SCIP_Real * coefscondition )
static

The maximal S-free set is gamma(z) <= 0; we find the intersection point of the ray ray starting from zlp with the boundary of the S-free set. That is, we find t >= 0 such that gamma(zlp + t * ray) = 0.

In cases 1,2, and 3, gamma is of the form gamma(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E)

In the case 4 gamma is of the form gamma(zlp + t * ray) = sqrt(A t^2 + B t + C) - (D t + E) if some condition holds sqrt(A' t^2 + B' t + C') - (D' t + E') otherwise

It can be shown (given the special properties of gamma) that the smallest positive root of each function of the form sqrt(a t^2 + b t + c) - (d t + e) is the same as the smallest positive root of the quadratic equation: (sqrt(a t^2 + b t + c) - (d t + e)) * (sqrt(a t^2 + b t + c) + (d t + e)) = 0 <==> (a - d^2) t^2 + (b - 2 d*e) t + (c - e^2) = 0

So, in cases 1, 2, and 3, this function just returns the solution of the above equation. In case 4, it first solves the equation assuming we are in the first piece. If there is no solution, then the second piece can't have a solution (first piece >= second piece for all t) Then we check if the solution satisfies the condition. If it doesn't then we solve the equation for the second piece. If it has a solution, then it has to be the solution.

Parameters
scipSCIP data structure
useboundswhether we are in case 4 or not
coefsvalues of A, B, C, D, and E of cases 1, 2, 3, or 4a
coefs4bvalues of A, B, C, D, and E of case 4b
coefsconditionvalues needed to evaluate condition of case 4

Definition at line 904 of file sepa_interminor.c.

References assert(), computeRoot(), isCase4a(), MAX, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), and sol.

Referenced by addCols(), addRows(), and findRho().

◆ addColToCut()

SCIP_RETCODE addColToCut ( SCIP * scip,
SCIP_ROWPREP * rowprep,
SCIP_Real cutcoef,
SCIP_COL * col )
static

adds cutcoef * (col - col*) to rowprep

Parameters
scipSCIP data structure
rowpreprowprep to store intersection cut
cutcoefcut coefficient
colcolumn to add to rowprep

Definition at line 953 of file sepa_interminor.c.

References assert(), NULL, SCIP_BASESTAT_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetBasisStatus(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPinfoMessage(), SCIProwprepAddConstant(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by addCols(), and computeNegCutcoefs().

◆ addRowToCut()

SCIP_RETCODE addRowToCut ( SCIP * scip,
SCIP_ROWPREP * rowprep,
SCIP_Real cutcoef,
SCIP_ROW * row,
SCIP_Bool * success )
static

adds cutcoef * (slack - slack*) to rowprep

row is lhs <= <coefs, vars> + constant <= rhs, thus slack is defined by slack + <coefs, vars> + constant = side If row (slack) is at upper, it means that <coefs,vars*> + constant = rhs, and so slack* = side - rhs --> slack - slack* = rhs - <coefs, vars> - constant. If row (slack) is at lower, then <coefs,vars*> + constant = lhs, and so slack* = side - lhs --> slack - slack* = lhs - <coefs, vars> - constant.

Parameters
scipSCIP data structure
rowpreprowprep to store intersection cut
cutcoefcut coefficient
rowrow, whose slack we are adding to rowprep
successbuffer to store whether the row is nonbasic enough

Definition at line 985 of file sepa_interminor.c.

References assert(), FALSE, i, NULL, SCIP_BASESTAT_LOWER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRowprepTerm(), SCIPcolGetVar(), SCIPgetRowActivity(), SCIPinfoMessage(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and SCIProwprepAddConstant().

Referenced by addRows(), and computeNegCutcoefs().

◆ getTableauRows()

SCIP_RETCODE getTableauRows ( SCIP * scip,
SCIP_VAR ** vars,
int * basicvarpos2tableaurow,
SCIP_HASHMAP * tableau,
SCIP_Real ** tableaurows,
SCIP_Bool * success )
static

get the tableau rows of the variables in vars

Parameters
scipSCIP data structure
varsvariables in the minor
basicvarpos2tableaurowmap between basic var and its tableau row
tableaumap between var an its tableau row
tableaurowsbuffer to store tableau row
successset to TRUE if no variable had basisstat = ZERO

Definition at line 1046 of file sepa_interminor.c.

References FALSE, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPvarGetCol(), TRUE, and vars.

Referenced by separateDeterminant().

◆ addCols()

SCIP_RETCODE addCols ( SCIP * scip,
SCIP_VAR ** vars,
SCIP_Real ** tableaurows,
SCIP_ROWPREP * rowprep,
SCIP_Real * rays,
int * nrays,
int * rayslppos,
SCIP_Real * interpoints,
SCIP_Bool usebounds,
SCIP_Real * ad,
SCIP_Bool * success )
static

computes the cut coefs of the non-basic (non-slack) variables (correspond to cols) and adds them to the intersection cut

Parameters
scipSCIP data structure
varsvariables
tableaurowstableau rows corresponding to the variables in vars
rowprepstore cut
raysbuffer to store rays
nrayspointer to store number of nonzero rays
rayslpposbuffer to store lppos of nonzero rays
interpointsbuffer to store intersection points or NULL if not needed
useboundsTRUE if we want to separate non-negative bound
adcoefs a and d for the hyperplane aTx + dTy <= 0
successpointer to store whether the generation of cutcoefs was successful

Definition at line 1110 of file sepa_interminor.c.

References addColToCut(), assert(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, i, NULL, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPgetLPCols(), SCIPgetNLPCols(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), TRUE, and vars.

Referenced by separateDeterminant().

◆ addRows()

SCIP_RETCODE addRows ( SCIP * scip,
SCIP_VAR ** vars,
SCIP_Real ** tableaurows,
SCIP_ROWPREP * rowprep,
SCIP_Real * rays,
int * nrays,
int * rayslppos,
SCIP_Real * interpoints,
SCIP_Bool usebounds,
SCIP_Real * ad,
SCIP_Bool * success )
static

computes the cut coefs of the non-basic slack variables (correspond to rows) and adds them to the intersection cut

Parameters
scipSCIP data structure
varsvariables
tableaurowstableau rows corresponding to the variables in vars
rowprepstore cut
raysbuffer to store rays
nrayspointer to store number of nonzero rays
rayslpposbuffer to store lppos of nonzero rays
interpointsbuffer to store intersection points or NULL if not needed
useboundsTRUE if we want to separate non-negative bound
adcoefs a and d for the hyperplane aTx + dTy <= 0
successpointer to store whether the generation of cutcoefs was successful

Definition at line 1216 of file sepa_interminor.c.

References addRowToCut(), assert(), computeIntersectionPoint(), computeRestrictionToRay(), FALSE, i, NULL, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisInfinity(), SCIPisZero(), SCIProwGetBasisStatus(), TRUE, and vars.

Referenced by separateDeterminant().

◆ raysAreDependent()

SCIP_Bool raysAreDependent ( SCIP * scip,
SCIP_Real * ray1,
SCIP_Real * ray2,
SCIP_Real * coef )
static
Parameters
scipSCIP data structure
ray1coefficients of ray 1
ray2coefficients of ray 2
coefpointer to store coef (s.t. r1 = coef * r2) in case rays are dependent

Definition at line 1326 of file sepa_interminor.c.

References FALSE, i, SCIP_Bool, SCIP_Real, SCIPisFeasEQ(), SCIPisZero(), and TRUE.

Referenced by findRho().

◆ findRho()

SCIP_RETCODE findRho ( SCIP * scip,
SCIP_Real * rays,
int nrays,
int idx,
SCIP_Real * interpoints,
SCIP_VAR ** vars,
SCIP_Real * rho,
SCIP_Bool usebounds,
SCIP_Real * ad,
SCIP_Bool * success )
static

finds the smallest negative steplength for the current ray r_idx such that the combination of r_idx with all rays not in the recession cone is in the recession cone

Parameters
scipSCIP data structure
raysrays
nraysnumber of nonzero rays
idxindex of current ray we want to find rho for
interpointsintersection points of nonzero rays
varsvariables
rhopointer to store the optimal rho
useboundsTRUE if we want to separate non-negative bound
adcoefs a and d for the hyperplane aTx + dTy <= 0
successTRUE if computation of rho was successful

Definition at line 1363 of file sepa_interminor.c.

References alpha, BINSEARCH_MAXITERS, computeIntersectionPoint(), computeRestrictionToRay(), i, raysAreDependent(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisZero(), TRUE, and vars.

Referenced by computeNegCutcoefs().

◆ computeNegCutcoefs()

SCIP_RETCODE computeNegCutcoefs ( SCIP * scip,
SCIP_VAR ** vars,
SCIP_Real * rays,
int nrays,
int * rayslppos,
SCIP_Real * interpoints,
SCIP_ROWPREP * rowprep,
SCIP_Bool usebounds,
SCIP_Real * ad,
SCIP_Bool * success )
static

computes negative steplengths for the rays that are in the recession cone of the S-free set, i.e., which have an infinite intersection point.

Parameters
scipSCIP data structure
varsvariables
raysrays
nraysnumber of nonzero rays
rayslpposlppos of nonzero rays
interpointsintersection points
rowpreprowprep for the generated cut
useboundsTRUE if we want to separate non-negative bound
adcoefs a and d for the hyperplane aTx + dTy <= 0
successif a cut candidate could be computed

Definition at line 1467 of file sepa_interminor.c.

References addColToCut(), addRowToCut(), assert(), findRho(), i, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetBasisStatus(), SCIPgetLPCols(), SCIPgetLPRows(), SCIPisInfinity(), SCIProwGetBasisStatus(), TRUE, and vars.

Referenced by separateDeterminant().

◆ separateDeterminant()

SCIP_RETCODE separateDeterminant ( SCIP * scip,
SCIP_SEPA * sepa,
SCIP_SEPADATA * sepadata,
SCIP_VAR * xik,
SCIP_VAR * xil,
SCIP_VAR * xjk,
SCIP_VAR * xjl,
SCIP_Bool * isxikdiag,
SCIP_Bool * isxildiag,
SCIP_Bool * isxjkdiag,
SCIP_Bool * isxjldiag,
int * basicvarpos2tableaurow,
SCIP_HASHMAP * tableau,
SCIP_RESULT * result )
static

separates cuts for stored principal minors

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
xikvariable X_ik = x_i * x_k
xilvariable X_il = x_i * x_l
xjkvariable X_jk = x_j * x_k
xjlvariable X_jl = x_j * x_l
isxikdiagis X_ik diagonal? (i.e. i = k)
isxildiagis X_il diagonal? (i.e. i = l)
isxjkdiagis X_jk diagonal? (i.e. j = k)
isxjldiagis X_jl diagonal? (i.e. j = l)
basicvarpos2tableaurowmap from basic var to its tableau row
tableaumap from var to its tableau row
resultpointer to store the result of the separation call

Definition at line 1538 of file sepa_interminor.c.

References addCols(), addRows(), assert(), computeNegCutcoefs(), FALSE, getTableauRows(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIPaddRow(), SCIPallocBufferArray, SCIPcleanupRowprep(), SCIPcreateRowprep(), SCIPfreeBuffer, SCIPfreeRowprep(), SCIPgetCutEfficacy(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetRowprepRowSepa(), SCIPisFeasNegative(), SCIPmergeRowprepTerms(), SCIPreleaseRow(), SCIProwprepAddSide(), SCIPvarGetLPSol(), sepadata, TRUE, and vars.

Referenced by separatePoint().

◆ separatePoint()

◆ SCIP_DECL_SEPACOPY()

SCIP_DECL_SEPACOPY ( sepaCopyMinor )
static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 1795 of file sepa_interminor.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaInterminor(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

SCIP_DECL_SEPAFREE ( sepaFreeMinor )
static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 1810 of file sepa_interminor.c.

References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaSetData(), and sepadata.

◆ SCIP_DECL_SEPAINIT()

SCIP_DECL_SEPAINIT ( sepaInitMinor )
static

initialization method of separator (called after problem was transformed)

Definition at line 1830 of file sepa_interminor.c.

References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), sepadata, and TRUE.

◆ SCIP_DECL_SEPAEXIT()

SCIP_DECL_SEPAEXIT ( sepaExitMinor )
static

deinitialization method of separator (called before transformed problem is freed)

Definition at line 1848 of file sepa_interminor.c.

References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), and sepadata.

◆ SCIP_DECL_SEPAINITSOL()

SCIP_DECL_SEPAINITSOL ( sepaInitsolMinor )
static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 1866 of file sepa_interminor.c.

References SCIP_OKAY.

◆ SCIP_DECL_SEPAEXITSOL()

SCIP_DECL_SEPAEXITSOL ( sepaExitsolMinor )
static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 1874 of file sepa_interminor.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), sepadata, and sepadataClear().

◆ SCIP_DECL_SEPAEXECLP()

SCIP_DECL_SEPAEXECLP ( sepaExeclpMinor )
static