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-2020 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
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
64 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
65 { /*lint --e{715}*/
66  return SCIP_OKAY;
67 }
68 
69 
70 /** execution method of relaxator */
71 static
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 */
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") );
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) );
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");
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 */
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 */
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 */
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 }
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip, SCIP_RELAX *relax, SCIP_Bool includeslp)
Definition: scip_var.c:2561
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:596
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip_nlp.c:119
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip_var.c:2636
static SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
Definition: relax_nlp.c:56
internal methods for NLPI solver interfaces
#define RELAX_DESC
Definition: relax_nlp.c:30
#define FEASTOLFAC
Definition: relax_nlp.c:36
SCIP_RETCODE SCIPnlpiCreateProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem, const char *name)
Definition: nlpi.c:212
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define RELAX_PRIORITY
Definition: relax_nlp.c:31
SCIP_RETCODE SCIPnlpiSetRealPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, SCIP_Real dval)
Definition: nlpi.c:672
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_RELAX *relax, SCIP_VAR *var, SCIP_Real val)
Definition: scip_var.c:2418
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:575
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:417
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip_relax.c:208
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:619
SCIP_RETCODE SCIPincludeRelaxNlp(SCIP *scip)
Definition: relax_nlp.c:181
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:538
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:512
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
#define NLPVERLEVEL
Definition: relax_nlp.c:35
#define SCIP_CALL(x)
Definition: def.h:364
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip_nlp.c:439
#define RELAX_NAME
Definition: relax_nlp.c:29
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3013
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_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:210
int SCIPgetNNlpis(SCIP *scip)
Definition: scip_nlp.c:132
SCIP_RETCODE SCIPnlpiSetIntPar(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_NLPPARAM type, int ival)
Definition: nlpi.c:637
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:498
SCIP_RETCODE SCIPclearRelaxSolVals(SCIP *scip, SCIP_RELAX *relax)
Definition: scip_var.c:2368
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip_lp.c:2715
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
static SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
Definition: relax_nlp.c:64
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip_relax.c:192
SCIP_RETCODE SCIPnlpiFreeProblem(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM **problem)
Definition: nlpi.c:225
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3047
static SCIP_DECL_RELAXEXEC(relaxExecNlp)
Definition: relax_nlp.c:72
#define SCIP_Real
Definition: def.h:163
SCIP_Bool SCIPisRelaxSolValid(SCIP *scip)
Definition: scip_var.c:2541
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define NLPITERLIMIT
Definition: relax_nlp.c:34
#define RELOBJTOLFAC
Definition: relax_nlp.c:37
nlp relaxator
#define RELAX_FREQ
Definition: relax_nlp.c:32
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)