Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.2.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
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-2017 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 email to 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/scip.h
"
72
73
#ifdef __cplusplus
74
extern
"C"
{
75
#endif
76
77
/** creates the gauge separator and includes it in SCIP
78
*
79
* @ingroup SeparatorIncludes
80
*/
81
extern
82
SCIP_RETCODE
SCIPincludeSepaGauge
(
83
SCIP
*
scip
/**< SCIP data structure */
84
);
85
86
#ifdef __cplusplus
87
}
88
#endif
89
90
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludeSepaGauge
SCIP_RETCODE SCIPincludeSepaGauge(SCIP *scip)
Definition:
sepa_gauge.c:1049
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.