Scippy

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 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
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[
27  * \min t \\
28  * \f]
29  * \f[
30  * s.t. \; g_j(x) \le t \, \forall j=1,\ldots,m
31  * \f]
32  * \f[
33  * l_k(x) \le 0 \, \forall k=1,\ldots,p
34  * \f]
35  * where each \f$ g_j \f$ is a convex function and \f$ l_k \f$ is a linear function and
36  * \f[
37  * C = \{ x \colon g_j(x) \le 0 \, \forall j=1,\ldots,m, l_k(x) \le 0 \, \forall k=1,\ldots,p \}
38  * \f]
39  * is a convex relaxation of the current problem.
40  * If we can not find an interior solution, the separator will not be executed again.
41  *
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.
45  *
46  * By default, the separator runs only if the convex relaxation has at least two nonlinear convex constraints.
47  *
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.
52  *
53  * Technical details:
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
62  * we generate will not separate \f$ x_0 \f$ from the feasible region.
63  */
64 
65 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
66 
67 #ifndef __SCIP_SEPA_GAUGE_H__
68 #define __SCIP_SEPA_GAUGE_H__
69 
70 
71 #include "scip/def.h"
72 #include "scip/type_retcode.h"
73 #include "scip/type_scip.h"
74 
75 #ifdef __cplusplus
76 extern "C" {
77 #endif
78 
79 /** creates the gauge separator and includes it in SCIP
80  *
81  * @ingroup SeparatorIncludes
82  */
83 extern
85  SCIP* scip /**< SCIP data structure */
86  );
87 
88 #ifdef __cplusplus
89 }
90 #endif
91 
92 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
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:1071
common defines and data types used in all packages of SCIP