SCIP
Solving Constraint Integer Programs
sepa_minor.h File Reference
Detailed Description
principal minor separator
This separator detects all principal minors of the matrix \( xx' \) for which all auxiliary variables \( X \) exist, i.e., two indices \( i \neq j \) such that \( X_{ii} \), \( X_{jj} \), and \( X_{ij} \) exist. Because \( X - xx' \) is required to be positive semi-definite, it follows that the matrix
\[ A(x,X) = \begin{bmatrix} 1 & x_i & x_j \\ x_i & X_{ii} & X_{ij} \\ x_j & X_{ij} & X_{jj} \end{bmatrix} \]
is also required to be positive semi-definite. Let \( v \) be a negative eigenvector for \( A(x^*,X^*) \) in a point \( (x^*,X^*) \), which implies that \( v' A(x^*,X^*) v < 0 \). To cut off \( (x^*,X^*) \), the separator computes the globally valid linear inequality \( v' A(x,X) v \ge 0 \).
To identify which entries of the matrix X exist, we (the separator) iterate over the available nonlinear constraints. For each constraint, we explore its expression and collect all nodes (expressions) of the form
- \(x^2\)
- \(y \cdot z\)
Then, we go through the found bilinear terms \((yz)\) and if the corresponding \(y^2\) and \(z^2\) exist, then we have found a minor.
For circle packing instances, the minor cuts are not really helpful (see Packing circles in a square: a theoretical comparison of various convexification techniques). Furthermore, the performance was negatively affected, thus circle packing constraint are identified and ignored in the above algorithm. This behavior is controlled with the parameter "separating/minor/ignorepackingconss".
Definition in file sepa_minor.h.
#include "scip/scip.h"Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeSepaMinor (SCIP *scip) |