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-2024 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
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"
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
57extern "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 */
63SCIP_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
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition: def.h:91
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
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:648
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:4944
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:1112
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:2095
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:1285
SCIP_Bool SCIPsolveIsStopped(SCIP_SET *set, SCIP_STAT *stat, SCIP_Bool checknodelimits)
Definition: solve.c:102
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:2042
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:218
Definition: heur_padm.c:135
type definitions for conflict analysis
type definitions for conflict store
type definitions for storing cuts in a cut pool
type definitions for managing events
type definitions for LP management
type definitions for block memory pools and memory buffers
type definitions for message output methods
type definitions for storing priced variables
type definitions for collecting primal CIP solutions and primal informations
type definitions for storing and manipulating the main problem
type definitions for collecting reoptimization information
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for storing separated cuts
type definitions for global SCIP settings
type definitions for problem statistics
unsigned int SCIP_PROPTIMING
Definition: type_timing.h:74
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:101
type definitions for branch and bound tree