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