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
heur_multistart.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 heur_multistart.h
17
* @ingroup PRIMALHEURISTICS
18
* @brief multistart heuristic for convex and nonconvex MINLPs
19
* @author Benjamin Mueller
20
*
21
* The heuristic applies multiple NLP local searches to a mixed-integer nonlinear program with, probably nonconvex,
22
* constraints of the form \f$g_j(x) \le 0\f$. The algorithm tries to identify clusters which approximate the boundary
23
* of the feasible set of the continuous relaxation by sampling and improving randomly generated points. For each
24
* cluster we use a local search heuristic to find feasible solutions. The algorithm consists of the following four
25
* steps:
26
*
27
* 1. sample points
28
*
29
* Sample random points \f$ x^1, \ldots, x^n \f$ in the box \f$ [\ell,u] \f$. For an unbounded variable \f$ x_i \f$
30
* we consider \f$ [\ell_i,\ell_i + \alpha], [u_i - \alpha,u_i], \f$ or \f$ [-\alpha / 2, \alpha / 2]\f$ for an \f$
31
* \alpha > 0 \f$ depending on which bound is infinite.
32
*
33
* 2. reduce infeasibility
34
*
35
* For each point \f$ x^i \f$ we use a gradient descent method to reduce the maximum infeasibility. We first compute
36
*
37
* \f[
38
* d_j = -\frac{g_j(x^i)}{||\nabla g_j(x^i)||^2} \nabla g_j(x^i)
39
* \f]
40
*
41
* and update the current point \f$ x^i \f$ with
42
*
43
* \f[
44
* x^i := x^i + \frac{1}{n_j} \sum_{j} d_j
45
* \f]
46
*
47
* where \f$ n_j \f$ is the number of strictly positive \f$ d_j \f$. The algorithm is called Constraint Consensus
48
* Method and has been introduced by <a
49
* href="http://www.sce.carleton.ca/faculty/chinneck/docs/ConstraintConsensusJoC.pdf">here </a>.
50
*
51
* 3. cluster points
52
*
53
* We use a greedy algorithm to all of the resulting points of step 3. to find clusters which (hopefully) approximate
54
* the boundary of the feasible set locally. Points with a too large violations will be filtered.
55
*
56
* 4. solve sub-problems
57
*
58
* Depending on the current setting, we solve a sub-problem for each identified cluster. The default strategy is to
59
* compute a starting point for the sub-NLP heuristic (see @ref heur_subnlp.h) by using a linear combination of the
60
* points in a cluster \f$ C \f$, i.e.,
61
*
62
* \f[
63
* s := \sum_{x \in C} \lambda_x x
64
* \f]
65
*
66
* Since the sub-NLP heuristic requires a starting point which is integer feasible we round each fractional
67
* value \f$ s_i \f$ to its closest integer.
68
*/
69
70
71
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
72
73
#ifndef __SCIP_HEUR_MULTISTART_H__
74
#define __SCIP_HEUR_MULTISTART_H__
75
76
77
#include "
scip/scip.h
"
78
79
#ifdef __cplusplus
80
extern
"C"
{
81
#endif
82
83
/** creates the multistart primal heuristic and includes it in SCIP
84
*
85
* @ingroup PrimalHeuristicIncludes
86
*/
87
extern
88
SCIP_RETCODE
SCIPincludeHeurMultistart
(
89
SCIP
*
scip
/**< SCIP data structure */
90
);
91
92
#ifdef __cplusplus
93
}
94
#endif
95
96
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludeHeurMultistart
SCIP_RETCODE SCIPincludeHeurMultistart(SCIP *scip)
Definition:
heur_multistart.c:1037
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.