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   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 */
49   	struct SCIP_Conflicthdlr
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 */
68   	struct SCIP_ConflictSet
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 */
90   	struct SCIP_ProofSet
91   	{
92   	   SCIP_Real*            vals;
93   	   int*                  inds;
94   	   SCIP_Real             rhs;
95   	   int                   nnz;
96   	   int                   size;
97   	   int                   validdepth;
98   	   SCIP_CONFTYPE         conflicttype;       /**< conflict type: unknown, infeasible LP, bound exceeding LP */
99   	};
100  	
101  	/** set of LP bound change */
102  	struct SCIP_LPBdChgs
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 */
113  	struct SCIP_Conflict
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
200