SCIP
Solving Constraint Integer Programs
sepa_gauge.h File Reference
Detailed Description
gauge separator
This separator receives a point \( x_0 \) to separate and, given an interior point \( \bar x \), finds the intersection between the boundary of a convex relaxation of the current problem and the segment joining \( x_0 \) and \( \bar x \). Then it generates gradient cuts at the intersection.
The interior point \( \bar x \) is computed only once, by solving
\[ \min t \\ \]
\[ s.t. \; g_j(x) \le t \, \forall j=1,\ldots,m \]
\[ l_k(x) \le 0 \, \forall k=1,\ldots,p \]
where each \( g_j \) is a convex function and \( l_k \) is a linear function and
\[ C = \{ x \colon g_j(x) \le 0 \, \forall j=1,\ldots,m, l_k(x) \le 0 \, \forall k=1,\ldots,p \} \]
is a convex relaxation of the current problem. If we can not find an interior solution, the separator will not be executed again.
Note that we do not try to push the linear constraints into the interior, i.e. we use \( l_k(x) \le 0 \) instead of \( l_k(x) \le t \), since some of the inequalities might actually be equalities, forcing \( t \) to zero. We also use an arbitrary lower bound on \( t \) to handle the case when \( C \) is unbounded.
By default, the separator runs only if the convex relaxation has at least two nonlinear convex constraints.
In order to compute the boundary point, we consider only nonlinear convex constraints that are violated by the point we want to separate. These constraints define a convex region for which \( \bar x \) is an interior point. Then, a binary search is perform on the segment \([\bar x, x_0]\) in order to find the boundary point. Gradient cuts are computed for each of these nonlinear convex constraints which are active at the boundary point.
Technical details:
- We consider a constraint for the binary search, only when its violation is larger than \( 10^{-4} \), see MIN_VIOLATION in sepa_gauge.c. The reason is that if the violation is too small, chances are that the point in the boundary is in the interior for this constraint and we wouldn't generate a cut for it anyway. On the other hand, even if we generate a cut for this constraint, it is likely that the boundary point is very close to the point to separate. Hence the cut generate would be very similar to the gradient cut at the point to separate.
- Before separating, if a slight perturbation of the interior point in the direction of the point to separate is gives a point outside the region, we do not separate. The reason is that the interior point we computed could be almost at the boundary and the segment \([\bar x, x_0]\) could be tangent to the region. In that case, the cuts we generate will not separate \( x_0 \) from the feasible region.
Definition in file sepa_gauge.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeSepaGauge (SCIP *scip) |