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-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 email to scip@zib.de. */
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
56 SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
57 { /*lint --e{715}*/
58 
59  return SCIP_OKAY;
60 }
61 
62 
63 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
64 static
65 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
66 { /*lint --e{715}*/
67 
68  return SCIP_OKAY;
69 }
70 
71 
72 /** execution method of relaxator */
73 static
74 SCIP_DECL_RELAXEXEC(relaxExecNlp)
75 { /*lint --e{715}*/
76  SCIP_NLROW** nlrows;
77  SCIP_NLPIPROBLEM* nlpiprob;
78  SCIP_HASHMAP* var2idx;
79  SCIP_NLPI* nlpi;
80  SCIP_Real timelimit;
81  int nnlrows;
82 
83  *result = SCIP_DIDNOTRUN;
84  *lowerbound = -SCIPinfinity(scip);
85 
86  /* check if it is not possible to run the relaxator */
88  return SCIP_OKAY;
89 
90  nlrows = SCIPgetNLPNlRows(scip);
91  nnlrows = SCIPgetNNLPNlRows(scip);
92 
93  /* create a convex NLP relaxation */
94  nlpi = SCIPgetNlpis(scip)[0];
95  assert(nlpi != NULL);
96 
97  SCIP_CALL( SCIPnlpiCreateProblem(nlpi, &nlpiprob, "relax-NLP") );
99 
100  SCIP_CALL( SCIPcreateNlpiProb(scip, nlpi, nlrows, nnlrows, nlpiprob, var2idx, NULL, SCIPgetCutoffbound(scip),
101  TRUE, TRUE) );
102  SCIP_CALL( SCIPaddNlpiProbRows(scip, nlpi, nlpiprob, var2idx, SCIPgetLPRows(scip), SCIPgetNLPRows(scip)) );
103 
104  /* set working limits */
105  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
106  if( !SCIPisInfinity(scip, timelimit) )
107  {
108  timelimit -= SCIPgetSolvingTime(scip);
109  if( timelimit <= 1.0 )
110  {
111  SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
112  return SCIP_OKAY;
113  }
114  }
115 
116  SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
121 
122  /* solve NLP */
123  SCIP_CALL( SCIPnlpiSolve(nlpi, nlpiprob) );
124 
125  /* forward solution if we solved to optimality; local optimality is enough since the NLP is convex */
126  if( SCIPnlpiGetSolstat(nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_LOCOPT )
127  {
128  SCIP_VAR** vars;
129  SCIP_Real* primal;
130  SCIP_Real relaxval;
131  int nvars;
132  int i;
133 
134  vars = SCIPgetVars(scip);
135  nvars = SCIPgetNVars(scip);
136 
137  SCIP_CALL( SCIPnlpiGetSolution(nlpi, nlpiprob, &primal, NULL, NULL, NULL, &relaxval) );
138 
139  /* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
140  if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
141  {
142  SCIPdebugMsg(scip, "Setting NLP relaxation solution, which improved upon earlier solution\n");
144 
145  for( i = 0; i < nvars; ++i )
146  {
147  #ifndef NDEBUG
148  SCIP_Real lb;
149  SCIP_Real ub;
150 
151  lb = SCIPvarGetLbLocal(vars[i]);
152  ub = SCIPvarGetUbLocal(vars[i]);
153  assert(SCIPisInfinity(scip, -lb) || SCIPisLE(scip, lb, primal[i]));
154  assert(SCIPisInfinity(scip, ub) || SCIPisLE(scip, primal[i], ub));
155  SCIPdebugMsg(scip, "relax value of %s = %g in [%g,%g]\n", SCIPvarGetName(vars[i]), primal[i], lb, ub);
156  #endif
157 
158  SCIP_CALL( SCIPsetRelaxSolVal(scip, vars[i], primal[i]) );
159  }
160 
161  /* mark relaxation solution to be valid */
163  }
164 
165  SCIPdebugMsg(scip, "NLP lower bound = %g\n", relaxval);
166  *lowerbound = relaxval;
167  *result = SCIP_SUCCESS;
168  }
169 
170  /* free memory */
171  SCIPhashmapFree(&var2idx);
172  SCIP_CALL( SCIPnlpiFreeProblem(nlpi, &nlpiprob) );
173 
174  return SCIP_OKAY;
175 }
176 
177 
178 /*
179  * relaxator specific interface methods
180  */
181 
182 /** creates the nlp relaxator and includes it in SCIP */
184  SCIP* scip /**< SCIP data structure */
185  )
186 {
187  SCIP_RELAXDATA* relaxdata;
188  SCIP_RELAX* relax;
189 
190  /* create nlp relaxator data */
191  relaxdata = NULL;
192  relax = NULL;
193 
194  /* include relaxator */
196  relaxExecNlp, relaxdata) );
197 
198  assert(relax != NULL);
199 
200  /* set non fundamental callbacks via setter functions */
201  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolNlp) );
202  SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolNlp) );
203 
204  return SCIP_OKAY;
205 }
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip.c:29675
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31462
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:46306
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:46443
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:31233
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_Bool includeslp)
Definition: scip.c:20072
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43453
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
Definition: scip.c:34032
static SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
Definition: relax_nlp.c:56
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4489
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
internal methods for NLPI solver interfaces
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:211
#define RELAX_DESC
Definition: relax_nlp.c:30
#define FEASTOLFAC
Definition: relax_nlp.c:36
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues, SCIP_Real *objval)
Definition: nlpi.c:537
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip.c:7262
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2793
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.c:7148
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47028
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip)
Definition: scip.c:19889
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip.c:20145
#define RELAX_PRIORITY
Definition: relax_nlp.c:31
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31440
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:497
SCIP_RETCODE SCIPincludeRelaxNlp(SCIP *scip)
Definition: relax_nlp.c:183
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:46731
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2826
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip.c:34407
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9602
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29696
#define NLPVERLEVEL
Definition: relax_nlp.c:35
#define SCIP_CALL(x)
Definition: def.h:350
#define RELAX_NAME
Definition: relax_nlp.c:29
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:511
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:224
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:636
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47039
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35836
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11812
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip.c:35802
static SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
Definition: relax_nlp.c:65
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:19935
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47002
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip.c:20052
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11767
static SCIP_DECL_RELAXEXEC(relaxExecNlp)
Definition: relax_nlp.c:74
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29719
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46989
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip.c:9589
#define NLPITERLIMIT
Definition: relax_nlp.c:34
#define RELOBJTOLFAC
Definition: relax_nlp.c:37
nlp relaxator
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip.c:7246
#define RELAX_FREQ
Definition: relax_nlp.c:32
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:671