1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /*                                                                           */
3 /*                  This file is part of the program and library             */
4 /*         SCIP --- Solving Constraint Integer Programs                      */
5 /*                                                                           */
6 /*    Copyright (C) 2002-2021 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
SCIP_DECL_RELAXINITSOL(relaxInitsolNlp)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
SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)64 SCIP_DECL_RELAXEXITSOL(relaxExitsolNlp)
65 {  /*lint --e{715}*/
66    return SCIP_OKAY;
67 }
68 
69 
70 /** execution method of relaxator */
71 static
SCIP_DECL_RELAXEXEC(relaxExecNlp)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 */
85    if( !SCIPisNLPConstructed(scip) || SCIPinProbing(scip) || SCIPinDive(scip) || !SCIPallColsInLP(scip) || (SCIPgetNNlpis(scip) == 0) )
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") );
96    SCIP_CALL( SCIPhashmapCreate(&var2idx, SCIPblkmem(scip), SCIPgetNVars(scip)) );
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) );
115    SCIP_CALL( SCIPnlpiSetIntPar(nlpi, nlpiprob, SCIP_NLPPAR_ITLIM, NLPITERLIMIT) );
116    SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_FEASTOL, SCIPfeastol(scip) * FEASTOLFAC) );
117    SCIP_CALL( SCIPnlpiSetRealPar(nlpi, nlpiprob, SCIP_NLPPAR_RELOBJTOL, SCIPfeastol(scip) * RELOBJTOLFAC) );
118    SCIP_CALL( SCIPnlpiSetIntPar(nlpi, nlpiprob, SCIP_NLPPAR_VERBLEVEL, NLPVERLEVEL) );
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");
141          SCIP_CALL( SCIPclearRelaxSolVals(scip, relax) );
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 */
160          SCIP_CALL( SCIPmarkRelaxSolValid(scip, relax, TRUE) );
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 */
SCIPincludeRelaxNlp(SCIP * scip)181 SCIP_RETCODE SCIPincludeRelaxNlp(
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 */
193    SCIP_CALL( SCIPincludeRelaxBasic(scip, &relax, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ,
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 }
204