Scippy

SCIP

Solving Constraint Integer Programs

relax_nlp.c
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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file relax_nlp.c
26  * @brief nlp relaxator
27  * @author Benjamin Mueller
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include <assert.h>
33 
34 #include "relax_nlp.h"
35 #include "scip/scip_nlpi.h"
36 
37 
38 #define RELAX_NAME "nlp"
39 #define RELAX_DESC "relaxator solving a convex NLP relaxation"
40 #define RELAX_PRIORITY 10
41 #define RELAX_FREQ 1
42 
43 #define NLPITERLIMIT 500 /**< iteration limit of NLP solver */
44 #define FEASTOLFAC 0.01 /**< factor for NLP feasibility tolerance */
45 #define RELOBJTOLFAC 0.01 /**< factor for NLP relative objective tolerance */
46 
47 /*
48  * Data structures
49  */
50 
51 
52 /*
53  * Local methods
54  */
55 
56 
57 /*
58  * Callback methods of relaxator
59  */
60 
61 
62 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
63 static
64 SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
65 { /*lint --e{715}*/
66  return SCIP_OKAY;
67 }
68 
69 
70 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
71 static
72 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
73 { /*lint --e{715}*/
74  return SCIP_OKAY;
75 }
76 
77 
78 /** execution method of relaxator */
79 static
80 SCIP_DECL_RELAXEXEC(relaxExecNlp)
81 { /*lint --e{715}*/
82  SCIP_NLROW** nlrows;
83  SCIP_NLPIPROBLEM* nlpiprob;
84  SCIP_HASHMAP* var2idx;
85  SCIP_NLPI* nlpi;
87  int nnlrows;
88 
89  *result = SCIP_DIDNOTRUN;
90  *lowerbound = -SCIPinfinity(scip);
91 
92  /* check if it is not possible to run the relaxator */
94  return SCIP_OKAY;
95 
96  nlrows = SCIPgetNLPNlRows(scip);
97  nnlrows = SCIPgetNNLPNlRows(scip);
98 
99  /* create a convex NLP relaxation */
100  nlpi = SCIPgetNlpis(scip)[0];
101  assert(nlpi != NULL);
102 
104 
105  SCIP_CALL( SCIPcreateNlpiProblemFromNlRows(scip, nlpi, &nlpiprob, "relax-NLP", nlrows, nnlrows, var2idx, NULL, NULL, SCIPgetCutoffbound(scip),
106  TRUE, TRUE) );
107  SCIP_CALL( SCIPaddNlpiProblemRows(scip, nlpi, nlpiprob, var2idx, SCIPgetLPRows(scip), SCIPgetNLPRows(scip)) );
108 
109  nlpparam.iterlimit = NLPITERLIMIT;
110  nlpparam.feastol = SCIPfeastol(scip) * FEASTOLFAC;
111  nlpparam.opttol = SCIPfeastol(scip) * RELOBJTOLFAC;
112 
113  /* solve NLP */
114  SCIP_CALL( SCIPsolveNlpiParam(scip, nlpi, nlpiprob, nlpparam) );
115 
116  /* forward solution if we solved to optimality; local optimality is enough since the NLP is convex */
117  if( SCIPgetNlpiSolstat(scip, nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_LOCOPT )
118  {
119  SCIP_VAR** vars;
120  SCIP_Real* primal;
121  SCIP_Real relaxval;
122  int nvars;
123  int i;
124 
125  vars = SCIPgetVars(scip);
126  nvars = SCIPgetNVars(scip);
127 
128  SCIP_CALL( SCIPgetNlpiSolution(scip, nlpi, nlpiprob, &primal, NULL, NULL, NULL, &relaxval) );
129 
130  /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
131  if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
132  {
133  SCIPdebugMsg(scip, "Setting NLP relaxation solution, which improved upon earlier solution\n");
135 
136  for( i = 0; i < nvars; ++i )
137  {
138  #ifndef NDEBUG
139  SCIP_Real lb;
140  SCIP_Real ub;
141 
142  lb = SCIPvarGetLbLocal(vars[i]);
143  ub = SCIPvarGetUbLocal(vars[i]);
144  assert(SCIPisInfinity(scip, -lb) || SCIPisFeasLE(scip, lb, primal[i]));
145  assert(SCIPisInfinity(scip, ub) || SCIPisFeasLE(scip, primal[i], ub));
146  SCIPdebugMsg(scip, "relax value of %s = %g in [%g,%g]\n", SCIPvarGetName(vars[i]), primal[i], lb, ub);
147  #endif
148 
149  SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, vars[i], primal[i]) );
150  }
151 
152  /* mark relaxation solution to be valid */
154  }
155 
156  SCIPdebugMsg(scip, "NLP lower bound = %g\n", relaxval);
157  *lowerbound = relaxval;
158  *result = SCIP_SUCCESS;
159  }
160 
161  /* free memory */
162  SCIPhashmapFree(&var2idx);
163  SCIP_CALL( SCIPfreeNlpiProblem(scip, nlpi, &nlpiprob) );
164 
165  return SCIP_OKAY;
166 }
167 
168 
169 /*
170  * relaxator specific interface methods
171  */
172 
173 /** creates the nlp relaxator and includes it in SCIP */
175  SCIP* scip /**< SCIP data structure */
176  )
177 {
178  SCIP_RELAXDATA* relaxdata;
179  SCIP_RELAX* relax;
180 
181  /* create nlp relaxator data */
182  relaxdata = NULL;
183  relax = NULL;
184 
185  /* include relaxator */
187  relaxExecNlp, relaxdata) );
188 
189  assert(relax != NULL);
190 
191  /* set non fundamental callbacks via setter functions */
192  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolNlp) );
193  SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolNlp) );
194 
195  return SCIP_OKAY;
196 }
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:605
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:341
#define NULL
Definition: def.h:267
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_Real opttol
Definition: type_nlpi.h:70
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip, SCIP_RELAX *relax)
Definition: scip_var.c:2366
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
Definition: relax_nlp.c:64
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_Real feastol
Definition: type_nlpi.h:69
#define RELAX_DESC
Definition: relax_nlp.c:39
#define FEASTOLFAC
Definition: relax_nlp.c:44
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip_relax.c:217
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPincludeRelaxBasic(SCIP *scip, SCIP_RELAX **relaxptr, const char *name, const char *desc, int priority, int freq, SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: scip_relax.c:103
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip_var.c:2634
#define RELAX_PRIORITY
Definition: relax_nlp.c:40
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlpi.c:187
#define SCIPdebugMsg
Definition: scip_message.h:78
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:200
public methods for NLPI solver interfaces
SCIP_RETCODE SCIPincludeRelaxNlp(SCIP *scip)
Definition: relax_nlp.c:174
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_RELAX *relax, SCIP_VAR *var, SCIP_Real val)
Definition: scip_var.c:2416
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:319
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define RELAX_NAME
Definition: relax_nlp.c:38
SCIP_RETCODE SCIPaddNlpiProblemRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip_nlpi.c:782
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool includeslp)
Definition: scip_var.c:2559
SCIP_RETCODE SCIPcreateNlpiProblemFromNlRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **nlpiprob, const char *name, SCIP_NLROW **nlrows, int nnlrows, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip_nlpi.c:444
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip_lp.c:2775
static SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
Definition: relax_nlp.c:72
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:47
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2539
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
static SCIP_DECL_RELAXEXEC(relaxExecNlp)
Definition: relax_nlp.c:80
#define SCIP_NLPPARAM_DEFAULT(scip)
Definition: type_nlpi.h:126
#define SCIP_Real
Definition: def.h:173
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define NLPITERLIMIT
Definition: relax_nlp.c:43
#define RELOBJTOLFAC
Definition: relax_nlp.c:45
nlp relaxator
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip_relax.c:201
#define RELAX_FREQ
Definition: relax_nlp.c:41