1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file relax_nlp.c
17 * @brief nlp relaxator
18 * @author Benjamin Mueller
19 */
20
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22
23 #include <assert.h>
24
25 #include "nlpi/nlpi.h"
26 #include "relax_nlp.h"
27
28
29 #define RELAX_NAME "nlp"
30 #define RELAX_DESC "relaxator solving a convex NLP relaxation"
31 #define RELAX_PRIORITY 10
32 #define RELAX_FREQ 1
33
34 #define NLPITERLIMIT 500 /**< iteration limit of NLP solver */
35 #define NLPVERLEVEL 0 /**< verbosity level of NLP solver */
36 #define FEASTOLFAC 0.01 /**< factor for NLP feasibility tolerance */
37 #define RELOBJTOLFAC 0.01 /**< factor for NLP relative objective tolerance */
38
39 /*
40 * Data structures
41 */
42
43
44 /*
45 * Local methods
46 */
47
48
49 /*
50 * Callback methods of relaxator
51 */
52
53
54 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
55 static
SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)56 SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
57 { /*lint --e{715}*/
58 return SCIP_OKAY;
59 }
60
61
62 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
63 static
SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)64 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
65 { /*lint --e{715}*/
66 return SCIP_OKAY;
67 }
68
69
70 /** execution method of relaxator */
71 static
SCIP_DECL_RELAXEXEC(relaxExecNlp)72 SCIP_DECL_RELAXEXEC(relaxExecNlp)
73 { /*lint --e{715}*/
74 SCIP_NLROW** nlrows;
75 SCIP_NLPIPROBLEM* nlpiprob;
76 SCIP_HASHMAP* var2idx;
77 SCIP_NLPI* nlpi;
78 SCIP_Real timelimit;
79 int nnlrows;
80
81 *result = SCIP_DIDNOTRUN;
82 *lowerbound = -SCIPinfinity(scip);
83
84 /* check if it is not possible to run the relaxator */
85 if( !SCIPisNLPConstructed(scip) || SCIPinProbing(scip) || SCIPinDive(scip) || !SCIPallColsInLP(scip) || (SCIPgetNNlpis(scip) == 0) )
86 return SCIP_OKAY;
87
88 nlrows = SCIPgetNLPNlRows(scip);
89 nnlrows = SCIPgetNNLPNlRows(scip);
90
91 /* create a convex NLP relaxation */
92 nlpi = SCIPgetNlpis(scip)[0];
93 assert(nlpi != NULL);
94
95 SCIP_CALL( SCIPnlpiCreateProblem(nlpi, &nlpiprob, "relax-NLP") );
96 SCIP_CALL( SCIPhashmapCreate(&var2idx, SCIPblkmem(scip), SCIPgetNVars(scip)) );
97
98 SCIP_CALL( SCIPcreateNlpiProb(scip, nlpi, nlrows, nnlrows, nlpiprob, var2idx, NULL, NULL, SCIPgetCutoffbound(scip),
99 TRUE, TRUE) );
100 SCIP_CALL( SCIPaddNlpiProbRows(scip, nlpi, nlpiprob, var2idx, SCIPgetLPRows(scip), SCIPgetNLPRows(scip)) );
101
102 /* set working limits */
103 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
104 if( !SCIPisInfinity(scip, timelimit) )
105 {
106 timelimit -= SCIPgetSolvingTime(scip);
107 if( timelimit <= 1.0 )
108 {
109 SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
110 return SCIP_OKAY;
111 }
112 }
113
114 SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
115 SCIP_CALL( SCIPnlpiSetIntPar(nlpi, nlpiprob, SCIP_NLPPAR_ITLIM, NLPITERLIMIT) );
116 SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_FEASTOL, SCIPfeastol(scip) * FEASTOLFAC) );
117 SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_RELOBJTOL, SCIPfeastol(scip) * RELOBJTOLFAC) );
118 SCIP_CALL( SCIPnlpiSetIntPar(nlpi, nlpiprob, SCIP_NLPPAR_VERBLEVEL, NLPVERLEVEL) );
119
120 /* solve NLP */
121 SCIP_CALL( SCIPnlpiSolve(nlpi, nlpiprob) );
122
123 /* forward solution if we solved to optimality; local optimality is enough since the NLP is convex */
124 if( SCIPnlpiGetSolstat(nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_LOCOPT )
125 {
126 SCIP_VAR** vars;
127 SCIP_Real* primal;
128 SCIP_Real relaxval;
129 int nvars;
130 int i;
131
132 vars = SCIPgetVars(scip);
133 nvars = SCIPgetNVars(scip);
134
135 SCIP_CALL( SCIPnlpiGetSolution(nlpi, nlpiprob, &primal, NULL, NULL, NULL, &relaxval) );
136
137 /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
138 if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
139 {
140 SCIPdebugMsg(scip, "Setting NLP relaxation solution, which improved upon earlier solution\n");
141 SCIP_CALL( SCIPclearRelaxSolVals(scip, relax) );
142
143 for( i = 0; i < nvars; ++i )
144 {
145 #ifndef NDEBUG
146 SCIP_Real lb;
147 SCIP_Real ub;
148
149 lb = SCIPvarGetLbLocal(vars[i]);
150 ub = SCIPvarGetUbLocal(vars[i]);
151 assert(SCIPisInfinity(scip, -lb) || SCIPisLE(scip, lb, primal[i]));
152 assert(SCIPisInfinity(scip, ub) || SCIPisLE(scip, primal[i], ub));
153 SCIPdebugMsg(scip, "relax value of %s = %g in [%g,%g]\n", SCIPvarGetName(vars[i]), primal[i], lb, ub);
154 #endif
155
156 SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, vars[i], primal[i]) );
157 }
158
159 /* mark relaxation solution to be valid */
160 SCIP_CALL( SCIPmarkRelaxSolValid(scip, relax, TRUE) );
161 }
162
163 SCIPdebugMsg(scip, "NLP lower bound = %g\n", relaxval);
164 *lowerbound = relaxval;
165 *result = SCIP_SUCCESS;
166 }
167
168 /* free memory */
169 SCIPhashmapFree(&var2idx);
170 SCIP_CALL( SCIPnlpiFreeProblem(nlpi, &nlpiprob) );
171
172 return SCIP_OKAY;
173 }
174
175
176 /*
177 * relaxator specific interface methods
178 */
179
180 /** creates the nlp relaxator and includes it in SCIP */
SCIPincludeRelaxNlp(SCIP * scip)181 SCIP_RETCODE SCIPincludeRelaxNlp(
182 SCIP* scip /**< SCIP data structure */
183 )
184 {
185 SCIP_RELAXDATA* relaxdata;
186 SCIP_RELAX* relax;
187
188 /* create nlp relaxator data */
189 relaxdata = NULL;
190 relax = NULL;
191
192 /* include relaxator */
193 SCIP_CALL( SCIPincludeRelaxBasic(scip, &relax, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ,
194 relaxExecNlp, relaxdata) );
195
196 assert(relax != NULL);
197
198 /* set non fundamental callbacks via setter functions */
199 SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolNlp) );
200 SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolNlp) );
201
202 return SCIP_OKAY;
203 }
204