sepa_gauge.h
Go to the documentation of this file.
21 * This separator receives a point \f$ x_0 \f$ to separate and, given an interior point \f$ \bar x \f$, finds the
22 * intersection between the boundary of a convex relaxation of the current problem and the segment joining \f$ x_0 \f$
42 * Note that we do not try to push the linear constraints into the interior, i.e. we use \f$ l_k(x) \le 0 \f$ instead
43 * of \f$ l_k(x) \le t \f$, since some of the inequalities might actually be equalities, forcing \f$ t \f$ to zero.
44 * We also use an arbitrary lower bound on \f$ t \f$ to handle the case when \f$ C \f$ is unbounded.
46 * By default, the separator runs only if the convex relaxation has at least two nonlinear convex constraints.
48 * In order to compute the boundary point, we consider only nonlinear convex constraints that are violated by the point
49 * we want to separate. These constraints define a convex region for which \f$ \bar x \f$ is an interior point. Then,
50 * a binary search is perform on the segment \f$[\bar x, x_0]\f$ in order to find the boundary point. Gradient cuts are
51 * computed for each of these nonlinear convex constraints which are active at the boundary point.
54 * - We consider a constraint for the binary search, only when its violation is larger than \f$ 10^{-4} \f$, see
55 * MIN_VIOLATION in sepa_gauge.c. The reason is that if the violation is too small, chances are that the point in the
56 * boundary is in the interior for this constraint and we wouldn't generate a cut for it anyway. On the other hand,
57 * even if we generate a cut for this constraint, it is likely that the boundary point is very close to the point to
58 * separate. Hence the cut generate would be very similar to the gradient cut at the point to separate.
59 * - Before separating, if a slight perturbation of the interior point in the direction of the point to separate is
60 * gives a point outside the region, we do not separate. The reason is that the interior point we computed could be
61 * almost at the boundary and the segment \f$[\bar x, x_0]\f$ could be tangent to the region. In that case, the cuts
65 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
Definition: struct_scip.h:59
type definitions for return codes for SCIP methods
type definitions for SCIP's main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPincludeSepaGauge(SCIP *scip)
Definition: sepa_gauge.c:1075
common defines and data types used in all packages of SCIP
Definition: objbenders.h:33