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