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_convexproj.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_convexproj.h
17
* @ingroup SEPARATORS
18
* @brief convexproj separator
19
* @author Felipe Serrano
20
*
21
* This separator receives a point \f$ x_0 \f$ to separate, projects it onto a convex relaxation
22
* of the current problem and then generates gradient cuts at the projection.
23
*
24
* In more detail, the separators builds and stores a convex relaxation of the problem
25
* \f[
26
* C = \{ x \colon g_j(x) \le 0 \, \forall j=1,\ldots,m \}
27
* \f]
28
* where each \f$ g_j \f$ is a convex function and computes the projection by solving
29
* \f[
30
* \min || x - x_0 ||^2 \\
31
* \f]
32
* \f[
33
* s.t. \; g_j(x) \le 0 \, \forall j=1,\ldots,m \\
34
* \f]
35
*
36
* By default, the separator runs only if the convex relaxation has at least one nonlinear convex function
37
*
38
* The separator generates cuts for constraints which were violated by the solution we want to separate and active
39
* at the projection. If the projection problem is not solved to optimality, it still tries to add a cut at the
40
* best solution found. In case that the projection problem is solved to optimality, it is guaranteed that a cut
41
* separates the point. To see this, remember that \f$ z \f$ is the projection if and only if
42
* \f[
43
* \langle x - z, z - x_0 \rangle \ge 0 \, \forall x \in C \\
44
* \f]
45
* This inequality is violated by for \f$ x = x_0 \f$. On the other hand, one of the optimality conditions of the
46
* projection problem at the optimum looks like
47
* \f[
48
* 2 (z - x_0) + \sum_j \lambda_j \nabla g_j(z) = 0
49
* \f]
50
* Now suppose that the no gradient cut at \f$ z \f$ separates \f$ x_0 \f$, i.e.,
51
* \f[
52
* g_j(z) + \langle \nabla g_j(z), x_0 - z \rangle \le 0
53
* \f]
54
* Multiplying each inequality with \f$ \lambda_j \ge 0 \f$ and summing up, we get the following contradiction:
55
* \f[
56
* \langle -2(z - x_0), x_0 - z \rangle \le 0
57
* \f]
58
*/
59
60
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61
62
#ifndef __SCIP_SEPA_CONVEXPROJ_H__
63
#define __SCIP_SEPA_CONVEXPROJ_H__
64
65
66
#include "
scip/scip.h
"
67
68
#ifdef __cplusplus
69
extern
"C"
{
70
#endif
71
72
/** creates the convexproj separator and includes it in SCIP
73
*
74
* @ingroup SeparatorIncludes
75
*/
76
extern
77
SCIP_RETCODE
SCIPincludeSepaConvexproj
(
78
SCIP
*
scip
/**< SCIP data structure */
79
);
80
81
#ifdef __cplusplus
82
}
83
#endif
84
85
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludeSepaConvexproj
SCIP_RETCODE SCIPincludeSepaConvexproj(SCIP *scip)
Definition:
sepa_convexproj.c:889
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.