Scippy

SCIP

Solving Constraint Integer Programs

sol.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 sol.h
17  * @brief internal methods for storing primal CIP solutions
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_SOL_H__
24 #define __SCIP_SOL_H__
25 
26 
27 #include <stdio.h>
28 
29 #include "scip/def.h"
30 #include "blockmemshell/memory.h"
31 #include "scip/type_retcode.h"
32 #include "scip/type_set.h"
33 #include "scip/type_stat.h"
34 #include "scip/type_lp.h"
35 #include "scip/type_nlp.h"
36 #include "scip/type_var.h"
37 #include "scip/type_prob.h"
38 #include "scip/type_sol.h"
39 #include "scip/type_primal.h"
40 #include "scip/type_tree.h"
41 #include "scip/type_heur.h"
42 #include "scip/pub_sol.h"
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 /** creates primal CIP solution, initialized to zero */
49 extern
50 SCIP_RETCODE SCIPsolCreate(
51  SCIP_SOL** sol, /**< pointer to primal CIP solution */
52  BMS_BLKMEM* blkmem, /**< block memory */
53  SCIP_SET* set, /**< global SCIP settings */
54  SCIP_STAT* stat, /**< problem statistics data */
55  SCIP_PRIMAL* primal, /**< primal data */
56  SCIP_TREE* tree, /**< branch and bound tree, or NULL */
57  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
58  );
59 
60 /** creates primal CIP solution in original problem space, initialized to the offset in the original problem */
61 extern
62 SCIP_RETCODE SCIPsolCreateOriginal(
63  SCIP_SOL** sol, /**< pointer to primal CIP solution */
64  BMS_BLKMEM* blkmem, /**< block memory */
65  SCIP_SET* set, /**< global SCIP settings */
66  SCIP_STAT* stat, /**< problem statistics data */
67  SCIP_PROB* origprob, /**< original problem data */
68  SCIP_PRIMAL* primal, /**< primal data */
69  SCIP_TREE* tree, /**< branch and bound tree */
70  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
71  );
72 
73 /** creates a copy of a primal CIP solution */
74 extern
75 SCIP_RETCODE SCIPsolCopy(
76  SCIP_SOL** sol, /**< pointer to store the copy of the primal CIP solution */
77  BMS_BLKMEM* blkmem, /**< block memory */
78  SCIP_SET* set, /**< global SCIP settings */
79  SCIP_STAT* stat, /**< problem statistics data */
80  SCIP_PRIMAL* primal, /**< primal data */
81  SCIP_SOL* sourcesol /**< primal CIP solution to copy */
82  );
83 
84 /** transformes given original solution to the transformed space; a corresponding transformed solution has to be given
85  * which is copied into the existing solution and freed afterwards
86  */
87 extern
88 SCIP_RETCODE SCIPsolTransform(
89  SCIP_SOL* sol, /**< primal CIP solution to change, living in original space */
90  SCIP_SOL** transsol, /**< pointer to corresponding transformed primal CIP solution */
91  BMS_BLKMEM* blkmem, /**< block memory */
92  SCIP_SET* set, /**< global SCIP settings */
93  SCIP_PRIMAL* primal /**< primal data */
94  );
95 
96 /** adjusts solution values of implicit integer variables in handed solution. Solution objective value is not
97  * deteriorated by this method.
98  */
99 extern
100 SCIP_RETCODE SCIPsolAdjustImplicitSolVals(
101  SCIP_SOL* sol, /**< primal CIP solution */
102  SCIP_SET* set, /**< global SCIP settings */
103  SCIP_STAT* stat, /**< problem statistics data */
104  SCIP_PROB* prob, /**< either original or transformed problem, depending on sol origin */
105  SCIP_TREE* tree, /**< branch and bound tree */
106  SCIP_Bool uselprows /**< should LP row information be considered for none-objective variables */
107  );
108 
109 /** creates primal CIP solution, initialized to the current LP solution */
110 extern
111 SCIP_RETCODE SCIPsolCreateLPSol(
112  SCIP_SOL** sol, /**< pointer to primal CIP solution */
113  BMS_BLKMEM* blkmem, /**< block memory */
114  SCIP_SET* set, /**< global SCIP settings */
115  SCIP_STAT* stat, /**< problem statistics data */
116  SCIP_PROB* prob, /**< transformed problem data */
117  SCIP_PRIMAL* primal, /**< primal data */
118  SCIP_TREE* tree, /**< branch and bound tree */
119  SCIP_LP* lp, /**< current LP data */
120  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
121  );
122 
123 /** creates primal CIP solution, initialized to the current NLP solution */
124 extern
125 SCIP_RETCODE SCIPsolCreateNLPSol(
126  SCIP_SOL** sol, /**< pointer to primal CIP solution */
127  BMS_BLKMEM* blkmem, /**< block memory */
128  SCIP_SET* set, /**< global SCIP settings */
129  SCIP_STAT* stat, /**< problem statistics data */
130  SCIP_PRIMAL* primal, /**< primal data */
131  SCIP_TREE* tree, /**< branch and bound tree */
132  SCIP_NLP* nlp, /**< current NLP data */
133  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
134  );
135 
136 /** creates primal CIP solution, initialized to the current relaxation solution */
137 extern
138 SCIP_RETCODE SCIPsolCreateRelaxSol(
139  SCIP_SOL** sol, /**< pointer to primal CIP solution */
140  BMS_BLKMEM* blkmem, /**< block memory */
141  SCIP_SET* set, /**< global SCIP settings */
142  SCIP_STAT* stat, /**< problem statistics data */
143  SCIP_PRIMAL* primal, /**< primal data */
144  SCIP_TREE* tree, /**< branch and bound tree */
145  SCIP_RELAXATION* relaxation, /**< global relaxation data */
146  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
147  );
148 
149 /** creates primal CIP solution, initialized to the current pseudo solution */
150 extern
151 SCIP_RETCODE SCIPsolCreatePseudoSol(
152  SCIP_SOL** sol, /**< pointer to primal CIP solution */
153  BMS_BLKMEM* blkmem, /**< block memory */
154  SCIP_SET* set, /**< global SCIP settings */
155  SCIP_STAT* stat, /**< problem statistics data */
156  SCIP_PROB* prob, /**< transformed problem data */
157  SCIP_PRIMAL* primal, /**< primal data */
158  SCIP_TREE* tree, /**< branch and bound tree, or NULL */
159  SCIP_LP* lp, /**< current LP data */
160  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
161  );
162 
163 /** creates primal CIP solution, initialized to the current solution */
164 extern
165 SCIP_RETCODE SCIPsolCreateCurrentSol(
166  SCIP_SOL** sol, /**< pointer to primal CIP solution */
167  BMS_BLKMEM* blkmem, /**< block memory */
168  SCIP_SET* set, /**< global SCIP settings */
169  SCIP_STAT* stat, /**< problem statistics data */
170  SCIP_PROB* prob, /**< transformed problem data */
171  SCIP_PRIMAL* primal, /**< primal data */
172  SCIP_TREE* tree, /**< branch and bound tree */
173  SCIP_LP* lp, /**< current LP data */
174  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
175  );
176 
177 /** creates primal CIP solution, initialized to unknown values */
178 extern
179 SCIP_RETCODE SCIPsolCreateUnknown(
180  SCIP_SOL** sol, /**< pointer to primal CIP solution */
181  BMS_BLKMEM* blkmem, /**< block memory */
182  SCIP_SET* set, /**< global SCIP settings */
183  SCIP_STAT* stat, /**< problem statistics data */
184  SCIP_PRIMAL* primal, /**< primal data */
185  SCIP_TREE* tree, /**< branch and bound tree */
186  SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */
187  );
188 
189 /** frees primal CIP solution */
190 extern
191 SCIP_RETCODE SCIPsolFree(
192  SCIP_SOL** sol, /**< pointer to primal CIP solution */
193  BMS_BLKMEM* blkmem, /**< block memory */
194  SCIP_PRIMAL* primal /**< primal data */
195  );
196 
197 /** copies current LP solution into CIP solution by linking */
198 extern
199 SCIP_RETCODE SCIPsolLinkLPSol(
200  SCIP_SOL* sol, /**< primal CIP solution */
201  SCIP_SET* set, /**< global SCIP settings */
202  SCIP_STAT* stat, /**< problem statistics data */
203  SCIP_PROB* prob, /**< transformed problem data */
204  SCIP_TREE* tree, /**< branch and bound tree */
205  SCIP_LP* lp /**< current LP data */
206  );
207 
208 /** copies current NLP solution into CIP solution by linking */
209 extern
210 SCIP_RETCODE SCIPsolLinkNLPSol(
211  SCIP_SOL* sol, /**< primal CIP solution */
212  SCIP_STAT* stat, /**< problem statistics data */
213  SCIP_TREE* tree, /**< branch and bound tree */
214  SCIP_NLP* nlp /**< current NLP data */
215  );
216 
217 /** copies current relaxation solution into CIP solution by linking */
218 extern
219 SCIP_RETCODE SCIPsolLinkRelaxSol(
220  SCIP_SOL* sol, /**< primal CIP solution */
221  SCIP_SET* set, /**< global SCIP settings */
222  SCIP_STAT* stat, /**< problem statistics data */
223  SCIP_TREE* tree, /**< branch and bound tree */
224  SCIP_RELAXATION* relaxation /**< global relaxation data */
225  );
226 
227 /** copies current pseudo solution into CIP solution by linking */
228 extern
229 SCIP_RETCODE SCIPsolLinkPseudoSol(
230  SCIP_SOL* sol, /**< primal CIP solution */
231  SCIP_SET* set, /**< global SCIP settings */
232  SCIP_STAT* stat, /**< problem statistics data */
233  SCIP_PROB* prob, /**< transformed problem data */
234  SCIP_TREE* tree, /**< branch and bound tree, or NULL */
235  SCIP_LP* lp /**< current LP data */
236  );
237 
238 /** copies current solution (LP or pseudo solution) into CIP solution by linking */
239 extern
240 SCIP_RETCODE SCIPsolLinkCurrentSol(
241  SCIP_SOL* sol, /**< primal CIP solution */
242  SCIP_SET* set, /**< global SCIP settings */
243  SCIP_STAT* stat, /**< problem statistics data */
244  SCIP_PROB* prob, /**< transformed problem data */
245  SCIP_TREE* tree, /**< branch and bound tree */
246  SCIP_LP* lp /**< current LP data */
247  );
248 
249 /** clears primal CIP solution */
250 extern
251 SCIP_RETCODE SCIPsolClear(
252  SCIP_SOL* sol, /**< primal CIP solution */
253  SCIP_STAT* stat, /**< problem statistics data */
254  SCIP_TREE* tree /**< branch and bound tree */
255  );
256 
257 /** declares all entries in the primal CIP solution to be unknown */
258 extern
259 SCIP_RETCODE SCIPsolSetUnknown(
260  SCIP_SOL* sol, /**< primal CIP solution */
261  SCIP_STAT* stat, /**< problem statistics data */
262  SCIP_TREE* tree /**< branch and bound tree */
263  );
264 
265 /** stores solution values of variables in solution's own array */
266 extern
267 SCIP_RETCODE SCIPsolUnlink(
268  SCIP_SOL* sol, /**< primal CIP solution */
269  SCIP_SET* set, /**< global SCIP settings */
270  SCIP_PROB* prob /**< transformed problem data */
271  );
272 
273 /** sets value of variable in primal CIP solution */
274 extern
275 SCIP_RETCODE SCIPsolSetVal(
276  SCIP_SOL* sol, /**< primal CIP solution */
277  SCIP_SET* set, /**< global SCIP settings */
278  SCIP_STAT* stat, /**< problem statistics data */
279  SCIP_TREE* tree, /**< branch and bound tree */
280  SCIP_VAR* var, /**< variable to add to solution */
281  SCIP_Real val /**< solution value of variable */
282  );
283 
284 /** increases value of variable in primal CIP solution */
285 extern
286 SCIP_RETCODE SCIPsolIncVal(
287  SCIP_SOL* sol, /**< primal CIP solution */
288  SCIP_SET* set, /**< global SCIP settings */
289  SCIP_STAT* stat, /**< problem statistics data */
290  SCIP_TREE* tree, /**< branch and bound tree */
291  SCIP_VAR* var, /**< variable to increase solution value for */
292  SCIP_Real incval /**< increment for solution value of variable */
293  );
294 
295 /** returns value of variable in primal CIP solution */
296 extern
297 SCIP_Real SCIPsolGetVal(
298  SCIP_SOL* sol, /**< primal CIP solution */
299  SCIP_SET* set, /**< global SCIP settings */
300  SCIP_STAT* stat, /**< problem statistics data */
301  SCIP_VAR* var /**< variable to get value for */
302  );
303 
304 /** returns value of variable in primal ray represented by primal CIP solution */
305 extern
306 SCIP_Real SCIPsolGetRayVal(
307  SCIP_SOL* sol, /**< primal CIP solution, representing a primal ray */
308  SCIP_SET* set, /**< global SCIP settings */
309  SCIP_STAT* stat, /**< problem statistics data */
310  SCIP_VAR* var /**< variable to get value for */
311  );
312 
313 
314 /** gets objective value of primal CIP solution in transformed problem */
315 extern
316 SCIP_Real SCIPsolGetObj(
317  SCIP_SOL* sol, /**< primal CIP solution */
318  SCIP_SET* set, /**< global SCIP settings */
319  SCIP_PROB* transprob, /**< tranformed problem data */
320  SCIP_PROB* origprob /**< original problem data */
321  );
322 
323 /** updates primal solutions after a change in a variable's objective value */
324 extern
325 void SCIPsolUpdateVarObj(
326  SCIP_SOL* sol, /**< primal CIP solution */
327  SCIP_VAR* var, /**< problem variable */
328  SCIP_Real oldobj, /**< old objective value */
329  SCIP_Real newobj /**< new objective value */
330  );
331 
332 /** checks primal CIP solution for feasibility */
333 extern
334 SCIP_RETCODE SCIPsolCheck(
335  SCIP_SOL* sol, /**< primal CIP solution */
336  SCIP_SET* set, /**< global SCIP settings */
337  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
338  BMS_BLKMEM* blkmem, /**< block memory */
339  SCIP_STAT* stat, /**< problem statistics */
340  SCIP_PROB* prob, /**< transformed problem data */
341  SCIP_Bool printreason, /**< should all reasons of violations be printed? */
342  SCIP_Bool checkbounds, /**< should the bounds of the variables be checked? */
343  SCIP_Bool checkintegrality, /**< has integrality to be checked? */
344  SCIP_Bool checklprows, /**< have current LP rows to be checked? */
345  SCIP_Bool* feasible /**< stores whether solution is feasible */
346  );
347 
348 /** try to round given solution */
349 extern
350 SCIP_RETCODE SCIPsolRound(
351  SCIP_SOL* sol, /**< primal solution */
352  SCIP_SET* set, /**< global SCIP settings */
353  SCIP_STAT* stat, /**< problem statistics data */
354  SCIP_PROB* prob, /**< transformed problem data */
355  SCIP_TREE* tree, /**< branch and bound tree */
356  SCIP_Bool* success /**< pointer to store whether rounding was successful */
357  );
358 
359 /** updates the solution value sums in variables by adding the value in the given solution */
360 extern
361 void SCIPsolUpdateVarsum(
362  SCIP_SOL* sol, /**< primal CIP solution */
363  SCIP_SET* set, /**< global SCIP settings */
364  SCIP_STAT* stat, /**< problem statistics data */
365  SCIP_PROB* prob, /**< transformed problem data */
366  SCIP_Real weight /**< weight of solution in weighted average */
367  );
368 
369 /** retransforms solution to original problem space */
370 extern
371 SCIP_RETCODE SCIPsolRetransform(
372  SCIP_SOL* sol, /**< primal CIP solution */
373  SCIP_SET* set, /**< global SCIP settings */
374  SCIP_STAT* stat, /**< problem statistics data */
375  SCIP_PROB* origprob, /**< original problem */
376  SCIP_PROB* transprob, /**< transformed problem */
377  SCIP_Bool* hasinfval /**< pointer to store whether the solution has infinite values */
378  );
379 
380 /** recomputes the objective value of an original solution, e.g., when transferring solutions
381  * from the solution pool (objective coefficients might have changed in the meantime)
382  */
383 extern
384 void SCIPsolRecomputeObj(
385  SCIP_SOL* sol, /**< primal CIP solution */
386  SCIP_SET* set, /**< global SCIP settings */
387  SCIP_STAT* stat, /**< problem statistics data */
388  SCIP_PROB* origprob /**< original problem */
389  );
390 
391 
392 /** returns whether the given solutions in transformed space are equal */
393 extern
394 SCIP_Bool SCIPsolsAreEqual(
395  SCIP_SOL* sol1, /**< first primal CIP solution */
396  SCIP_SOL* sol2, /**< second primal CIP solution */
397  SCIP_SET* set, /**< global SCIP settings */
398  SCIP_STAT* stat, /**< problem statistics data */
399  SCIP_PROB* origprob, /**< original problem */
400  SCIP_PROB* transprob /**< transformed problem after presolve */
401  );
402 
403 /** outputs non-zero elements of solution to file stream */
404 extern
405 SCIP_RETCODE SCIPsolPrint(
406  SCIP_SOL* sol, /**< primal CIP solution */
407  SCIP_SET* set, /**< global SCIP settings */
408  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
409  SCIP_STAT* stat, /**< problem statistics data */
410  SCIP_PROB* prob, /**< problem data (original or transformed) */
411  SCIP_PROB* transprob, /**< transformed problem data or NULL (to display priced variables) */
412  FILE* file, /**< output file (or NULL for standard output) */
413  SCIP_Bool printzeros /**< should variables set to zero be printed? */
414  );
415 
416 /** outputs non-zero elements of solution representing a ray to file stream */
417 extern
418 SCIP_RETCODE SCIPsolPrintRay(
419  SCIP_SOL* sol, /**< primal CIP solution */
420  SCIP_SET* set, /**< global SCIP settings */
421  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
422  SCIP_STAT* stat, /**< problem statistics data */
423  SCIP_PROB* prob, /**< problem data (original or transformed) */
424  SCIP_PROB* transprob, /**< transformed problem data or NULL (to display priced variables) */
425  FILE* file, /**< output file (or NULL for standard output) */
426  SCIP_Bool printzeros /**< should variables set to zero be printed? */
427  );
428 
429 
430 
431 /* In debug mode, the following methods are implemented as function calls to ensure
432  * type validity.
433  */
434 
435 /** adds value to the objective value of a given original primal CIP solution */
436 extern
437 void SCIPsolOrigAddObjval(
438  SCIP_SOL* sol, /**< primal CIP solution */
439  SCIP_Real addval /**< offset value to add */
440  );
441 
442 /** gets current position of solution in array of existing solutions of primal data */
443 extern
444 int SCIPsolGetPrimalIndex(
445  SCIP_SOL* sol /**< primal CIP solution */
446  );
447 
448 /** sets current position of solution in array of existing solutions of primal data */
449 extern
450 void SCIPsolSetPrimalIndex(
451  SCIP_SOL* sol, /**< primal CIP solution */
452  int primalindex /**< new primal index of solution */
453  );
454 
455 #ifdef NDEBUG
456 
457 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
458  * speed up the algorithms.
459  */
460 
461 #define SCIPsolOrigAddObjval(sol, addval) ((sol)->obj += (addval))
462 #define SCIPsolGetPrimalIndex(sol) ((sol)->primalindex)
463 #define SCIPsolSetPrimalIndex(sol,idx) { (sol)->primalindex = idx; }
464 
465 #endif
466 
467 #ifdef __cplusplus
468 }
469 #endif
470 
471 #endif
472