Scippy

SCIP

Solving Constraint Integer Programs

primal.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 primal.h
17  * @brief internal methods for collecting primal CIP solutions and primal informations
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_PRIMAL_H__
24 #define __SCIP_PRIMAL_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_event.h"
32 #include "scip/type_lp.h"
33 #include "scip/type_var.h"
34 #include "scip/type_prob.h"
35 #include "scip/type_sol.h"
36 #include "scip/type_primal.h"
37 #include "scip/type_tree.h"
38 #include "scip/type_heur.h"
39 
40 #include "scip/struct_primal.h"
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 /** creates primal data */
47 extern
48 SCIP_RETCODE SCIPprimalCreate(
49  SCIP_PRIMAL** primal /**< pointer to primal data */
50  );
51 
52 /** frees primal data */
53 extern
54 SCIP_RETCODE SCIPprimalFree(
55  SCIP_PRIMAL** primal, /**< pointer to primal data */
56  BMS_BLKMEM* blkmem /**< block memory */
57  );
58 
59 /** sets the cutoff bound in primal data and in LP solver */
60 extern
61 SCIP_RETCODE SCIPprimalSetCutoffbound(
62  SCIP_PRIMAL* primal, /**< primal data */
63  BMS_BLKMEM* blkmem, /**< block memory */
64  SCIP_SET* set, /**< global SCIP settings */
65  SCIP_STAT* stat, /**< problem statistics data */
66  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
67  SCIP_PROB* transprob, /**< tranformed problem data */
68  SCIP_PROB* origprob, /**< original problem data */
69  SCIP_TREE* tree, /**< branch and bound tree */
70  SCIP_LP* lp, /**< current LP data */
71  SCIP_Real cutoffbound, /**< new cutoff bound */
72  SCIP_Bool useforobjlimit /**< should the cutoff bound be used to update the objective limit, if
73  * better? */
74  );
75 
76 /** sets upper bound in primal data and in LP solver */
77 extern
78 SCIP_RETCODE SCIPprimalSetUpperbound(
79  SCIP_PRIMAL* primal, /**< primal data */
80  BMS_BLKMEM* blkmem, /**< block memory */
81  SCIP_SET* set, /**< global SCIP settings */
82  SCIP_STAT* stat, /**< problem statistics data */
83  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
84  SCIP_PROB* prob, /**< transformed problem after presolve */
85  SCIP_TREE* tree, /**< branch and bound tree */
86  SCIP_LP* lp, /**< current LP data */
87  SCIP_Real upperbound /**< new upper bound */
88  );
89 
90 /** updates upper bound and cutoff bound in primal data after a tightening of the problem's objective limit */
91 extern
92 SCIP_RETCODE SCIPprimalUpdateObjlimit(
93  SCIP_PRIMAL* primal, /**< primal data */
94  BMS_BLKMEM* blkmem, /**< block memory */
95  SCIP_SET* set, /**< global SCIP settings */
96  SCIP_STAT* stat, /**< problem statistics data */
97  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
98  SCIP_PROB* transprob, /**< tranformed problem data */
99  SCIP_PROB* origprob, /**< original problem data */
100  SCIP_TREE* tree, /**< branch and bound tree */
101  SCIP_LP* lp /**< current LP data */
102  );
103 
104 /** recalculates upper bound and cutoff bound in primal data after a change of the problem's objective offset */
105 extern
106 SCIP_RETCODE SCIPprimalUpdateObjoffset(
107  SCIP_PRIMAL* primal, /**< primal data */
108  BMS_BLKMEM* blkmem, /**< block memory */
109  SCIP_SET* set, /**< global SCIP settings */
110  SCIP_STAT* stat, /**< problem statistics data */
111  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
112  SCIP_PROB* transprob, /**< tranformed problem data */
113  SCIP_PROB* origprob, /**< original problem data */
114  SCIP_TREE* tree, /**< branch and bound tree */
115  SCIP_LP* lp /**< current LP data */
116  );
117 
118 /** adds additional objective offset in origanal space to all existing solution (in original space) */
119 extern
120 void SCIPprimalAddOrigObjoffset(
121  SCIP_PRIMAL* primal, /**< primal data */
122  SCIP_SET* set, /**< global SCIP settings */
123  SCIP_Real addval /**< additional objective offset in original space */
124  );
125 
126 /** returns whether the current primal bound is justified with a feasible primal solution; if not, the primal bound
127  * was set from the user as objective limit
128  */
129 extern
130 SCIP_Bool SCIPprimalUpperboundIsSol(
131  SCIP_PRIMAL* primal, /**< primal data */
132  SCIP_SET* set, /**< global SCIP settings */
133  SCIP_PROB* transprob, /**< tranformed problem data */
134  SCIP_PROB* origprob /**< original problem data */
135  );
136 
137 /** adds primal solution to solution storage by copying it */
138 extern
139 SCIP_RETCODE SCIPprimalAddSol(
140  SCIP_PRIMAL* primal, /**< primal data */
141  BMS_BLKMEM* blkmem, /**< block memory */
142  SCIP_SET* set, /**< global SCIP settings */
143  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
144  SCIP_STAT* stat, /**< problem statistics data */
145  SCIP_PROB* origprob, /**< original problem */
146  SCIP_PROB* transprob, /**< transformed problem after presolve */
147  SCIP_TREE* tree, /**< branch and bound tree */
148  SCIP_LP* lp, /**< current LP data */
149  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
150  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
151  SCIP_SOL* sol, /**< primal CIP solution */
152  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
153  );
154 
155 /** adds primal solution to solution storage, frees the solution afterwards */
156 extern
157 SCIP_RETCODE SCIPprimalAddSolFree(
158  SCIP_PRIMAL* primal, /**< primal data */
159  BMS_BLKMEM* blkmem, /**< block memory */
160  SCIP_SET* set, /**< global SCIP settings */
161  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
162  SCIP_STAT* stat, /**< problem statistics data */
163  SCIP_PROB* origprob, /**< original problem */
164  SCIP_PROB* transprob, /**< transformed problem after presolve */
165  SCIP_TREE* tree, /**< branch and bound tree */
166  SCIP_LP* lp, /**< current LP data */
167  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
168  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
169  SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
170  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
171  );
172 
173 /** adds primal solution to solution candidate storage of original problem space */
174 extern
175 SCIP_RETCODE SCIPprimalAddOrigSol(
176  SCIP_PRIMAL* primal, /**< primal data */
177  BMS_BLKMEM* blkmem, /**< block memory */
178  SCIP_SET* set, /**< global SCIP settings */
179  SCIP_STAT* stat, /**< problem statistics data */
180  SCIP_PROB* prob, /**< original problem data */
181  SCIP_SOL* sol, /**< primal CIP solution; is cleared in function call */
182  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
183  );
184 
185 /** adds primal solution to solution candidate storage of original problem space, frees the solution afterwards */
186 extern
187 SCIP_RETCODE SCIPprimalAddOrigSolFree(
188  SCIP_PRIMAL* primal, /**< primal data */
189  BMS_BLKMEM* blkmem, /**< block memory */
190  SCIP_SET* set, /**< global SCIP settings */
191  SCIP_STAT* stat, /**< problem statistics data */
192  SCIP_PROB* prob, /**< original problem data */
193  SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
194  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
195  );
196 
197 /** adds current LP/pseudo solution to solution storage */
198 extern
199 SCIP_RETCODE SCIPprimalAddCurrentSol(
200  SCIP_PRIMAL* primal, /**< primal data */
201  BMS_BLKMEM* blkmem, /**< block memory */
202  SCIP_SET* set, /**< global SCIP settings */
203  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
204  SCIP_STAT* stat, /**< problem statistics data */
205  SCIP_PROB* origprob, /**< original problem */
206  SCIP_PROB* transprob, /**< transformed problem after presolve */
207  SCIP_TREE* tree, /**< branch and bound tree */
208  SCIP_LP* lp, /**< current LP data */
209  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
210  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
211  SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */
212  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
213  );
214 
215 /** checks primal solution; if feasible, adds it to storage by copying it */
216 extern
217 SCIP_RETCODE SCIPprimalTrySol(
218  SCIP_PRIMAL* primal, /**< primal data */
219  BMS_BLKMEM* blkmem, /**< block memory */
220  SCIP_SET* set, /**< global SCIP settings */
221  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
222  SCIP_STAT* stat, /**< problem statistics data */
223  SCIP_PROB* origprob, /**< original problem */
224  SCIP_PROB* transprob, /**< transformed problem after presolve */
225  SCIP_TREE* tree, /**< branch and bound tree */
226  SCIP_LP* lp, /**< current LP data */
227  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
228  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
229  SCIP_SOL* sol, /**< primal CIP solution */
230  SCIP_Bool printreason, /**< should all reasons of violations be printed? */
231  SCIP_Bool checkbounds, /**< should the bounds of the variables be checked? */
232  SCIP_Bool checkintegrality, /**< has integrality to be checked? */
233  SCIP_Bool checklprows, /**< have current LP rows to be checked? */
234  SCIP_Bool* stored /**< stores whether given solution was feasible and good enough to keep */
235  );
236 
237 /** checks primal solution; if feasible, adds it to storage; solution is freed afterwards */
238 extern
239 SCIP_RETCODE SCIPprimalTrySolFree(
240  SCIP_PRIMAL* primal, /**< primal data */
241  BMS_BLKMEM* blkmem, /**< block memory */
242  SCIP_SET* set, /**< global SCIP settings */
243  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
244  SCIP_STAT* stat, /**< problem statistics data */
245  SCIP_PROB* origprob, /**< original problem */
246  SCIP_PROB* transprob, /**< transformed problem after presolve */
247  SCIP_TREE* tree, /**< branch and bound tree */
248  SCIP_LP* lp, /**< current LP data */
249  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
250  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
251  SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */
252  SCIP_Bool printreason, /**< should all reasons of violations be printed? */
253  SCIP_Bool checkbounds, /**< should the bounds of the variables be checked? */
254  SCIP_Bool checkintegrality, /**< has integrality to be checked? */
255  SCIP_Bool checklprows, /**< have current LP rows to be checked? */
256  SCIP_Bool* stored /**< stores whether solution was feasible and good enough to keep */
257  );
258 
259 /** checks current LP/pseudo solution; if feasible, adds it to storage */
260 extern
261 SCIP_RETCODE SCIPprimalTryCurrentSol(
262  SCIP_PRIMAL* primal, /**< primal data */
263  BMS_BLKMEM* blkmem, /**< block memory */
264  SCIP_SET* set, /**< global SCIP settings */
265  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
266  SCIP_STAT* stat, /**< problem statistics data */
267  SCIP_PROB* origprob, /**< original problem */
268  SCIP_PROB* transprob, /**< transformed problem after presolve */
269  SCIP_TREE* tree, /**< branch and bound tree */
270  SCIP_LP* lp, /**< current LP data */
271  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
272  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
273  SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */
274  SCIP_Bool printreason, /**< should all reasons of violations be printed? */
275  SCIP_Bool checkintegrality, /**< has integrality to be checked? */
276  SCIP_Bool checklprows, /**< have current LP rows to be checked? */
277  SCIP_Bool* stored /**< stores whether given solution was good enough to keep */
278  );
279 
280 /** inserts solution into the global array of all existing primal solutions */
281 extern
282 SCIP_RETCODE SCIPprimalSolCreated(
283  SCIP_PRIMAL* primal, /**< primal data */
284  SCIP_SET* set, /**< global SCIP settings */
285  SCIP_SOL* sol /**< primal CIP solution */
286  );
287 
288 /** removes solution from the global array of all existing primal solutions */
289 extern
290 void SCIPprimalSolFreed(
291  SCIP_PRIMAL* primal, /**< primal data */
292  SCIP_SOL* sol /**< primal CIP solution */
293  );
294 
295 /** updates all existing primal solutions after a change in a variable's objective value */
296 extern
297 void SCIPprimalUpdateVarObj(
298  SCIP_PRIMAL* primal, /**< primal data */
299  SCIP_VAR* var, /**< problem variable */
300  SCIP_Real oldobj, /**< old objective value */
301  SCIP_Real newobj /**< new objective value */
302  );
303 
304 /** retransforms all existing solutions to original problem space */
305 extern
306 SCIP_RETCODE SCIPprimalRetransformSolutions(
307  SCIP_PRIMAL* primal, /**< primal data */
308  SCIP_SET* set, /**< global SCIP settings */
309  SCIP_STAT* stat, /**< problem statistics data */
310  SCIP_PROB* origprob, /**< original problem */
311  SCIP_PROB* transprob /**< transformed problem */
312  );
313 
314 /** tries to transform original solution to the transformed problem space */
315 extern
316 SCIP_RETCODE SCIPprimalTransformSol(
317  SCIP_PRIMAL* primal, /**< primal data */
318  SCIP_SOL* sol, /**< primal solution */
319  BMS_BLKMEM* blkmem, /**< block memory */
320  SCIP_SET* set, /**< global SCIP settings */
321  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
322  SCIP_STAT* stat, /**< problem statistics data */
323  SCIP_PROB* origprob, /**< original problem */
324  SCIP_PROB* transprob, /**< transformed problem after presolve */
325  SCIP_TREE* tree, /**< branch and bound tree */
326  SCIP_LP* lp, /**< current LP data */
327  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
328  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
329  SCIP_Real* solvals, /**< array for internal use to store solution values, or NULL;
330  * if the method is called multiple times in a row, an array with size >=
331  * number of active variables should be given for performance reasons */
332  SCIP_Bool* solvalset, /**< array for internal use to store which solution values were set, or NULL;
333  * if the method is called multiple times in a row, an array with size >=
334  * number of active variables should be given for performance reasons */
335  int solvalssize, /**< size of solvals and solvalset arrays, should be >= number of active
336  * variables */
337  SCIP_Bool* added /**< pointer to store whether the solution was added */
338  );
339 
340 #ifdef __cplusplus
341 }
342 #endif
343 
344 #endif
345