Scippy

SCIP

Solving Constraint Integer Programs

solve.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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file solve.h
26  * @ingroup INTERNALAPI
27  * @brief internal methods for main solving loop and node processing
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_SOLVE_H__
34 #define __SCIP_SOLVE_H__
35 
36 
37 #include "blockmemshell/memory.h"
38 #include "scip/def.h"
39 #include "scip/type_conflict.h"
41 #include "scip/type_cutpool.h"
42 #include "scip/type_event.h"
43 #include "scip/type_lp.h"
44 #include "scip/type_mem.h"
45 #include "scip/type_message.h"
46 #include "scip/type_pricestore.h"
47 #include "scip/type_primal.h"
48 #include "scip/type_prob.h"
49 #include "scip/type_reopt.h"
50 #include "scip/type_retcode.h"
51 #include "scip/type_sepastore.h"
52 #include "scip/type_set.h"
53 #include "scip/type_stat.h"
54 #include "scip/type_tree.h"
55 
56 #ifdef __cplusplus
57 extern "C" {
58 #endif
59 
60 /** returns whether the solving process will be / was stopped before proving optimality;
61  * if the solving process was stopped, stores the reason as status in stat
62  */
63 SCIP_EXPORT
65  SCIP_SET* set, /**< global SCIP settings */
66  SCIP_STAT* stat, /**< dynamic problem statistics */
67  SCIP_Bool checknodelimits /**< should the node limits be involved in the check? */
68  );
69 
70 /** applies domain propagation on current node and flushes the conflict store afterwards */
72  BMS_BLKMEM* blkmem, /**< block memory buffers */
73  SCIP_SET* set, /**< global SCIP settings */
74  SCIP_STAT* stat, /**< dynamic problem statistics */
75  SCIP_PROB* transprob, /**< transformed problem */
76  SCIP_PROB* origprob, /**< original problem */
77  SCIP_TREE* tree, /**< branch and bound tree */
78  SCIP_REOPT* reopt, /**< reoptimization data structure */
79  SCIP_LP* lp, /**< LP data */
80  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
81  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
82  SCIP_CONFLICT* conflict, /**< conflict analysis data */
83  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
84  int depth, /**< depth level to use for propagator frequency checks */
85  int maxrounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
86  SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */
87  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
88  );
89 
90 /** puts all constraints with initial flag TRUE into the LP */
92  BMS_BLKMEM* blkmem, /**< block memory buffers */
93  SCIP_SET* set, /**< global SCIP settings */
94  SCIP_SEPASTORE* sepastore, /**< separation storage */
95  SCIP_CUTPOOL* cutpool, /**< global cutpool */
96  SCIP_STAT* stat, /**< dynamic problem statistics */
97  SCIP_PROB* transprob, /**< transformed problem */
98  SCIP_PROB* origprob, /**< original problem */
99  SCIP_TREE* tree, /**< branch and bound tree */
100  SCIP_REOPT* reopt, /**< reoptimization data structure */
101  SCIP_LP* lp, /**< LP data */
102  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
103  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
104  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
105  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
106  SCIP_Bool root, /**< is this the initial root LP? */
107  SCIP_Bool firstsubtreeinit, /**< is this the first call in the current subtree after jumping through the tree? */
108  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
109  );
110 
111 /** constructs the LP of the current node, but does not load the LP state and warmstart information */
113  BMS_BLKMEM* blkmem, /**< block memory buffers */
114  SCIP_SET* set, /**< global SCIP settings */
115  SCIP_STAT* stat, /**< dynamic problem statistics */
116  SCIP_PROB* transprob, /**< transformed problem */
117  SCIP_PROB* origprob, /**< original problem */
118  SCIP_TREE* tree, /**< branch and bound tree */
119  SCIP_REOPT* reopt, /**< reoptimization data structure */
120  SCIP_LP* lp, /**< LP data */
121  SCIP_PRICESTORE* pricestore, /**< pricing storage */
122  SCIP_SEPASTORE* sepastore, /**< separation storage */
123  SCIP_CUTPOOL* cutpool, /**< global cutpool */
124  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
125  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
126  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
127  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
128  SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */
129  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
130  );
131 
132 /** calls primal heuristics */
134  SCIP_SET* set, /**< global SCIP settings */
135  SCIP_STAT* stat, /**< dynamic problem statistics */
136  SCIP_PROB* prob, /**< transformed problem after presolve */
137  SCIP_PRIMAL* primal, /**< primal data */
138  SCIP_TREE* tree, /**< branch and bound tree */
139  SCIP_LP* lp, /**< LP data */
140  SCIP_NODE* nextnode, /**< next node that will be processed, or NULL if no more nodes left
141  * (only needed when calling after node heuristics) */
142  SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
143  SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
144  SCIP_Bool* foundsol, /**< pointer to store whether a solution has been found */
145  SCIP_Bool* unbounded /**< pointer to store whether an unbounded ray was found in the LP */
146  );
147 
148 /** applies one round of separation on the given primal solution or on the LP solution */
150  BMS_BLKMEM* blkmem, /**< block memory buffers */
151  SCIP_SET* set, /**< global SCIP settings */
152  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
153  SCIP_STAT* stat, /**< dynamic problem statistics */
154  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
155  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
156  SCIP_PROB* prob, /**< transformed problem after presolve */
157  SCIP_PRIMAL* primal, /**< primal data */
158  SCIP_TREE* tree, /**< branch and bound tree */
159  SCIP_LP* lp, /**< LP data */
160  SCIP_SEPASTORE* sepastore, /**< separation storage */
161  SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
162  int actdepth, /**< current depth in the tree */
163  SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
164  SCIP_Bool onlydelayed, /**< should only delayed separators be called? */
165  SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
166  SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
167  );
168 
169 /** solves the current LP completely with pricing in new variables */
171  BMS_BLKMEM* blkmem, /**< block memory buffers */
172  SCIP_SET* set, /**< global SCIP settings */
173  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
174  SCIP_STAT* stat, /**< dynamic problem statistics */
175  SCIP_PROB* transprob, /**< transformed problem */
176  SCIP_PROB* origprob, /**< original problem */
177  SCIP_PRIMAL* primal, /**< primal data */
178  SCIP_TREE* tree, /**< branch and bound tree */
179  SCIP_REOPT* reopt, /**< reoptimization data structure */
180  SCIP_LP* lp, /**< LP data */
181  SCIP_PRICESTORE* pricestore, /**< pricing storage */
182  SCIP_SEPASTORE* sepastore, /**< separation storage */
183  SCIP_CUTPOOL* cutpool, /**< global cutpool */
184  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
185  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
186  SCIP_EVENTFILTER* eventfilter, /**< global event filter */
187  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
188  SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
189  SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
190  int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
191  * a finite limit means that the LP might not be solved to optimality! */
192  int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */
193  SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */
194  SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */
195  SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must
196  * not be used */
197  );
198 
199 /** main solving loop */
201  BMS_BLKMEM* blkmem, /**< block memory buffers */
202  SCIP_SET* set, /**< global SCIP settings */
203  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
204  SCIP_STAT* stat, /**< dynamic problem statistics */
205  SCIP_MEM* mem, /**< block memory pools */
206  SCIP_PROB* origprob, /**< original problem */
207  SCIP_PROB* transprob, /**< transformed problem after presolve */
208  SCIP_PRIMAL* primal, /**< primal data */
209  SCIP_TREE* tree, /**< branch and bound tree */
210  SCIP_REOPT* reopt, /**< reoptimization data structure */
211  SCIP_LP* lp, /**< LP data */
212  SCIP_RELAXATION* relaxation, /**< global relaxation data */
213  SCIP_PRICESTORE* pricestore, /**< pricing storage */
214  SCIP_SEPASTORE* sepastore, /**< separation storage */
215  SCIP_CUTPOOL* cutpool, /**< global cut pool */
216  SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */
217  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
218  SCIP_CONFLICT* conflict, /**< conflict analysis data */
219  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
220  SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
221  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
222  SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
223  SCIP_Bool* restart /**< should solving process be started again with presolving? */
224  );
225 
226 #ifdef __cplusplus
227 }
228 #endif
229 
230 #endif
SCIP_RETCODE SCIPseparationRound(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int actdepth, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: solve.c:1960
type definitions for conflict store
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:106
type definitions for storing priced variables
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for global SCIP settings
SCIP_RETCODE SCIPconstructCurrentLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool newinitconss, SCIP_Bool *cutoff)
Definition: solve.c:1281
type definitions for return codes for SCIP methods
type definitions for collecting reoptimization information
type definitions for problem statistics
type definitions for LP management
SCIP_RETCODE SCIPsolveCIP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_MEM *mem, SCIP_PROB *origprob, SCIP_PROB *transprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_CUTPOOL *delayedcutpool, SCIP_BRANCHCAND *branchcand, SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *restart)
Definition: solve.c:4828
type definitions for storing cuts in a cut pool
SCIP_RETCODE SCIPpropagateDomains(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CONFLICT *conflict, SCIP_CLIQUETABLE *cliquetable, int depth, int maxrounds, SCIP_PROPTIMING timingmask, SCIP_Bool *cutoff)
Definition: solve.c:644
type definitions for storing separated cuts
type definitions for conflict analysis
type definitions for managing events
#define SCIP_Bool
Definition: def.h:93
type definitions for branch and bound tree
SCIP_RETCODE SCIPpriceLoop(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, int *npricedcolvars, SCIP_Bool *mustsepa, SCIP_Bool *lperror, SCIP_Bool *aborted)
Definition: solve.c:2013
type definitions for storing and manipulating the main problem
type definitions for block memory pools and memory buffers
unsigned int SCIP_PROPTIMING
Definition: type_timing.h:75
SCIP_RETCODE SCIPprimalHeuristics(SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_NODE *nextnode, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, SCIP_Bool *foundsol, SCIP_Bool *unbounded)
Definition: solve.c:214
type definitions for message output methods
type definitions for collecting primal CIP solutions and primal informations
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
SCIP_Bool SCIPsolveIsStopped(SCIP_SET *set, SCIP_STAT *stat, SCIP_Bool checknodelimits)
Definition: solve.c:102
SCIP_RETCODE SCIPinitConssLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_Bool firstsubtreeinit, SCIP_Bool *cutoff)
Definition: solve.c:1108
memory allocation routines