Scippy

SCIP

Solving Constraint Integer Programs

struct_conflict.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 2002-2022 Zuse Institute Berlin */
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 struct_conflict.h
26  * @ingroup INTERNALAPI
27  * @brief datastructures for conflict analysis
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_STRUCT_CONFLICT_H__
34 #define __SCIP_STRUCT_CONFLICT_H__
35 
36 
37 #include "scip/def.h"
38 #include "scip/type_clock.h"
39 #include "scip/type_misc.h"
40 #include "scip/type_var.h"
41 #include "scip/type_conflict.h"
42 #include "lpi/type_lpi.h"
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 /** conflict handler */
50 {
51  char* name; /**< name of conflict handler */
52  char* desc; /**< description of conflict handler */
53  SCIP_DECL_CONFLICTCOPY((*conflictcopy)); /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
54  SCIP_DECL_CONFLICTFREE((*conflictfree)); /**< destructor of conflict handler */
55  SCIP_DECL_CONFLICTINIT((*conflictinit)); /**< initialize conflict handler */
56  SCIP_DECL_CONFLICTEXIT((*conflictexit)); /**< deinitialize conflict handler */
57  SCIP_DECL_CONFLICTINITSOL((*conflictinitsol));/**< solving process initialization method of conflict handler */
58  SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol));/**< solving process deinitialization method of conflict handler */
59  SCIP_DECL_CONFLICTEXEC((*conflictexec)); /**< conflict processing method of conflict handler */
60  SCIP_CONFLICTHDLRDATA* conflicthdlrdata; /**< conflict handler data */
61  SCIP_CLOCK* setuptime; /**< time spend for setting up this conflict handler for the next stages */
62  SCIP_CLOCK* conflicttime; /**< conflict handler execution time */
63  int priority; /**< priority of the conflict handler */
64  SCIP_Bool initialized; /**< is conflict handler initialized? */
65 };
66 
67 /** set of conflicting bound changes */
69 {
70  SCIP_BDCHGINFO** bdchginfos; /**< bound change informations of the conflict set */
71  SCIP_BDCHGINFO* confbdchginfo; /**< a bound change at the conflict depth */
72  SCIP_Real* relaxedbds; /**< array of relaxed bounds which are efficient for a valid conflict */
73  SCIP_Real confrelaxedbd; /**< relaxed bound belonging the the bound change at the conflict depth */
74  int* sortvals; /**< aggregated var index/bound type values for sorting */
75  int bdchginfossize; /**< size of bdchginfos array */
76  int nbdchginfos; /**< number of bound change informations in the conflict set */
77  int validdepth; /**< depth in the tree where the conflict set is valid */
78  int insertdepth; /**< depth level where constraint should be added */
79  int conflictdepth; /**< depth in the tree where the conflict set yields a conflict */
80  int repropdepth; /**< depth at which the conflict set triggers a deduction */
81  unsigned int repropagate:1; /**< should the conflict constraint trigger a repropagation? */
82  unsigned int depthcalced:1; /**< are the conflict and repropagation depth calculated? */
83  unsigned int sorted:1; /**< is the conflict set sorted */
84  unsigned int usescutoffbound:1; /**< is the conflict based on the cutoff bound? */
85  unsigned int hasrelaxonlyvar:1; /**< is one of the bound change informations using a relaxation-only variable */
86  SCIP_CONFTYPE conflicttype; /**< conflict type: unknown, infeasible LP, bound exceeding LP, propagation */
87 };
88 
89 /** set of conflicting bound changes */
91 {
93  int* inds;
95  int nnz;
96  int size;
98  SCIP_CONFTYPE conflicttype; /**< conflict type: unknown, infeasible LP, bound exceeding LP */
99 };
100 
101 /** set of LP bound change */
103 {
104  int* bdchginds; /**< array of column indices */
105  SCIP_Real* bdchglbs; /**< array of lower bounds */
106  SCIP_Real* bdchgubs; /**< array of upper bounds */
107  int* bdchgcolinds; /**< array of ???????????? */
108  SCIP_Bool* usedcols; /**< array to mark if a column is used */
109  int nbdchgs; /**< number of stored LP bound changes */
110 };
111 
112 /** conflict analysis data structure */
114 {
115  SCIP_Longint nglbchgbds; /**< total number of applied global bound changes */
116  SCIP_Longint nappliedglbconss; /**< total number of conflict constraints added globally to the problem */
117  SCIP_Longint nappliedglbliterals;/**< total number of literals in globally applied conflict constraints */
118  SCIP_Longint nlocchgbds; /**< total number of applied local bound changes */
119  SCIP_Longint nappliedlocconss; /**< total number of conflict constraints added locally to the problem */
120  SCIP_Longint nappliedlocliterals;/**< total number of literals in locally applied conflict constraints */
121  SCIP_Longint npropcalls; /**< number of calls to propagation conflict analysis */
122  SCIP_Longint npropsuccess; /**< number of calls yielding at least one conflict constraint */
123  SCIP_Longint npropconfconss; /**< number of valid conflict constraints detected in propagation conflict analysis */
124  SCIP_Longint npropconfliterals; /**< total number of literals in valid propagation conflict constraints */
125  SCIP_Longint npropreconvconss; /**< number of reconvergence constraints detected in propagation conflict analysis */
126  SCIP_Longint npropreconvliterals;/**< total number of literals in valid propagation reconvergence constraints */
127  SCIP_Longint ninflpcalls; /**< number of calls to infeasible LP conflict analysis */
128  SCIP_Longint ninflpsuccess; /**< number of calls yielding at least one conflict constraint */
129  SCIP_Longint ninflpconfconss; /**< number of valid conflict constraints detected in infeasible LP conflict
130  * analysis */
131  SCIP_Longint ninflpconfliterals; /**< total number of literals in valid infeasible LP conflict constraints */
132  SCIP_Longint ninflpreconvconss; /**< number of reconvergence constraints detected in infeasible LP conflict
133  * analysis */
134  SCIP_Longint ninflpreconvliterals; /**< total number of literals in valid infeasible LP reconvergence
135  * constraints */
136  SCIP_Longint ninflpiterations; /**< total number of LP iterations used in infeasible LP conflict analysis */
137  SCIP_Longint nboundlpcalls; /**< number of calls to bound exceeding LP conflict analysis */
138  SCIP_Longint nboundlpsuccess; /**< number of calls yielding at least one conflict constraint */
139  SCIP_Longint nboundlpconfconss; /**< number of valid conflict constraints detected in bound exceeding LP
140  * conflict analysis */
141  SCIP_Longint nboundlpconfliterals; /**< total number of literals in valid bound exceeding LP conflict
142  * constraints */
143  SCIP_Longint nboundlpreconvconss;/**< number of reconvergence constraints detected in bound exceeding LP
144  * conflict analysis */
145  SCIP_Longint nboundlpreconvliterals; /**< total number of literals in valid bound exceeding LP reconvergence
146  * constraints */
147  SCIP_Longint nboundlpiterations; /**< total number of LP iterations used in bound exceeding LP conflict
148  * analysis */
149  SCIP_Longint nsbcalls; /**< number of calls to infeasible strong branching conflict analysis */
150  SCIP_Longint nsbsuccess; /**< number of calls yielding at least one conflict constraint */
151  SCIP_Longint nsbconfconss; /**< number of conflict constraints detected in strong branching conflict analysis */
152  SCIP_Longint nsbconfliterals; /**< total number of literals in valid strong branching conflict constraints */
153  SCIP_Longint nsbreconvconss; /**< number of reconvergence constraints detected in strong branch conflict analysis */
154  SCIP_Longint nsbreconvliterals; /**< total number of literals in valid strong branching reconvergence constraints */
155  SCIP_Longint nsbiterations; /**< total number of LP iterations used in strong branching conflict analysis */
156  SCIP_Longint npseudocalls; /**< number of calls to pseudo solution conflict analysis */
157  SCIP_Longint npseudosuccess; /**< number of calls yielding at least one conflict constraint */
158  SCIP_Longint npseudoconfconss; /**< number of valid conflict constraints detected in pseudo sol conflict analysis */
159  SCIP_Longint npseudoconfliterals;/**< total number of literals in valid pseudo solution conflict constraints */
160  SCIP_Longint npseudoreconvconss; /**< number of reconvergence constraints detected in pseudo sol conflict analysis */
161  SCIP_Longint npseudoreconvliterals;/**< total number of literals in valid pseudo solution reconvergence constraints */
162  SCIP_Longint ndualproofsinfglobal;/**< number of globally added dual proof constraints derived from infeasible LP */
163  SCIP_Longint ndualproofsinflocal;/**< number of locally added dual proof constraints derived from infeasible LP */
164  SCIP_Longint ndualproofsinfsuccess;/**< number of successfully dual proof analysis calls for infeasible LPs */
165  SCIP_Longint dualproofsinfnnonzeros;/**< number of non-zeros over all accepted dual proof constraints derived from infeasible LP */
166  SCIP_Longint ndualproofsbndglobal;/**< number of globally added dual proof constraints derived from bound exceeding LP */
167  SCIP_Longint ndualproofsbndlocal;/**< number of locally added dual proof constraints derived from bound exceeding LP */
168  SCIP_Longint ndualproofsbndsuccess;/**< number of successfully dual proof analysis calls for bound exceeding LPs */
169  SCIP_Longint dualproofsbndnnonzeros;/**< number of non-zeros over all accepted dual proof constraints derived from bound exceeding LPs */
170 
171  SCIP_CLOCK* dIBclock; /**< time used for detect implied bounds */
172 
173  SCIP_CLOCK* propanalyzetime; /**< time used for propagation conflict analysis */
174  SCIP_CLOCK* inflpanalyzetime; /**< time used for infeasible LP conflict analysis */
175  SCIP_CLOCK* boundlpanalyzetime; /**< time used for bound exceeding LP conflict analysis */
176  SCIP_CLOCK* sbanalyzetime; /**< time used for strong branching LP conflict analysis */
177  SCIP_CLOCK* pseudoanalyzetime; /**< time used for pseudo solution conflict analysis */
178  SCIP_PQUEUE* bdchgqueue; /**< unprocessed conflict bound changes */
179  SCIP_PQUEUE* forcedbdchgqueue; /**< unprocessed conflict bound changes that must be resolved */
180  SCIP_PROOFSET* proofset; /**< proof sets found at the current node */
181  SCIP_PROOFSET** proofsets; /**< proof sets found at the current node */
182  SCIP_CONFLICTSET* conflictset; /**< bound changes resembling the current conflict set */
183  SCIP_CONFLICTSET** conflictsets; /**< conflict sets found at the current node */
184  SCIP_Real* conflictsetscores; /**< score values of the conflict sets found at the current node */
185  SCIP_BDCHGINFO** tmpbdchginfos; /**< temporarily created bound change information data */
186  int conflictsetssize; /**< size of conflictsets array */
187  int nconflictsets; /**< number of available conflict sets (used slots in conflictsets array) */
188  int proofsetssize; /**< size of proofsets array */
189  int nproofsets; /**< number of available proof sets (used slots in proofsets array) */
190  int tmpbdchginfossize; /**< size of tmpbdchginfos array */
191  int ntmpbdchginfos; /**< number of temporary created bound change information data */
192  int count; /**< conflict set counter to label binary conflict variables with */
193 };
194 
195 #ifdef __cplusplus
196 }
197 #endif
198 
199 #endif
SCIP_CLOCK * propanalyzetime
unsigned int sorted
SCIP_Longint ninflpconfliterals
unsigned int repropagate
SCIP_Longint ninflpreconvconss
SCIP_Longint ndualproofsinfsuccess
type definitions for miscellaneous datastructures
SCIP_Real confrelaxedbd
SCIP_PQUEUE * bdchgqueue
SCIP_Longint dualproofsinfnnonzeros
SCIP_Longint nsbcalls
SCIP_Longint nappliedlocliterals
SCIP_CLOCK * inflpanalyzetime
SCIP_Real * bdchgubs
SCIP_Longint nappliedglbliterals
SCIP_Longint npseudoreconvliterals
SCIP_Longint npropconfliterals
SCIP_Longint nappliedglbconss
SCIP_Longint npseudoreconvconss
SCIP_Longint nlocchgbds
SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))
SCIP_DECL_CONFLICTCOPY((*conflictcopy))
SCIP_Real * relaxedbds
SCIP_Longint npropcalls
SCIP_Longint nglbchgbds
SCIP_Real * bdchglbs
SCIP_Longint npropsuccess
SCIP_DECL_CONFLICTEXEC((*conflictexec))
SCIP_Longint nappliedlocconss
SCIP_Longint npseudosuccess
SCIP_Longint ninflpiterations
SCIP_Longint npropreconvliterals
SCIP_Longint ndualproofsinflocal
SCIP_Longint npropconfconss
SCIP_Longint nboundlpcalls
SCIP_CLOCK * setuptime
SCIP_CLOCK * pseudoanalyzetime
SCIP_CLOCK * boundlpanalyzetime
SCIP_Longint ninflpreconvliterals
SCIP_BDCHGINFO ** tmpbdchginfos
SCIP_CLOCK * conflicttime
SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))
SCIP_Longint ndualproofsbndglobal
SCIP_CONFLICTHDLRDATA * conflicthdlrdata
SCIP_Longint ndualproofsbndlocal
SCIP_Longint npropreconvconss
SCIP_PROOFSET * proofset
type definitions for specific LP solvers interface
SCIP_DECL_CONFLICTEXIT((*conflictexit))
SCIP_PROOFSET ** proofsets
SCIP_Longint ninflpcalls
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:49
unsigned int depthcalced
type definitions for problem variables
type definitions for conflict analysis
SCIP_CLOCK * sbanalyzetime
SCIP_Longint dualproofsbndnnonzeros
SCIP_Longint nboundlpsuccess
SCIP_CONFLICTSET * conflictset
SCIP_Longint nboundlpreconvconss
SCIP_DECL_CONFLICTFREE((*conflictfree))
#define SCIP_Bool
Definition: def.h:93
SCIP_Real * vals
SCIP_Longint ndualproofsinfglobal
SCIP_CONFTYPE conflicttype
SCIP_PQUEUE * forcedbdchgqueue
SCIP_Longint nboundlpreconvliterals
SCIP_Longint nsbconfconss
type definitions for clocks and timing issues
SCIP_Longint nsbconfliterals
SCIP_Longint nboundlpiterations
SCIP_Longint npseudoconfliterals
SCIP_Longint ninflpconfconss
SCIP_CONFTYPE conflicttype
SCIP_Longint nsbsuccess
SCIP_Longint nsbreconvliterals
SCIP_Longint nboundlpconfliterals
SCIP_Real * conflictsetscores
#define SCIP_Real
Definition: def.h:186
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:65
SCIP_Longint npseudocalls
unsigned int hasrelaxonlyvar
SCIP_DECL_CONFLICTINIT((*conflictinit))
SCIP_CLOCK * dIBclock
SCIP_Longint nsbiterations
SCIP_Longint nboundlpconfconss
#define SCIP_Longint
Definition: def.h:171
SCIP_Longint npseudoconfconss
SCIP_BDCHGINFO ** bdchginfos
unsigned int usescutoffbound
SCIP_CONFLICTSET ** conflictsets
common defines and data types used in all packages of SCIP
SCIP_Longint ndualproofsbndsuccess
SCIP_BDCHGINFO * confbdchginfo
SCIP_Longint nsbreconvconss
SCIP_Bool * usedcols
SCIP_Longint ninflpsuccess