Scippy

SCIP

Solving Constraint Integer Programs

heur_subnlp.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 heur_subnlp.h
17  * @ingroup PRIMALHEURISTICS
18  * @brief NLP local search primal heuristic using sub-SCIPs
19  * @author Stefan Vigerske
20  *
21  * This heuristic applies a NLP local search to a nonlinear CIP after fixing all discrete variables.
22  * That is, the CIP is copied, all discrete variables are fixed, presolving is applied,
23  * and if the resulting CIP has a nonlinear relaxation, then it is tried to solve this relaxation
24  * by an NLP solver.
25  * The heuristic only runs if continuous nonlinearities are present (@ref SCIPhasNLPContinuousNonlinearity()).
26  *
27  * Fixing values for discrete values are either taken from a solution of the LP relaxation which
28  * satisfies all integrality constraints, or are provided by SCIPupdateStartpointHeurSubNlp().
29  *
30  * This heuristic is orthogonal to the undercover heuristic (@ref heur_undercover.h), which fixes
31  * variables in a nonlinear CIP in a way that a (possibly mixed-integer) linear subproblem is obtained.
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef HEUR_SUBNLP_H_
37 #define HEUR_SUBNLP_H_
38 
39 #include "scip/def.h"
40 #include "scip/type_heur.h"
41 #include "scip/type_result.h"
42 #include "scip/type_retcode.h"
43 #include "scip/type_scip.h"
44 #include "scip/type_sol.h"
45 #include "scip/type_var.h"
46 
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50 
51 /** creates the NLP local search primal heuristic and includes it in SCIP
52  *
53  * @ingroup PrimalHeuristicIncludes
54  */
55 extern
57  SCIP* scip /**< SCIP data structure */
58  );
59 
60 /**@addtogroup PRIMALHEURISTICS
61  *
62  * @{
63  */
64 
65 /** updates the starting point for the NLP heuristic
66  *
67  * Is called, for example, by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails.
68  */
69 extern
71  SCIP* scip, /**< SCIP data structure */
72  SCIP_HEUR* heur, /**< subNLP heuristic */
73  SCIP_SOL* solcand, /**< solution candidate */
74  SCIP_Real violation /**< constraint violation of solution candidate */
75  );
76 
77 /** main procedure of the subNLP heuristic */
78 extern
80  SCIP* scip, /**< original SCIP data structure */
81  SCIP_HEUR* heur, /**< heuristic data structure */
82  SCIP_RESULT* result, /**< pointer to store result of: solution found, no solution found, or fixing is infeasible (cutoff) */
83  SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */
84  SCIP_Longint itercontingent, /**< iteration limit for NLP solver */
85  SCIP_Real timelimit, /**< time limit for NLP solver */
86  SCIP_Real minimprove, /**< desired minimal relative improvement in objective function value */
87  SCIP_Longint* iterused, /**< buffer to store number of iterations used by NLP solver, or NULL if not of interest */
88  SCIP_SOL* resultsol /**< a solution where to store found solution values, if any, or NULL if to try adding to SCIP */
89  );
90 
91 /** for a given solution, resolves the corresponding subNLP and updates solution values for continuous variables, if NLP solution is feasible in original problem */
92 extern
94  SCIP* scip, /**< original SCIP data structure */
95  SCIP_HEUR* heur, /**< heuristic data structure */
96  SCIP_SOL* sol, /**< solution for which to solve NLP, and where to store resolved solution values */
97  SCIP_Bool* success, /**< buffer where to store whether a feasible solution was found */
98  SCIP_Longint itercontingent, /**< iteration limit for NLP solver, or -1 for default of NLP heuristic */
99  SCIP_Real timelimit /**< time limit for NLP solver */
100  );
101 
102 /** adds all known linear constraint to the NLP, if initialized and not done already
103  * This function is temporary and will hopefully become obsolete in the near future.
104  */
105 extern
107  SCIP* scip, /**< original SCIP data structure */
108  SCIP_HEUR* heur, /**< heuristic data structure */
109  SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints, i.e., linear constraints that involve only discrete variables */
110  SCIP_Bool addcontconss /**< whether to add continuous linear constraints, i.e., linear constraints that involve not only discrete variables */
111  );
112 
113 /** gets sub-SCIP used by NLP heuristic, or NULL if none */
114 extern
116  SCIP* scip, /**< original SCIP data structure */
117  SCIP_HEUR* heur /**< heuristic data structure */
118  );
119 
120 /** gets mapping of SCIP variables to sub-SCIP variables */
121 extern
123  SCIP* scip, /**< original SCIP data structure */
124  SCIP_HEUR* heur /**< heuristic data structure */
125  );
126 
127 /** gets mapping of sub-SCIP variables to SCIP variables */
128 extern
130  SCIP* scip, /**< original SCIP data structure */
131  SCIP_HEUR* heur /**< heuristic data structure */
132  );
133 
134 /** gets startpoint candidate to be used in next call to NLP heuristic, or NULL if none */
135 extern
137  SCIP* scip, /**< original SCIP data structure */
138  SCIP_HEUR* heur /**< heuristic data structure */
139  );
140 
141 /* @} */
142 
143 #ifdef __cplusplus
144 }
145 #endif
146 
147 #endif /*HEUR_SUBNLP_H_*/
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_VAR ** SCIPgetVarMappingScip2SubScipHeurSubNlp(SCIP *scip, SCIP_HEUR *heur)
Definition: heur_subnlp.c:2523
SCIP_RETCODE SCIPincludeHeurSubNlp(SCIP *scip)
Definition: heur_subnlp.c:2324
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for return codes for SCIP methods
SCIP_SOL * SCIPgetStartCandidateHeurSubNlp(SCIP *scip, SCIP_HEUR *heur)
Definition: heur_subnlp.c:2557
SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool addcombconss, SCIP_Bool addcontconss)
Definition: heur_subnlp.c:2417
type definitions for primal heuristics
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:62
SCIP_RETCODE SCIPresolveSolHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Longint itercontingent, SCIP_Real timelimit)
Definition: heur_subnlp.c:1898
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_Longint itercontingent, SCIP_Real timelimit, SCIP_Real minimprove, SCIP_Longint *iterused, SCIP_SOL *resultsol)
Definition: heur_subnlp.c:1700
SCIP_VAR ** SCIPgetVarMappingSubScip2ScipHeurSubNlp(SCIP *scip, SCIP_HEUR *heur)
Definition: heur_subnlp.c:2540
type definitions for storing primal CIP solutions
#define SCIP_Real
Definition: def.h:150
result codes for SCIP callback methods
#define SCIP_Longint
Definition: def.h:135
SCIP_RETCODE SCIPupdateStartpointHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *solcand, SCIP_Real violation)
Definition: heur_subnlp.c:2451
common defines and data types used in all packages of SCIP
SCIP * SCIPgetSubScipHeurSubNlp(SCIP *scip, SCIP_HEUR *heur)
Definition: heur_subnlp.c:2506