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-2017 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 0
32 #define RELAX_FREQ 1
33 #define RELAX_FULLLPINFO TRUE
34 
35 #define NLPITERLIMIT 500 /**< iteration limit of NLP solver */
36 #define NLPVERLEVEL 0 /**< verbosity level of NLP solver */
37 #define FEASTOLFAC 0.01 /**< factor for NLP feasibility tolerance */
38 #define RELOBJTOLFAC 0.01 /**< factor for NLP relative objective tolerance */
39 
40 /*
41  * Data structures
42  */
43 
44 
45 /*
46  * Local methods
47  */
48 
49 
50 /*
51  * Callback methods of relaxator
52  */
53 
54 
55 /** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
56 static
57 SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
58 { /*lint --e{715}*/
59 
60  return SCIP_OKAY;
61 }
62 
63 
64 /** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
65 static
66 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
67 { /*lint --e{715}*/
68 
69  return SCIP_OKAY;
70 }
71 
72 
73 /** execution method of relaxator */
74 static
75 SCIP_DECL_RELAXEXEC(relaxExecNlp)
76 { /*lint --e{715}*/
77  SCIP_NLROW** nlrows;
78  SCIP_NLPIPROBLEM* nlpiprob;
79  SCIP_HASHMAP* var2idx;
80  SCIP_NLPI* nlpi;
81  SCIP_Real timelimit;
82  int nnlrows;
83 
84  *result = SCIP_DIDNOTRUN;
85  *lowerbound = -SCIPinfinity(scip);
86 
87  /* check if it is not possible to run the relaxator */
89  return SCIP_OKAY;
90 
91  nlrows = SCIPgetNLPNlRows(scip);
92  nnlrows = SCIPgetNNLPNlRows(scip);
93 
94  /* create a convex NLP relaxation */
95  nlpi = SCIPgetNlpis(scip)[0];
96  assert(nlpi != NULL);
97 
98  SCIP_CALL( SCIPnlpiCreateProblem(nlpi, &nlpiprob, "relax-NLP") );
100 
101  SCIP_CALL( SCIPcreateNlpiProb(scip, nlpi, nlrows, nnlrows, nlpiprob, var2idx, NULL, SCIPgetCutoffbound(scip),
102  TRUE, TRUE) );
103  SCIP_CALL( SCIPaddNlpiProbRows(scip, nlpi, nlpiprob, var2idx, SCIPgetLPRows(scip), SCIPgetNLPRows(scip)) );
104 
105  /* set working limits */
106  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
107  if( !SCIPisInfinity(scip, timelimit) )
108  {
109  timelimit -= SCIPgetSolvingTime(scip);
110  if( timelimit <= 1.0 )
111  {
112  SCIPdebugMsg(scip, "skip NLP solve; no time left\n");
113  return SCIP_OKAY;
114  }
115  }
116 
117  SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_TILIM, timelimit) );
122 
123  /* solve NLP */
124  SCIP_CALL( SCIPnlpiSolve(nlpi, nlpiprob) );
125 
126  /* store solution if we solved to optimality; local optimality is enough since the NLP is convex */
127  if( SCIPnlpiGetSolstat(nlpi, nlpiprob) <= SCIP_NLPSOLSTAT_LOCOPT )
128  {
129  SCIP_VAR** vars;
130  SCIP_Real* primal;
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) );
138 
139  for( i = 0; i < nvars; ++i )
140  {
141 #ifndef NDEBUG
142  SCIP_Real lb;
143  SCIP_Real ub;
144 
145  lb = SCIPvarGetLbLocal(vars[i]);
146  ub = SCIPvarGetUbLocal(vars[i]);
147  assert(SCIPisInfinity(scip, -lb) || SCIPisLE(scip, lb, primal[i]));
148  assert(SCIPisInfinity(scip, ub) || SCIPisLE(scip, primal[i], ub));
149  SCIPdebugMsg(scip, "relax value of %s = %g in [%g,%g]\n", SCIPvarGetName(vars[i]), primal[i], lb, ub);
150 #endif
151 
152  SCIP_CALL( SCIPsetRelaxSolVal(scip, vars[i], primal[i]) );
153  }
154 
155  /* mark relaxation solution to be valid */
157 
158  SCIPdebugMsg(scip, "lower bound = %g\n", SCIPgetRelaxSolObj(scip));
159  *lowerbound = SCIPgetRelaxSolObj(scip);
160  *result = SCIP_SUCCESS;
161  }
162 
163  /* free memory */
164  SCIPhashmapFree(&var2idx);
165  SCIP_CALL( SCIPnlpiFreeProblem(nlpi, &nlpiprob) );
166 
167  return SCIP_OKAY;
168 }
169 
170 
171 /*
172  * relaxator specific interface methods
173  */
174 
175 /** creates the nlp relaxator and includes it in SCIP */
177  SCIP* scip /**< SCIP data structure */
178  )
179 {
180  SCIP_RELAXDATA* relaxdata;
181  SCIP_RELAX* relax;
182 
183  /* create nlp relaxator data */
184  relaxdata = NULL;
185  relax = NULL;
186 
187  /* include relaxator */
189  relaxExecNlp, relaxdata) );
190 
191  assert(relax != NULL);
192 
193  /* set non fundamental callbacks via setter functions */
194  SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsolNlp) );
195  SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsolNlp) );
196 
197  return SCIP_OKAY;
198 }
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip.c:29200
int SCIPgetNNLPNlRows(SCIP *scip)
Definition: scip.c:31064
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30835
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
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:33265
static SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)
Definition: relax_nlp.c:57
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4426
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
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:37
SCIP_RETCODE SCIPsetRelaxExitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: scip.c:7202
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
#define RELAX_FULLLPINFO
Definition: relax_nlp.c:33
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetRelaxSolObj(SCIP *scip)
Definition: scip.c:19751
#define RELAX_PRIORITY
Definition: relax_nlp.c:31
SCIP_RETCODE SCIPnlpiGetSolution(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem, SCIP_Real **primalvalues, SCIP_Real **consdualvalues, SCIP_Real **varlbdualvalues, SCIP_Real **varubdualvalues)
Definition: nlpi.c:535
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition: scip.c:31042
SCIP_RETCODE SCIPmarkRelaxSolValid(SCIP *scip)
Definition: scip.c:19679
SCIP_RETCODE SCIPnlpiSolve(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:495
SCIP_RETCODE SCIPincludeRelaxNlp(SCIP *scip)
Definition: relax_nlp.c:176
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
Definition: scip.c:33640
#define NULL
Definition: lpi_spx1.cpp:137
int SCIPgetNNlpis(SCIP *scip)
Definition: scip.c:9444
int SCIPgetNLPRows(SCIP *scip)
Definition: scip.c:29221
#define NLPVERLEVEL
Definition: relax_nlp.c:36
#define SCIP_CALL(x)
Definition: def.h:306
#define RELAX_NAME
Definition: relax_nlp.c:29
SCIP_NLPSOLSTAT SCIPnlpiGetSolstat(SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *problem)
Definition: nlpi.c:509
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:633
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip.c:34999
static SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
Definition: relax_nlp.c:66
SCIP_RETCODE SCIPincludeRelaxBasic(SCIP *scip, SCIP_RELAX **relaxptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool includeslp, SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: scip.c:7087
SCIP_RETCODE SCIPsetRelaxSolVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:19545
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:38
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
static SCIP_DECL_RELAXEXEC(relaxExecNlp)
Definition: relax_nlp.c:75
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29244
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_NLPI ** SCIPgetNlpis(SCIP *scip)
Definition: scip.c:9431
#define NLPITERLIMIT
Definition: relax_nlp.c:35
#define RELOBJTOLFAC
Definition: relax_nlp.c:38
nlp relaxator
SCIP_RETCODE SCIPsetRelaxInitsol(SCIP *scip, SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: scip.c:7186
#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:668