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-2014 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_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/scip.h"
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44 
45 /** creates the NLP local search primal heuristic and includes it in SCIP */
46 extern
47 SCIP_RETCODE SCIPincludeHeurSubNlp(
48  SCIP* scip /**< SCIP data structure */
49  );
50 
51 /** updates the starting point for the NLP heuristic
52  *
53  * Is called, for example, by a constraint handler that handles nonlinear constraints when a check on feasibility of a solution fails.
54  */
55 extern
56 SCIP_RETCODE SCIPupdateStartpointHeurSubNlp(
57  SCIP* scip, /**< SCIP data structure */
58  SCIP_HEUR* heur, /**< subNLP heuristic */
59  SCIP_SOL* solcand, /**< solution candidate */
60  SCIP_Real violation /**< constraint violation of solution candidate */
61  );
62 
63 /** main procedure of the subNLP heuristic */
64 extern
65 SCIP_RETCODE SCIPapplyHeurSubNlp(
66  SCIP* scip, /**< original SCIP data structure */
67  SCIP_HEUR* heur, /**< heuristic data structure */
68  SCIP_RESULT* result, /**< pointer to store result of: solution found, no solution found, or fixing is infeasible (cutoff) */
69  SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from, and startpoint for NLP solver; if NULL, then LP solution is used */
70  SCIP_Longint itercontingent, /**< iteration limit for NLP solver */
71  SCIP_Real timelimit, /**< time limit for NLP solver */
72  SCIP_Real minimprove, /**< desired minimal relative improvement in objective function value */
73  SCIP_Longint* iterused /**< buffer to store number of iterations used by NLP solver, or NULL if not of interest */
74  );
75 
76 /** for a given solution, resolves the corresponding subNLP and updates solution values for continuous variables, if NLP solution is feasible in original problem */
77 extern
78 SCIP_RETCODE SCIPresolveSolHeurSubNlp(
79  SCIP* scip, /**< original SCIP data structure */
80  SCIP_HEUR* heur, /**< heuristic data structure */
81  SCIP_SOL* sol, /**< solution for which to solve NLP, and where to store resolved solution values */
82  SCIP_Bool* success, /**< buffer where to store whether a feasible solution was found */
83  SCIP_Longint itercontingent, /**< iteration limit for NLP solver, or -1 for default of NLP heuristic */
84  SCIP_Real timelimit /**< time limit for NLP solver */
85  );
86 
87 /** adds all known linear constraint to the NLP, if initialized and not done already
88  * This function is temporary and will hopefully become obsolete in the near future.
89  */
90 extern
91 SCIP_RETCODE SCIPaddLinearConsToNlpHeurSubNlp(
92  SCIP* scip, /**< original SCIP data structure */
93  SCIP_HEUR* heur, /**< heuristic data structure */
94  SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints, i.e., linear constraints that involve only discrete variables */
95  SCIP_Bool addcontconss /**< whether to add continuous linear constraints, i.e., linear constraints that involve not only discrete variables */
96  );
97 
98 /** gets sub-SCIP used by NLP heuristic, or NULL if none */
99 extern
100 SCIP* SCIPgetSubScipHeurSubNlp(
101  SCIP* scip, /**< original SCIP data structure */
102  SCIP_HEUR* heur /**< heuristic data structure */
103  );
104 
105 /** gets mapping of SCIP variables to sub-SCIP variables */
106 extern
107 SCIP_VAR** SCIPgetVarMappingScip2SubScipHeurSubNlp(
108  SCIP* scip, /**< original SCIP data structure */
109  SCIP_HEUR* heur /**< heuristic data structure */
110  );
111 
112 /** gets mapping of sub-SCIP variables to SCIP variables */
113 extern
114 SCIP_VAR** SCIPgetVarMappingSubScip2ScipHeurSubNlp(
115  SCIP* scip, /**< original SCIP data structure */
116  SCIP_HEUR* heur /**< heuristic data structure */
117  );
118 
119 /** gets startpoint candidate to be used in next call to NLP heuristic, or NULL if none */
120 extern
121 SCIP_SOL* SCIPgetStartCandidateHeurSubNlp(
122  SCIP* scip, /**< original SCIP data structure */
123  SCIP_HEUR* heur /**< heuristic data structure */
124  );
125 
126 #ifdef __cplusplus
127 }
128 #endif
129 
130 #endif /*HEUR_SUBNLP_H_*/
131