Scippy

SCIP

Solving Constraint Integer Programs

scip_expr.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-2018 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_expr.c
17  * @brief public methods for expression handlers
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  * @author Robert Lion Gottwald
22  * @author Stefan Heinz
23  * @author Gregor Hendel
24  * @author Thorsten Koch
25  * @author Alexander Martin
26  * @author Marc Pfetsch
27  * @author Michael Winkler
28  * @author Kati Wolter
29  *
30  * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <ctype.h>
36 #include <stdarg.h>
37 #include <assert.h>
38 #include <string.h>
39 #if defined(_WIN32) || defined(_WIN64)
40 #else
41 #include <strings.h> /*lint --e{766}*/
42 #endif
43 
44 
45 #include "lpi/lpi.h"
46 #include "nlpi/exprinterpret.h"
47 #include "nlpi/nlpi.h"
48 #include "scip/benders.h"
49 #include "scip/benderscut.h"
50 #include "scip/branch.h"
51 #include "scip/branch_nodereopt.h"
52 #include "scip/clock.h"
53 #include "scip/compr.h"
54 #include "scip/concsolver.h"
55 #include "scip/concurrent.h"
56 #include "scip/conflict.h"
57 #include "scip/conflictstore.h"
58 #include "scip/cons.h"
59 #include "scip/cons_linear.h"
60 #include "scip/cutpool.h"
61 #include "scip/cuts.h"
62 #include "scip/debug.h"
63 #include "scip/def.h"
64 #include "scip/dialog.h"
65 #include "scip/dialog_default.h"
66 #include "scip/disp.h"
67 #include "scip/event.h"
68 #include "scip/heur.h"
69 #include "scip/heur_ofins.h"
70 #include "scip/heur_reoptsols.h"
72 #include "scip/heuristics.h"
73 #include "scip/history.h"
74 #include "scip/implics.h"
75 #include "scip/interrupt.h"
76 #include "scip/lp.h"
77 #include "scip/mem.h"
78 #include "scip/message_default.h"
79 #include "scip/misc.h"
80 #include "scip/nlp.h"
81 #include "scip/nodesel.h"
82 #include "scip/paramset.h"
83 #include "scip/presol.h"
84 #include "scip/presolve.h"
85 #include "scip/pricer.h"
86 #include "scip/pricestore.h"
87 #include "scip/primal.h"
88 #include "scip/prob.h"
89 #include "scip/prop.h"
90 #include "scip/reader.h"
91 #include "scip/relax.h"
92 #include "scip/reopt.h"
93 #include "scip/retcode.h"
94 #include "scip/scipbuildflags.h"
95 #include "scip/scipcoreplugins.h"
96 #include "scip/scipgithash.h"
97 #include "scip/sepa.h"
98 #include "scip/sepastore.h"
99 #include "scip/set.h"
100 #include "scip/sol.h"
101 #include "scip/solve.h"
102 #include "scip/stat.h"
103 #include "scip/syncstore.h"
104 #include "scip/table.h"
105 #include "scip/tree.h"
106 #include "scip/var.h"
107 #include "scip/visual.h"
108 #include "xml/xml.h"
109 
110 #include "scip/scip_expr.h"
111 #include "scip/scip_mem.h"
112 #include "scip/scip_numerics.h"
113 #include "scip/scip_sol.h"
114 #include "scip/scip_var.h"
115 
116 #include "scip/pub_message.h"
117 #include "scip/pub_nlp.h"
118 #include "scip/pub_var.h"
119 
120 
121 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
122  * this structure except the interface methods in scip.c.
123  * In optimized mode, the structure is included in scip.h, because some of the methods
124  * are implemented as defines for performance reasons (e.g. the numerical comparisons)
125  */
126 #ifndef NDEBUG
127 #include "scip/struct_scip.h"
128 #endif
129 
130 /** translate from one value of infinity to another
131  *
132  * if val is >= infty1, then give infty2, else give val
133  */
134 #define infty2infty(infty1, infty2, val) (val >= infty1 ? infty2 : val)
135 
136 /** replaces array of variables in expression tree by corresponding transformed variables
137  *
138  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
139  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
140  *
141  * @pre This method can be called if @p scip is in one of the following stages:
142  * - \ref SCIP_STAGE_TRANSFORMING
143  * - \ref SCIP_STAGE_TRANSFORMED
144  * - \ref SCIP_STAGE_INITPRESOLVE
145  * - \ref SCIP_STAGE_PRESOLVING
146  * - \ref SCIP_STAGE_EXITPRESOLVE
147  * - \ref SCIP_STAGE_PRESOLVED
148  * - \ref SCIP_STAGE_INITSOLVE
149  * - \ref SCIP_STAGE_SOLVING
150  * - \ref SCIP_STAGE_SOLVED
151  * - \ref SCIP_STAGE_EXITSOLVE
152  * - \ref SCIP_STAGE_FREETRANS
153  *
154  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
155  */
157  SCIP* scip, /**< SCIP data structure */
158  SCIP_EXPRTREE* tree /**< expression tree */
159  )
160 {
161  assert(scip != NULL);
162  assert(tree != NULL);
163 
164  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExprtreeTransformedVars", FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
165 
166  if( SCIPexprtreeGetNVars(tree) == 0 )
167  return SCIP_OKAY;
168 
170 
171  return SCIP_OKAY;
172 }
173 
174 /** evaluates an expression tree for a primal solution or LP solution
175  *
176  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
177  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
178  *
179  * @pre This method can be called if @p scip is in one of the following stages:
180  * - \ref SCIP_STAGE_PROBLEM
181  * - \ref SCIP_STAGE_TRANSFORMING
182  * - \ref SCIP_STAGE_TRANSFORMED
183  * - \ref SCIP_STAGE_INITPRESOLVE
184  * - \ref SCIP_STAGE_PRESOLVING
185  * - \ref SCIP_STAGE_EXITPRESOLVE
186  * - \ref SCIP_STAGE_PRESOLVED
187  * - \ref SCIP_STAGE_INITSOLVE
188  * - \ref SCIP_STAGE_SOLVING
189  * - \ref SCIP_STAGE_SOLVED
190  * - \ref SCIP_STAGE_EXITSOLVE
191  * - \ref SCIP_STAGE_FREETRANS
192  *
193  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
194  */
196  SCIP* scip, /**< SCIP data structure */
197  SCIP_EXPRTREE* tree, /**< expression tree */
198  SCIP_SOL* sol, /**< a solution, or NULL for current LP solution */
199  SCIP_Real* val /**< buffer to store value */
200  )
201 {
202  SCIP_Real* varvals;
203  int nvars;
204 
205  assert(scip != NULL);
206  assert(tree != NULL);
207  assert(val != NULL);
208 
209  SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeSol", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
210 
211  nvars = SCIPexprtreeGetNVars(tree);
212 
213  if( nvars == 0 )
214  {
215  SCIP_CALL( SCIPexprtreeEval(tree, NULL, val) );
216  return SCIP_OKAY;
217  }
218 
219  SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
220  SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, SCIPexprtreeGetVars(tree), varvals) );
221 
222  SCIP_CALL( SCIPexprtreeEval(tree, varvals, val) );
223 
224  SCIPfreeBufferArray(scip, &varvals);
225 
226  return SCIP_OKAY;
227 }
228 
229 /** evaluates an expression tree w.r.t. current global bounds
230  *
231  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
232  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
233  *
234  * @pre This method can be called if @p scip is in one of the following stages:
235  * - \ref SCIP_STAGE_PROBLEM
236  * - \ref SCIP_STAGE_TRANSFORMING
237  * - \ref SCIP_STAGE_TRANSFORMED
238  * - \ref SCIP_STAGE_INITPRESOLVE
239  * - \ref SCIP_STAGE_PRESOLVING
240  * - \ref SCIP_STAGE_EXITPRESOLVE
241  * - \ref SCIP_STAGE_PRESOLVED
242  * - \ref SCIP_STAGE_INITSOLVE
243  * - \ref SCIP_STAGE_SOLVING
244  * - \ref SCIP_STAGE_SOLVED
245  * - \ref SCIP_STAGE_EXITSOLVE
246  * - \ref SCIP_STAGE_FREETRANS
247  *
248  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
249  */
251  SCIP* scip, /**< SCIP data structure */
252  SCIP_EXPRTREE* tree, /**< expression tree */
253  SCIP_Real infinity, /**< value to use for infinity */
254  SCIP_INTERVAL* val /**< buffer to store result */
255  )
256 {
257  SCIP_INTERVAL* varvals;
258  SCIP_VAR** vars;
259  int nvars;
260  int i;
261 
262  assert(scip != NULL);
263  assert(tree != NULL);
264  assert(val != NULL);
265 
266  SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeGlobalBounds", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
267 
268  nvars = SCIPexprtreeGetNVars(tree);
269 
270  if( nvars == 0 )
271  {
272  SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, NULL, val) );
273  return SCIP_OKAY;
274  }
275 
276  vars = SCIPexprtreeGetVars(tree);
277  assert(vars != NULL);
278 
279  SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
280  for( i = 0; i < nvars; ++i )
281  {
282  SCIPintervalSetBounds(&varvals[i],
283  -infty2infty(SCIPinfinity(scip), infinity, -SCIPvarGetLbGlobal(vars[i])), /*lint !e666*/
284  infty2infty(SCIPinfinity(scip), infinity, SCIPvarGetUbGlobal(vars[i]))); /*lint !e666*/
285  }
286 
287  SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, varvals, val) );
288 
289  SCIPfreeBufferArray(scip, &varvals);
290 
291  return SCIP_OKAY;
292 }
293 
294 /** evaluates an expression tree w.r.t. current local bounds
295  *
296  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
297  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
298  *
299  * @pre This method can be called if @p scip is in one of the following stages:
300  * - \ref SCIP_STAGE_PROBLEM
301  * - \ref SCIP_STAGE_TRANSFORMING
302  * - \ref SCIP_STAGE_TRANSFORMED
303  * - \ref SCIP_STAGE_INITPRESOLVE
304  * - \ref SCIP_STAGE_PRESOLVING
305  * - \ref SCIP_STAGE_EXITPRESOLVE
306  * - \ref SCIP_STAGE_PRESOLVED
307  * - \ref SCIP_STAGE_INITSOLVE
308  * - \ref SCIP_STAGE_SOLVING
309  * - \ref SCIP_STAGE_SOLVED
310  * - \ref SCIP_STAGE_EXITSOLVE
311  * - \ref SCIP_STAGE_FREETRANS
312  *
313  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
314  */
316  SCIP* scip, /**< SCIP data structure */
317  SCIP_EXPRTREE* tree, /**< expression tree */
318  SCIP_Real infinity, /**< value to use for infinity */
319  SCIP_INTERVAL* val /**< buffer to store result */
320  )
321 {
322  SCIP_INTERVAL* varvals;
323  SCIP_VAR** vars;
324  int nvars;
325  int i;
326 
327  assert(scip != NULL);
328  assert(tree != NULL);
329  assert(val != NULL);
330 
331  SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeLocalBounds", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
332 
333  nvars = SCIPexprtreeGetNVars(tree);
334 
335  if( nvars == 0 )
336  {
337  SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, NULL, val) );
338  return SCIP_OKAY;
339  }
340 
341  vars = SCIPexprtreeGetVars(tree);
342  assert(vars != NULL);
343 
344  SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
345  for( i = 0; i < nvars; ++i )
346  {
347  /* due to numerics, the lower bound on a variable in SCIP can be slightly higher than the upper bound
348  * in this case, we take the most conservative way and switch the bounds
349  * further, we translate SCIP's value for infinity to the users value for infinity
350  */
351  SCIPintervalSetBounds(&varvals[i],
352  -infty2infty(SCIPinfinity(scip), infinity, -MIN(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i]))), /*lint !e666*/
353  infty2infty(SCIPinfinity(scip), infinity, MAX(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])))); /*lint !e666*/
354  }
355 
356  SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, varvals, val) );
357 
358  SCIPfreeBufferArray(scip, &varvals);
359 
360  return SCIP_OKAY;
361 }
362 
363 #undef infty2infty
internal methods for separators
#define NULL
Definition: def.h:239
internal methods for managing events
default message handler
trivialnegation primal heuristic
internal methods for storing primal CIP solutions
SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
Definition: expr.c:8739
methods to interpret (evaluate) an expression tree "fast"
internal methods for branch and bound tree
public methods for memory management
#define infinity
Definition: gastrans.c:71
methods for implications, variable bounds, and cliques
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
internal methods for clocks and timing issues
SCIP_RETCODE SCIPevalExprtreeGlobalBounds(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *val)
Definition: scip_expr.c:250
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17399
internal methods for NLPI solver interfaces
interface methods for specific LP solvers
internal methods for displaying statistics tables
#define FALSE
Definition: def.h:65
methods for the aggregation rows
internal methods for Benders&#39; decomposition
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
methods commonly used by primal heuristics
internal methods for branching rules and branching candidate storage
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
datastructures for concurrent solvers
public methods for problem variables
SCIP_RETCODE SCIPevalExprtreeSol(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_SOL *sol, SCIP_Real *val)
Definition: scip_expr.c:195
internal methods for handling parameter settings
methods for creating output for visualization tools (VBC, BAK)
nodereopt branching rule
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
public methods for SCIP variables
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
internal methods for LP management
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:102
internal methods for branching and inference history
public methods for numerical tolerances
internal methods for collecting primal CIP solutions and primal informations
internal methods for propagators
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
git hash methods
internal methods for storing and manipulating the main problem
methods for block memory pools and memory buffers
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1447
register additional core functionality that is designed as plugins
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:1933
public methods for expression handlers
internal methods for presolvers
internal methods for NLP management
internal miscellaneous methods
SCIP_RETCODE SCIPgetExprtreeTransformedVars(SCIP *scip, SCIP_EXPRTREE *tree)
Definition: scip_expr.c:156
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8612
internal methods for node selectors and node priority queues
internal methods for variable pricers
internal methods for global SCIP settings
internal methods for storing conflicts
#define SCIP_CALL(x)
Definition: def.h:351
SCIP main data structure.
internal methods for storing priced variables
internal methods for relaxators
internal methods for storing separated cuts
public methods for NLP management
methods commonly used for presolving
methods for catching the user CTRL-C interrupt
internal methods for problem variables
data structures and methods for collecting reoptimization information
the function declarations for the synchronization store
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
internal methods for user interface dialog
#define infty2infty(infty1, infty2, val)
Definition: scip_expr.c:134
internal methods for input file readers
#define MIN(x, y)
Definition: def.h:209
methods for debugging
reoptsols primal heuristic
internal methods for storing cuts in a cut pool
Constraint handler for linear constraints in their most general form, .
helper functions for concurrent scip solvers
internal methods for return codes for SCIP methods
#define MAX(x, y)
Definition: def.h:208
public methods for solutions
internal methods for conflict analysis
internal methods for tree compressions
internal methods for main solving loop and node processing
public methods for message output
default user interface dialog
#define SCIP_Real
Definition: def.h:150
internal methods for problem statistics
internal methods for constraints and constraint handlers
declarations for XML parsing
build flags methods
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
common defines and data types used in all packages of SCIP
internal methods for primal heuristics
internal methods for Benders&#39; decomposition cuts
SCIP_RETCODE SCIPevalExprtreeLocalBounds(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *val)
Definition: scip_expr.c:315
SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
Definition: expr.c:8723
internal methods for displaying runtime statistics
OFINS - Objective Function Induced Neighborhood Search - a primal heuristic for reoptimization.