Scippy

SCIP

Solving Constraint Integer Programs

prob.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 prob.h
17  * @brief internal methods for storing and manipulating the main problem
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_PROB_H__
24 #define __SCIP_PROB_H__
25 
26 
27 #include "scip/def.h"
28 #include "blockmemshell/memory.h"
29 #include "scip/type_retcode.h"
30 #include "scip/type_set.h"
31 #include "scip/type_stat.h"
32 #include "scip/type_event.h"
33 #include "scip/type_lp.h"
34 #include "scip/type_var.h"
35 #include "scip/type_implics.h"
36 #include "scip/type_prob.h"
37 #include "scip/type_primal.h"
38 #include "scip/type_tree.h"
39 #include "scip/type_branch.h"
40 #include "scip/type_cons.h"
41 
42 #include "scip/struct_prob.h"
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 /*
49  * problem creation
50  */
51 
52 /** creates problem data structure by copying the source problem;
53  * If the problem type requires the use of variable pricers, these pricers should be activated with calls
54  * to SCIPactivatePricer(). These pricers are automatically deactivated, when the problem is freed.
55  */
57  SCIP_PROB** prob, /**< pointer to problem data structure */
58  BMS_BLKMEM* blkmem, /**< block memory */
59  SCIP_SET* set, /**< global SCIP settings */
60  const char* name, /**< problem name */
61  SCIP* sourcescip, /**< source SCIP data structure */
62  SCIP_PROB* sourceprob, /**< source problem structure */
63  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
64  * target variables, or NULL */
65  SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
66  * target constraints, or NULL */
67  SCIP_Bool global /**< create a global or a local copy? */
68  );
69 
70 /** creates problem data structure
71  * If the problem type requires the use of variable pricers, these pricers should be activated with calls
72  * to SCIPactivatePricer(). These pricers are automatically deactivated, when the problem is freed.
73  */
74 extern
76  SCIP_PROB** prob, /**< pointer to problem data structure */
77  BMS_BLKMEM* blkmem, /**< block memory */
78  SCIP_SET* set, /**< global SCIP settings */
79  const char* name, /**< problem name */
80  SCIP_DECL_PROBDELORIG ((*probdelorig)), /**< frees user data of original problem */
81  SCIP_DECL_PROBTRANS ((*probtrans)), /**< creates user data of transformed problem by transforming original user data */
82  SCIP_DECL_PROBDELTRANS((*probdeltrans)), /**< frees user data of transformed problem */
83  SCIP_DECL_PROBINITSOL ((*probinitsol)), /**< solving process initialization method of transformed data */
84  SCIP_DECL_PROBEXITSOL ((*probexitsol)), /**< solving process deinitialization method of transformed data */
85  SCIP_DECL_PROBCOPY ((*probcopy)), /**< copies user data if you want to copy it to a subscip, or NULL */
86  SCIP_PROBDATA* probdata, /**< user problem data set by the reader */
87  SCIP_Bool transformed /**< is this the transformed problem? */
88  );
89 
90 /** sets callback to free user data of original problem */
91 extern
93  SCIP_PROB* prob, /**< problem */
94  SCIP_DECL_PROBDELORIG ((*probdelorig)) /**< frees user data of original problem */
95  );
96 
97 /** sets callback to create user data of transformed problem by transforming original user data */
98 extern
99 void SCIPprobSetTrans(
100  SCIP_PROB* prob, /**< problem */
101  SCIP_DECL_PROBTRANS ((*probtrans)) /**< creates user data of transformed problem by transforming original user data */
102  );
103 
104 /** sets callback to free user data of transformed problem */
105 extern
107  SCIP_PROB* prob, /**< problem */
108  SCIP_DECL_PROBDELTRANS((*probdeltrans)) /**< frees user data of transformed problem */
109  );
110 
111 /** sets solving process initialization callback of transformed data */
112 extern
113 void SCIPprobSetInitsol(
114  SCIP_PROB* prob, /**< problem */
115  SCIP_DECL_PROBINITSOL ((*probinitsol)) /**< solving process initialization callback of transformed data */
116  );
117 
118 /** sets solving process deinitialization callback of transformed data */
119 extern
120 void SCIPprobSetExitsol(
121  SCIP_PROB* prob, /**< problem */
122  SCIP_DECL_PROBEXITSOL ((*probexitsol)) /**< solving process deinitialization callback of transformed data */
123  );
124 
125 /** sets callback to copy user data to copy it to a subscip, or NULL */
126 extern
127 void SCIPprobSetCopy(
128  SCIP_PROB* prob, /**< problem */
129  SCIP_DECL_PROBCOPY ((*probcopy)) /**< copies user data if you want to copy it to a subscip, or NULL */
130  );
131 
132 /** frees problem data structure */
133 extern
135  SCIP_PROB** prob, /**< pointer to problem data structure */
136  BMS_BLKMEM* blkmem, /**< block memory buffer */
137  SCIP_SET* set, /**< global SCIP settings */
138  SCIP_STAT* stat, /**< dynamic problem statistics */
139  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
140  SCIP_LP* lp /**< current LP data (or NULL, if it's the original problem) */
141  );
142 
143 /** transform problem data into normalized form */
144 extern
146  SCIP_PROB* source, /**< problem to transform */
147  BMS_BLKMEM* blkmem, /**< block memory buffer */
148  SCIP_SET* set, /**< global SCIP settings */
149  SCIP_STAT* stat, /**< problem statistics */
150  SCIP_PRIMAL* primal, /**< primal data */
151  SCIP_TREE* tree, /**< branch and bound tree */
152  SCIP_LP* lp, /**< current LP data */
153  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
154  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
155  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
156  SCIP_PROB** target /**< pointer to target problem data structure */
157  );
158 
159 /** resets the global and local bounds of original variables in original problem to their original values */
160 extern
162  SCIP_PROB* prob, /**< original problem data */
163  BMS_BLKMEM* blkmem, /**< block memory */
164  SCIP_SET* set, /**< global SCIP settings */
165  SCIP_STAT* stat /**< problem statistics */
166  );
167 
168 /** (Re)Sort the variables, which appear in the four categories (binary, integer, implicit, continuous) after presolve
169  * with respect to their original index (within their categories). Adjust the problem index afterwards which is
170  * supposed to reflect the position in the variable array. This additional (re)sorting is supposed to get more robust
171  * against the order presolving fixed variables. (We also reobtain a possible block structure induced by the user
172  * model)
173  */
174 extern
175 void SCIPprobResortVars(
176  SCIP_PROB* prob /**< problem data */
177  );
178 
179 
180 /*
181  * problem modification
182  */
183 
184 /** sets user problem data */
185 extern
186 void SCIPprobSetData(
187  SCIP_PROB* prob, /**< problem */
188  SCIP_PROBDATA* probdata /**< user problem data to use */
189  );
190 
191 /** adds variable's name to the namespace */
192 extern
194  SCIP_PROB* prob, /**< problem data */
195  SCIP_VAR* var /**< variable */
196  );
197 
198 /** removes variable's name from the namespace */
199 extern
201  SCIP_PROB* prob, /**< problem data */
202  SCIP_VAR* var /**< variable */
203  );
204 
205 /** adds variable to the problem and captures it */
206 extern
208  SCIP_PROB* prob, /**< problem data */
209  BMS_BLKMEM* blkmem, /**< block memory buffers */
210  SCIP_SET* set, /**< global SCIP settings */
211  SCIP_LP* lp, /**< current LP data */
212  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
213  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
214  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
215  SCIP_VAR* var /**< variable to add */
216  );
217 
218 /** marks variable to be removed from the problem; however, the variable is NOT removed from the constraints */
219 extern
221  SCIP_PROB* prob, /**< problem data */
222  BMS_BLKMEM* blkmem, /**< block memory */
223  SCIP_SET* set, /**< global SCIP settings */
224  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
225  SCIP_VAR* var, /**< problem variable */
226  SCIP_Bool* deleted /**< pointer to store whether marking variable to be deleted was successful */
227  );
228 
229 /** actually removes the deleted variables from the problem and releases them */
230 extern
232  SCIP_PROB* prob, /**< problem data */
233  BMS_BLKMEM* blkmem, /**< block memory */
234  SCIP_SET* set, /**< global SCIP settings */
235  SCIP_STAT* stat, /**< dynamic problem statistics */
236  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
237  SCIP_LP* lp, /**< current LP data (may be NULL) */
238  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
239  );
240 
241 /** changes the type of a variable in the problem */
242 extern
244  SCIP_PROB* prob, /**< problem data */
245  BMS_BLKMEM* blkmem, /**< block memory */
246  SCIP_SET* set, /**< global SCIP settings */
247  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
248  SCIP_VAR* var, /**< variable to add */
249  SCIP_VARTYPE vartype /**< new type of variable */
250  );
251 
252 /** informs problem, that the given loose problem variable changed its status */
253 extern
255  SCIP_PROB* prob, /**< problem data */
256  BMS_BLKMEM* blkmem, /**< block memory */
257  SCIP_SET* set, /**< global SCIP settings */
258  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
259  SCIP_VAR* var /**< problem variable */
260  );
261 
262 /** adds constraint's name to the namespace */
263 extern
265  SCIP_PROB* prob, /**< problem data */
266  SCIP_CONS* cons /**< constraint */
267  );
268 
269 /** remove constraint's name from the namespace */
270 extern
272  SCIP_PROB* prob, /**< problem data */
273  SCIP_CONS* cons /**< constraint */
274  );
275 
276 /** adds constraint to the problem and captures it;
277  * a local constraint is automatically upgraded into a global constraint
278  */
279 extern
281  SCIP_PROB* prob, /**< problem data */
282  SCIP_SET* set, /**< global SCIP settings */
283  SCIP_STAT* stat, /**< dynamic problem statistics */
284  SCIP_CONS* cons /**< constraint to add */
285  );
286 
287 /** releases and removes constraint from the problem; if the user has not captured the constraint for his own use, the
288  * constraint may be invalid after the call
289  */
290 extern
292  SCIP_PROB* prob, /**< problem data */
293  BMS_BLKMEM* blkmem, /**< block memory */
294  SCIP_SET* set, /**< global SCIP settings */
295  SCIP_STAT* stat, /**< dynamic problem statistics */
296  SCIP_CONS* cons /**< constraint to remove */
297  );
298 
299 /** remembers the current number of constraints in the problem's internal data structure
300  * - resets maximum number of constraints to current number of constraints
301  * - remembers current number of constraints as starting number of constraints
302  */
303 extern
304 void SCIPprobMarkNConss(
305  SCIP_PROB* prob /**< problem data */
306  );
307 
308 /** sets objective sense: minimization or maximization */
309 extern
311  SCIP_PROB* prob, /**< problem data */
312  SCIP_OBJSENSE objsense /**< new objective sense */
313  );
314 
315 /** adds value to objective offset */
316 extern
318  SCIP_PROB* prob, /**< problem data */
319  SCIP_Real addval /**< value to add to objective offset */
320  );
321 
322 /** sets the dual bound on objective function */
323 extern
325  SCIP_PROB* prob, /**< problem data */
326  SCIP_Real dualbound /**< external dual bound */
327  );
328 
329 /** sets limit on objective function, such that only solutions better than this limit are accepted */
330 extern
331 void SCIPprobSetObjlim(
332  SCIP_PROB* prob, /**< problem data */
333  SCIP_Real objlim /**< external objective limit */
334  );
335 
336 /** informs the problem, that its objective value is always integral in every feasible solution */
337 extern
339  SCIP_PROB* prob /**< problem data */
340  );
341 
342 /** sets integral objective value flag, if all variables with non-zero objective values are integral and have
343  * integral objective value and also updates the cutoff bound if primal solution is already known
344  */
345 extern
347  SCIP_PROB* transprob, /**< tranformed problem data */
348  SCIP_PROB* origprob, /**< original problem data */
349  BMS_BLKMEM* blkmem, /**< block memory */
350  SCIP_SET* set, /**< global SCIP settings */
351  SCIP_STAT* stat, /**< problem statistics data */
352  SCIP_PRIMAL* primal, /**< primal data */
353  SCIP_TREE* tree, /**< branch and bound tree */
354  SCIP_LP* lp, /**< current LP data */
355  SCIP_EVENTQUEUE* eventqueue /**< event queue */
356  );
357 
358 /** if possible, scales objective function such that it is integral with gcd = 1 */
359 extern
361  SCIP_PROB* transprob, /**< tranformed problem data */
362  SCIP_PROB* origprob, /**< original problem data */
363  BMS_BLKMEM* blkmem, /**< block memory */
364  SCIP_SET* set, /**< global SCIP settings */
365  SCIP_STAT* stat, /**< problem statistics data */
366  SCIP_PRIMAL* primal, /**< primal data */
367  SCIP_TREE* tree, /**< branch and bound tree */
368  SCIP_LP* lp, /**< current LP data */
369  SCIP_EVENTQUEUE* eventqueue /**< event queue */
370  );
371 
372 /** remembers the current solution as root solution in the problem variables */
373 extern
375  SCIP_PROB* prob, /**< problem data */
376  SCIP_SET* set, /**< global SCIP settings */
377  SCIP_LP* lp, /**< current LP data */
378  SCIP_Bool roothaslp /**< is the root solution from LP? */
379  );
380 
381 /** remembers the best solution w.r.t. root reduced cost propagation as root solution in the problem variables */
382 extern
384  SCIP_PROB* prob, /**< problem data */
385  SCIP_SET* set, /**< global SCIP settings */
386  SCIP_STAT* stat, /**< problem statistics */
387  SCIP_LP* lp /**< current LP data */
388  );
389 
390 /** informs problem, that the presolving process was finished, and updates all internal data structures */
391 extern
393  SCIP_PROB* prob, /**< problem data */
394  SCIP_SET* set /**< global SCIP settings */
395  );
396 
397 /** initializes problem for branch and bound process */
398 extern
400  SCIP_PROB* prob, /**< problem data */
401  SCIP_SET* set /**< global SCIP settings */
402  );
403 
404 /** deinitializes problem after branch and bound process, and converts all COLUMN variables back into LOOSE variables */
405 extern
407  SCIP_PROB* prob, /**< problem data */
408  BMS_BLKMEM* blkmem, /**< block memory */
409  SCIP_SET* set, /**< global SCIP settings */
410  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
411  SCIP_LP* lp, /**< current LP data */
412  SCIP_Bool restart /**< was this exit solve call triggered by a restart? */
413  );
414 
415 
416 
417 
418 /*
419  * problem information
420  */
421 
422 /** sets problem name */
423 extern
425  SCIP_PROB* prob, /**< problem data */
426  const char* name /**< name to be set */
427  );
428 
429 /** returns the number of implicit binary variables, meaning variable of vartype != SCIP_VARTYPE_BINARY and !=
430  * SCIP_VARTYPE_CONTINUOUS but with global bounds [0,1]
431  *
432  * @note this number needs to be computed, because it cannot be update like the othe counters for binary and interger
433  * variables, each time the variable type changes(, we would need to update this counter each time a global bound
434  * changes), even at the end of presolving this cannot be computed, because some variable can change to an
435  * implicit binary status
436  */
437 extern
439  SCIP_PROB* prob /**< problem data */
440  );
441 
442 /** returns the number of variables with non-zero objective coefficient */
443 extern
445  SCIP_PROB* prob, /**< problem data */
446  SCIP_SET* set /**< global SCIP settings */
447  );
448 
449 /** update the number of variables with non-zero objective coefficient */
450 extern
452  SCIP_PROB* prob, /**< problem data */
453  SCIP_SET* set, /**< global SCIP settings */
454  SCIP_Real oldobj, /**< old objective value for variable */
455  SCIP_Real newobj /**< new objective value for variable */
456  );
457 
458 /** update the dual bound if its better as the current one */
459 extern
461  SCIP_PROB* prob, /**< problem data */
462  SCIP_Real newbound /**< new dual bound for the node (if it's tighter than the old one) */
463  );
464 
465 /** returns the external value of the given internal objective value */
466 extern
468  SCIP_PROB* transprob, /**< tranformed problem data */
469  SCIP_PROB* origprob, /**< original problem data */
470  SCIP_SET* set, /**< global SCIP settings */
471  SCIP_Real objval /**< internal objective value */
472  );
473 
474 /** returns the internal value of the given external objective value */
475 extern
477  SCIP_PROB* transprob, /**< tranformed problem data */
478  SCIP_PROB* origprob, /**< original problem data */
479  SCIP_SET* set, /**< global SCIP settings */
480  SCIP_Real objval /**< external objective value */
481  );
482 
483 /** returns variable of the problem with given name */
484 extern
486  SCIP_PROB* prob, /**< problem data */
487  const char* name /**< name of variable to find */
488  );
489 
490 /** returns constraint of the problem with given name */
491 extern
493  SCIP_PROB* prob, /**< problem data */
494  const char* name /**< name of variable to find */
495  );
496 
497 /** displays current pseudo solution */
498 extern
500  SCIP_PROB* prob, /**< problem data */
501  SCIP_SET* set, /**< global SCIP settings */
502  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
503  );
504 
505 /** outputs problem statistics */
506 extern
508  SCIP_PROB* prob, /**< problem data */
509  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
510  FILE* file /**< output file (or NULL for standard output) */
511  );
512 
513 
514 #ifndef NDEBUG
515 
516 /* In debug mode, the following methods are implemented as function calls to ensure
517  * type validity.
518  */
519 
520 /** is the problem data transformed */
521 extern
523  SCIP_PROB* prob /**< problem data */
524  );
525 
526 /** returns whether the objective value is known to be integral in every feasible solution */
527 extern
529  SCIP_PROB* prob /**< problem data */
530  );
531 
532 /** returns TRUE iff all columns, i.e. every variable with non-empty column w.r.t. all ever created rows, are present
533  * in the LP, and FALSE, if there are additional already existing columns, that may be added to the LP in pricing
534  */
535 extern
537  SCIP_PROB* prob, /**< problem data */
538  SCIP_SET* set, /**< global SCIP settings */
539  SCIP_LP* lp /**< current LP data */
540  );
541 
542 /** gets limit on objective function in external space */
543 extern
545  SCIP_PROB* prob, /**< problem data */
546  SCIP_SET* set /**< global SCIP settings */
547  );
548 
549 /** gets user problem data */
550 extern
552  SCIP_PROB* prob /**< problem */
553  );
554 
555 /** gets problem name */
556 extern
557 const char* SCIPprobGetName(
558  SCIP_PROB* prob /**< problem data */
559  );
560 
561 /** gets number of problem variables */
562 extern
563 int SCIPprobGetNVars(
564  SCIP_PROB* prob /**< problem data */
565  );
566 
567 /** gets number of binary problem variables */
568 extern
570  SCIP_PROB* prob /**< problem data */
571  );
572 
573 /** gets number of integer problem variables */
574 extern
576  SCIP_PROB* prob /**< problem data */
577  );
578 
579 /** gets number of implicit integer problem variables */
580 extern
582  SCIP_PROB* prob /**< problem data */
583  );
584 
585 /** gets number of continuous problem variables */
586 extern
588  SCIP_PROB* prob /**< problem data */
589  );
590 
591 /** gets problem variables */
592 extern
594  SCIP_PROB* prob /**< problem data */
595  );
596 
597 /** gets the objective offset */
598 extern
600  SCIP_PROB* prob /**< problem data */
601  );
602 
603 /** gets the objective scalar */
604 extern
606  SCIP_PROB* prob /**< problem data */
607  );
608 
609 #else
610 
611 /* In optimized mode, the methods are implemented as defines to reduce the number of function calls and
612  * speed up the algorithms.
613  */
614 
615 #define SCIPprobIsTransformed(prob) ((prob)->transformed)
616 #define SCIPprobIsObjIntegral(prob) ((prob)->objisintegral)
617 #define SCIPprobAllColsInLP(prob,set,lp) (SCIPlpGetNCols(lp) == (prob)->ncolvars && (set)->nactivepricers == 0)
618 #define SCIPprobGetObjlim(prob,set) \
619  ((prob)->objlim >= SCIP_INVALID ? (SCIP_Real)((prob)->objsense) * SCIPsetInfinity(set) : (prob)->objlim)
620 #define SCIPprobGetData(prob) ((prob)->probdata)
621 #define SCIPprobGetName(prob) ((prob)->name)
622 #define SCIPprobGetName(prob) ((prob)->name)
623 #define SCIPprobGetNVars(prob) ((prob)->nvars)
624 #define SCIPprobGetNBinVars(prob) ((prob)->nbinvars)
625 #define SCIPprobGetNIntVars(prob) ((prob)->nintvars)
626 #define SCIPprobGetNImplVars(prob) ((prob)->nimplvars)
627 #define SCIPprobGetNContVars(prob) ((prob)->ncontvars)
628 #define SCIPprobGetVars(prob) ((prob)->vars)
629 #define SCIPprobGetObjoffset(prob) ((prob)->objoffset)
630 #define SCIPprobGetObjscale(prob) ((prob)->objscale)
631 #endif
632 
633 
634 #ifdef __cplusplus
635 }
636 #endif
637 
638 #endif
639