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-2022 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 "relax_nlp.h"
26 #include "scip/scip_nlpi.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 FEASTOLFAC 0.01 /**< factor for NLP feasibility tolerance */
36 #define RELOBJTOLFAC 0.01 /**< factor for NLP relative objective tolerance */
37 
38 /*
39  * Data structures
40  */
41 
42 
43 /*
44  * Local methods
45  */
46 
47 
48 /*
49  * Callback methods of relaxator
50  */
51 
52 
53 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
54 static
55 SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
56 { /*lint --e{715}*/
57  return SCIP_OKAY;
58 }
59 
60 
61 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
62 static
63 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
64 { /*lint --e{715}*/
65  return SCIP_OKAY;
66 }
67 
68 
69 /** execution method of relaxator */
70 static
71 SCIP_DECL_RELAXEXEC(relaxExecNlp)
72 { /*lint --e{715}*/
73  SCIP_NLROW** nlrows;
74  SCIP_NLPIPROBLEM* nlpiprob;
75  SCIP_HASHMAP* var2idx;
76  SCIP_NLPI* nlpi;
78  int nnlrows;
79 
80  *result = SCIP_DIDNOTRUN;
81  *lowerbound = -SCIPinfinity(scip);
82 
83  /* check if it is not possible to run the relaxator */
85  return SCIP_OKAY;
86 
87  nlrows = SCIPgetNLPNlRows(scip);
88  nnlrows = SCIPgetNNLPNlRows(scip);
89 
90  /* create a convex NLP relaxation */
91  nlpi = SCIPgetNlpis(scip)[0];
92  assert(nlpi != NULL);
93 
95 
96  SCIP_CALL( SCIPcreateNlpiProblemFromNlRows(scip, nlpi, &nlpiprob, "relax-NLP", nlrows, nnlrows, var2idx, NULL, NULL, SCIPgetCutoffbound(scip),
97  TRUE, TRUE) );
99 
100  nlpparam.iterlimit = NLPITERLIMIT;
101  nlpparam.feastol = SCIPfeastol(scip) * FEASTOLFAC;
102  nlpparam.opttol = SCIPfeastol(scip) * RELOBJTOLFAC;
103 
104  /* solve NLP */
105  SCIP_CALL( SCIPsolveNlpiParam(scip, nlpi, nlpiprob, nlpparam) );
106 
107  /* forward solution if we solved to optimality; local optimality is enough since the NLP is convex */
108  if( SCIPgetNlpiSolstat(scip, nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_LOCOPT )
109  {
110  SCIP_VAR** vars;
111  SCIP_Real* primal;
112  SCIP_Real relaxval;
113  int nvars;
114  int i;
115 
116  vars = SCIPgetVars(scip);
117  nvars = SCIPgetNVars(scip);
118 
119  SCIP_CALL( SCIPgetNlpiSolution(scip, nlpi, nlpiprob, &primal, NULL, NULL, NULL, &relaxval) );
120 
121  /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
122  if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
123  {
124  SCIPdebugMsg(scip, "Setting NLP relaxation solution, which improved upon earlier solution\n");
126 
127  for( i = 0; i < nvars; ++i )
128  {
129  #ifndef NDEBUG
130  SCIP_Real lb;
131  SCIP_Real ub;
132 
133  lb = SCIPvarGetLbLocal(vars[i]);
134  ub = SCIPvarGetUbLocal(vars[i]);
135  assert(SCIPisInfinity(scip, -lb) || SCIPisLE(scip, lb, primal[i]));
136  assert(SCIPisInfinity(scip, ub) || SCIPisLE(scip, primal[i], ub));
137  SCIPdebugMsg(scip, "relax value of %s = %g in [%g,%g]\n", SCIPvarGetName(vars[i]), primal[i], lb, ub);
138  #endif
139 
140  SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, vars[i], primal[i]) );
141  }
142 
143  /* mark relaxation solution to be valid */
145  }
146 
147  SCIPdebugMsg(scip, "NLP lower bound = %g\n", relaxval);
148  *lowerbound = relaxval;
149  *result = SCIP_SUCCESS;
150  }
151 
152  /* free memory */
153  SCIPhashmapFree(&var2idx);
154  SCIP_CALL( SCIPfreeNlpiProblem(scip, nlpi, &nlpiprob) );
155 
156  return SCIP_OKAY;
157 }
158 
159 
160 /*
161  * relaxator specific interface methods
162  */
163 
164 /** creates the nlp relaxator and includes it in SCIP */
166  SCIP* scip /**< SCIP data structure */
167  )
168 {
169  SCIP_RELAXDATA* relaxdata;
170  SCIP_RELAX* relax;
171 
172  /* create nlp relaxator data */
173  relaxdata = NULL;
174  relax = NULL;
175 
176  /* include relaxator */
178  relaxExecNlp, relaxdata) );
179 
180  assert(relax != NULL);
181 
182  /* set non fundamental callbacks via setter functions */
183  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolNlp) );
184  SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolNlp) );
185 
186  return SCIP_OKAY;
187 }
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:596
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:332
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
SCIP_Real opttol
Definition: type_nlpi.h:61
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip, SCIP_RELAX *relax)
Definition: scip_var.c:2361
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
Definition: relax_nlp.c:55
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_Real feastol
Definition: type_nlpi.h:60
#define RELAX_DESC
Definition: relax_nlp.c:30
#define FEASTOLFAC
Definition: relax_nlp.c:35
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip_relax.c:208
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
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:94
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip_var.c:2629
#define RELAX_PRIORITY
Definition: relax_nlp.c:31
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlpi.c:177
#define SCIPdebugMsg
Definition: scip_message.h:69
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlpi.c:190
public methods for NLPI solver interfaces
SCIP_RETCODE SCIPincludeRelaxNlp(SCIP *scip)
Definition: relax_nlp.c:165
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_RELAX *relax, SCIP_VAR *var, SCIP_Real val)
Definition: scip_var.c:2411
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define NULL
Definition: lpi_spx1.cpp:155
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:617
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:310
#define RELAX_NAME
Definition: relax_nlp.c:29
SCIP_RETCODE SCIPaddNlpiProblemRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip_nlpi.c:772
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool includeslp)
Definition: scip_var.c:2554
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:434
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip_lp.c:2760
static SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
Definition: relax_nlp.c:63
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2534
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
static SCIP_DECL_RELAXEXEC(relaxExecNlp)
Definition: relax_nlp.c:71
#define SCIP_NLPPARAM_DEFAULT(scip)
Definition: type_nlpi.h:117
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:640
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define NLPITERLIMIT
Definition: relax_nlp.c:34
#define RELOBJTOLFAC
Definition: relax_nlp.c:36
nlp relaxator
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip_relax.c:192
#define RELAX_FREQ
Definition: relax_nlp.c:32