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