SCIP

Solving Constraint Integer Programs

sepa_gauge.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file sepa_gauge.h
17  * @ingroup SEPARATORS
18  * @brief gauge separator
19  * @author Felipe Serrano
20  *
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$
23  * and \f$\bar x \f$. Then it generates gradient cuts at the intersection.
24  *
25  * The interior point \f$\bar x \f$ is computed only once, by solving
26  * \f{align}{
27  * \min \; & t \\
28  * s.t. \; & g_j(x) \le t & \forall j=1,\ldots,m \\
29  * & l_k(x) \le 0 & \forall k=1,\ldots,p
30  * \f}
31  * where each \f$g_j \f$ is a convex function and \f$l_k \f$ is a linear function and
32  * \f[
33  * C = \{ x \colon g_j(x) \le 0 \, \forall j=1,\ldots,m, l_k(x) \le 0 \, \forall k=1,\ldots,p \}
34  * \f]
35  * is a convex relaxation of the current problem.
36  * If we can not find an interior solution, the separator will not be executed again.
37  *
38  * 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
39  * of \f$l_k(x) \le t \f$, since some of the inequalities might actually be equalities, forcing \f$t \f$ to zero.
40  * We also use an arbitrary lower bound on \f$t \f$ to handle the case when \f$C \f$ is unbounded.
41  *
42  * By default, the separator, if enabled, runs only if the convex relaxation has at least two nonlinear convex constraints.
43  *
44  * In order to compute the boundary point, we consider only nonlinear convex constraints that are violated by the point
45  * we want to separate. These constraints define a convex region for which \f$\bar x \f$ is an interior point. Then,
46  * a binary search is perform on the segment \f$[\bar x, x_0]\f$ in order to find the boundary point. Gradient cuts are
47  * computed for each of these nonlinear convex constraints which are active at the boundary point.
48  *
49  * Technical details:
50  * - We consider a constraint for the binary search only when its violation is larger than \f$10^{-4} \f$, see
51  * MIN_VIOLATION in sepa_gauge.c. The reason is that if the violation is too small, chances are that the point in the
52  * boundary is in the interior for this constraint and we wouldn't generate a cut for it anyway. On the other hand,
53  * even if we generate a cut for this constraint, it is likely that the boundary point is very close to the point to
54  * separate. Hence the cut generated would be very similar to the gradient cut at the point to separate.
55  * - Before separating, if a slight perturbation of the interior point in the direction of the point to separate
56  * gives a point outside the region, we do not separate. The reason is that the interior point we computed could be
57  * almost at the boundary and the segment \f$[\bar x, x_0]\f$ could be tangent to the region. In that case, the cuts
58  * we generate will not separate \f$x_0 \f$ from the feasible region.
59  *
60  * This separator is currently disabled by default. It requires additional
61  * tuning to be enabled by default. However, it may be useful to enable
62  * it on instances with convex nonlinear constraints if SCIP spends
63  * many iterations in the separation loop without doing sufficient progress.
64  */
65
66 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67
68 #ifndef __SCIP_SEPA_GAUGE_H__
69 #define __SCIP_SEPA_GAUGE_H__
70
71
72 #include "scip/def.h"
73 #include "scip/type_retcode.h"
74 #include "scip/type_scip.h"
75
76 #ifdef __cplusplus
77 extern "C" {
78 #endif
79
80 /** creates the gauge separator and includes it in SCIP
81  *
82  * @ingroup SeparatorIncludes
83  */
84 SCIP_EXPORT
86  SCIP* scip /**< SCIP data structure */
87  );
88
89 #ifdef __cplusplus
90 }
91 #endif
92
93 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPincludeSepaGauge(SCIP *scip)
Definition: sepa_gauge.c:979
common defines and data types used in all packages of SCIP