Scippy

SCIP

Solving Constraint Integer Programs

struct_nlp.h
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 struct_nlp.h
17  * @ingroup INTERNALAPI
18  * @brief datastructures for NLP management
19  * @author Thorsten Gellermann
20  * @author Stefan Vigerske
21  *
22  * In SCIP, the NLP is defined as follows:
23  *
24  * min const + obj * x + <x, Qx> + f(x)
25  * lhs <= const + A * x <= rhs
26  * lhs <= const + A * x + <x, Qx> + f(x) <= rhs
27  * lb <= x <= ub
28  *
29  * where the linear rows and variable bounds are managed by the LP
30  * and the nonlinear rows are managed by the NLP.
31  *
32  * The row activities are defined as
33  * activity = A * x + const
34  * for a linear row and as
35  * activity = f(x) + <x, Qx> + A * x + const
36  * for a nonlinear row.
37  * The activities must therefore be in the range of [lhs,rhs].
38  *
39  * The main datastructures for storing an NLP are the nonlinear rows.
40  * A nonlinear row can live on its own (if it was created by a separator),
41  * or as relaxation of a constraint. Thus, it has a nuses-counter, and is
42  * deleted, if not needed any more.
43  * In difference to columns of an LP, nonlinear rows are defined
44  * with respect SCIP variables.
45  */
46 
47 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 
49 #ifndef __SCIP_STRUCT_NLP_H__
50 #define __SCIP_STRUCT_NLP_H__
51 
52 #include "scip/def.h"
53 #include "scip/type_nlp.h"
54 #include "scip/type_var.h"
55 #include "nlpi/type_nlpi.h"
56 #include "nlpi/type_expr.h"
57 
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61 
62 /** NLP row */
63 struct SCIP_NlRow
64 {
65  /* sides */
66  SCIP_Real lhs; /**< left hand side */
67  SCIP_Real rhs; /**< right hand side */
68 
69  /* constant part */
70  SCIP_Real constant; /**< constant value */
71 
72  /* linear part */
73  int nlinvars; /**< number of linear variables */
74  int linvarssize; /**< size of arrays storing linear part of row */
75  SCIP_VAR** linvars; /**< linear variables */
76  double* lincoefs; /**< coefficients of linear variables */
77  SCIP_Bool linvarssorted; /**< are the linear coefficients sorted (by variable indices?) */
78 
79  /* quadratic part */
80  int nquadvars; /**< number of variables in quadratic terms */
81  int quadvarssize; /**< size of array storing quadratic variables of row */
82  SCIP_VAR** quadvars; /**< variables in quadratic term */
83  SCIP_HASHMAP* quadvarshash; /**< hash map from variable to indices in quadvars */
84  int nquadelems; /**< number of entries in quadratic matrix */
85  int quadelemssize; /**< size of quadratic elements array */
86  SCIP_QUADELEM* quadelems; /**< entries in quadratic matrix */
87  SCIP_Bool quadelemssorted; /**< are the quadratic elements sorted? */
88 
89  /* nonquadratic part */
90  SCIP_EXPRTREE* exprtree; /**< expression tree representing nonquadratic part */
91 
92  /* miscellaneous */
93  char* name; /**< name */
94  int nuses; /**< number of times, this row is referenced */
95  SCIP_Real activity; /**< row activity value in NLP, or SCIP_INVALID if not yet calculated */
96  SCIP_Longint validactivitynlp; /**< NLP number for which activity value is valid */
97  SCIP_Real pseudoactivity; /**< row activity value in pseudo solution, or SCIP_INVALID if not yet calculated */
98  SCIP_Longint validpsactivitydomchg; /**< domain change number for which pseudo activity value is valid */
99  SCIP_Real minactivity; /**< minimal activity value w.r.t. the variables' bounds, or SCIP_INVALID */
100  SCIP_Real maxactivity; /**< maximal activity value w.r.t. the variables' bounds, or SCIP_INVALID */
101  SCIP_Longint validactivitybdsdomchg; /**< domain change number for which activity bound values are valid */
102  int nlpindex; /**< index of this row in NLP, or -1 if not added */
103  int nlpiindex; /**< index of this row in NLPI problem, or -1 if not in there */
104  SCIP_Real dualsol; /**< dual value associated with row in last NLP solve */
105  SCIP_EXPRCURV curvature; /**< curvature of the nonlinear row */
106 };
107 
108 /** current NLP data */
109 struct SCIP_Nlp
110 {
111  /* NLP solver */
112  SCIP_NLPI* solver; /**< interface to NLP solver, or NULL if no NLP solvers are available */
113  SCIP_NLPIPROBLEM* problem; /**< problem in NLP solver */
114 
115  /* status */
116  int nunflushedvaradd; /**< number of variable additions not flushed to NLPI problem yet */
117  int nunflushedvardel; /**< number of variable deletions not flushed to NLPI problem yet */
118  int nunflushednlrowadd; /**< number of nonlinear row additions not flushed to NLPI problem yet */
119  int nunflushednlrowdel; /**< number of nonlinear row deletions not flushed to NLPI problem yet */
120  SCIP_Bool isrelax; /**< is the current NLP a relaxation of a SCIP problem? */
121  SCIP_Bool indiving; /**< are we currently in diving mode? */
122 
123  /* variables in problem */
124  int nvars; /**< number of variables */
125  int sizevars; /**< allocated space for variables */
126  SCIP_VAR** vars; /**< variables */
127  SCIP_HASHMAP* varhash; /**< variable hash: map SCIP_VAR* to index of variable in NLP */
128  /* variables in NLPI problem */
129  int nvars_solver; /**< number of variables in NLPI problem */
130  int sizevars_solver; /**< allocated space for variables in NLPI problem */
131  int* varmap_nlp2nlpi; /**< index of variables in NLPI problem, or -1 if variable has not been added to NLPI problem yet */
132  int* varmap_nlpi2nlp; /**< index of a NLPI problem variable in NLP (varmap_nlp2nlpi[varmap_nlpi2nlp[i]] == i for i = 0..nvarssolver-1), or -1 if variable has been deleted from NLP */
133 
134  /* nonlinear rows in problem */
135  int nnlrows; /**< number of nonlinear rows */
136  int sizenlrows; /**< allocated space for nonlinear rows */
137  SCIP_NLROW** nlrows; /**< nonlinear rows */
138  /* nonlinear rows in NLPI problem */
139  int nnlrows_solver; /**< number of nonlinear rows in solver */
140  int sizenlrows_solver; /**< allocated space for nonlinear rows in solver */
141  int* nlrowmap_nlpi2nlp; /**< index of a NLPI row in NLP (nlrows[nlrowmap_nlpi2nlp[i]]->nlpiidx == i for i = 0..nnlrows_solver-1), or -1 if row has been deleted from NLP */
142 
143  /* objective function */
144  SCIP_Bool objflushed; /**< is the objective in the NLPI up to date? */
145  SCIP_NLROW* divingobj; /**< objective function during diving */
146 
147  /* initial guess */
148  SCIP_Bool haveinitguess; /**< is an initial guess available? */
149  SCIP_Real* initialguess; /**< initial guess of primal values to use in next NLP solve, if available */
150 
151  /* solution of NLP */
152  SCIP_Real primalsolobjval; /**< objective function value of primal solution */
153  SCIP_NLPSOLSTAT solstat; /**< status of NLP solution (feasible, optimal, unknown...) */
154  SCIP_NLPTERMSTAT termstat; /**< termination status of NLP (normal, some limit reached, ...) */
155  SCIP_Real* varlbdualvals; /**< dual values associated with variable lower bounds */
156  SCIP_Real* varubdualvals; /**< dual values associated with variable upper bounds */
157 
158  /* event handling */
159  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
160  int globalfilterpos; /**< position of event handler in event handler filter */
161 
162  /* fractional variables in last NLP solution */
163  SCIP_VAR** fracvars; /**< fractional variables */
164  SCIP_Real* fracvarssol; /**< values of the fractional variables */
165  SCIP_Real* fracvarsfrac; /**< fractionality of the fractional variables */
166  int nfracvars; /**< number of fractional variables */
167  int npriofracvars; /**< number of fractional variables with highest branching priority */
168  int fracvarssize; /**< size of fracvars* arrays */
169  SCIP_Longint validfracvars; /**< the NLP solve for which the fractional variables are valid, or -1 if never setup */
170 
171  /* miscellaneous */
172  char* name; /**< problem name */
173 };
174 
175 #ifdef __cplusplus
176 }
177 #endif
178 
179 #endif /* __SCIP_STRUCT_NLP_H__ */
int nfracvars
Definition: struct_nlp.h:166
SCIP_Real * fracvarssol
Definition: struct_nlp.h:164
SCIP_Longint validpsactivitydomchg
Definition: struct_nlp.h:98
int * varmap_nlpi2nlp
Definition: struct_nlp.h:132
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition: type_nlpi.h:85
SCIP_EXPRTREE * exprtree
Definition: struct_nlp.h:90
int linvarssize
Definition: struct_nlp.h:74
type definitions for NLP management
SCIP_NLROW * divingobj
Definition: struct_nlp.h:145
SCIP_VAR ** linvars
Definition: struct_nlp.h:75
SCIP_VAR ** fracvars
Definition: struct_nlp.h:163
int nnlrows
Definition: struct_nlp.h:135
SCIP_HASHMAP * quadvarshash
Definition: struct_nlp.h:83
SCIP_NLPSOLSTAT solstat
Definition: struct_nlp.h:153
SCIP_Real * initialguess
Definition: struct_nlp.h:149
SCIP_NLPIPROBLEM * problem
Definition: struct_nlp.h:113
SCIP_Real pseudoactivity
Definition: struct_nlp.h:97
int nvars_solver
Definition: struct_nlp.h:129
int nnlrows_solver
Definition: struct_nlp.h:139
SCIP_VAR ** quadvars
Definition: struct_nlp.h:82
SCIP_Real dualsol
Definition: struct_nlp.h:104
int quadelemssize
Definition: struct_nlp.h:85
int nunflushedvaradd
Definition: struct_nlp.h:116
SCIP_QUADELEM * quadelems
Definition: struct_nlp.h:86
SCIP_NLPI * solver
Definition: struct_nlp.h:112
char * name
Definition: struct_nlp.h:93
SCIP_Bool isrelax
Definition: struct_nlp.h:120
SCIP_Real minactivity
Definition: struct_nlp.h:99
int fracvarssize
Definition: struct_nlp.h:168
SCIP_Longint validfracvars
Definition: struct_nlp.h:169
int sizenlrows
Definition: struct_nlp.h:136
SCIP_Longint validactivitybdsdomchg
Definition: struct_nlp.h:101
int quadvarssize
Definition: struct_nlp.h:81
SCIP_Real * varubdualvals
Definition: struct_nlp.h:156
SCIP_Real rhs
Definition: struct_nlp.h:67
SCIP_Real lhs
Definition: struct_nlp.h:66
SCIP_Bool quadelemssorted
Definition: struct_nlp.h:87
SCIP_Bool objflushed
Definition: struct_nlp.h:144
SCIP_Real maxactivity
Definition: struct_nlp.h:100
SCIP_Real * fracvarsfrac
Definition: struct_nlp.h:165
SCIP_HASHMAP * varhash
Definition: struct_nlp.h:127
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition: type_nlpi.h:69
int nlpiindex
Definition: struct_nlp.h:103
SCIP_EVENTHDLR * eventhdlr
Definition: struct_nlp.h:159
SCIP_Real * varlbdualvals
Definition: struct_nlp.h:155
SCIP_EXPRCURV curvature
Definition: struct_nlp.h:105
SCIP_VAR ** vars
Definition: struct_nlp.h:126
type definitions for problem variables
SCIP_NLPTERMSTAT termstat
Definition: struct_nlp.h:154
#define SCIP_Bool
Definition: def.h:61
int nquadvars
Definition: struct_nlp.h:80
char * name
Definition: struct_nlp.h:172
int globalfilterpos
Definition: struct_nlp.h:160
SCIP_NLROW ** nlrows
Definition: struct_nlp.h:137
SCIP_Bool haveinitguess
Definition: struct_nlp.h:148
int nunflushedvardel
Definition: struct_nlp.h:117
int nunflushednlrowadd
Definition: struct_nlp.h:118
int nvars
Definition: struct_nlp.h:124
enum SCIP_ExprCurv SCIP_EXPRCURV
Definition: type_expr.h:93
int sizevars
Definition: struct_nlp.h:125
SCIP_Bool indiving
Definition: struct_nlp.h:121
int * varmap_nlp2nlpi
Definition: struct_nlp.h:131
type definitions for expressions and expression trees
#define SCIP_Real
Definition: def.h:145
int nunflushednlrowdel
Definition: struct_nlp.h:119
SCIP_Real activity
Definition: struct_nlp.h:95
#define SCIP_Longint
Definition: def.h:130
int nlinvars
Definition: struct_nlp.h:73
int nquadelems
Definition: struct_nlp.h:84
int sizevars_solver
Definition: struct_nlp.h:130
int nlpindex
Definition: struct_nlp.h:102
common defines and data types used in all packages of SCIP
int * nlrowmap_nlpi2nlp
Definition: struct_nlp.h:141
SCIP_Real constant
Definition: struct_nlp.h:70
SCIP_Real primalsolobjval
Definition: struct_nlp.h:152
double * lincoefs
Definition: struct_nlp.h:76
SCIP_Bool linvarssorted
Definition: struct_nlp.h:77
int npriofracvars
Definition: struct_nlp.h:167
SCIP_Longint validactivitynlp
Definition: struct_nlp.h:96
int sizenlrows_solver
Definition: struct_nlp.h:140
type definitions for specific NLP solver interfaces