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_implics.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  datastructures for implications, variable bounds, and cliques
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_STRUCT_IMPLICS_H__
34   	#define __SCIP_STRUCT_IMPLICS_H__
35   	
36   	
37   	#include "scip/def.h"
38   	#include "scip/type_implics.h"
39   	#include "scip/type_lp.h"
40   	#include "scip/type_misc.h"
41   	#include "scip/type_var.h"
42   	
43   	#ifdef __cplusplus
44   	extern "C" {
45   	#endif
46   	
47   	/** variable bounds of a variable x in the form x <= b*z + d  or  x >= b*z + d */
48   	struct SCIP_VBounds
49   	{
50   	   SCIP_VAR**            vars;               /**< variables z    in variable bounds x <= b*z + d  or  x >= b*z + d */
51   	   SCIP_Real*            coefs;              /**< coefficients b in variable bounds x <= b*z + d  or  x >= b*z + d */
52   	   SCIP_Real*            constants;          /**< constants d    in variable bounds x <= b*z + d  or  x >= b*z + d */
53   	   int                   len;                /**< number of existing variable bounds (used slots in arrays) */
54   	   int                   size;               /**< size of vars, coefs, and constants arrays */
55   	};
56   	
57   	/** implications for binary variable x to non-binary variables y in the form
58   	 *    x  <= 0  ==>  y <= b or y >= b (stored in arrays[0])
59   	 *    x  >= 1  ==>  y <= b or y >= b (stored in arrays[1])
60   	 *  array is sorted by variable index of y
61   	 */
62   	struct SCIP_Implics
63   	{
64   	   SCIP_VAR**            vars[2];            /**< variables y  in implications y <= b or y >= b */
65   	   SCIP_BOUNDTYPE*       types[2];           /**< types        of implications y <= b (SCIP_BOUNDTYPE_UPPER)
66   	                                              *                             or y >= b (SCIP_BOUNDTYPE_LOWER) */
67   	   SCIP_Real*            bounds[2];          /**< bounds b     in implications y <= b or y >= b */
68   	   int*                  ids[2];             /**< unique ids of implications; < 0 iff implication is a shortcut,
69   	                                              *   i.e., it was added as part of the transitive closure of another implication */
70   	   int                   size[2];            /**< size of implvars, implbounds and implvals arrays  for x <= 0 and x >= 1*/
71   	   int                   nimpls[2];          /**< number of all implications                        for x <= 0 and x >= 1 */
72   	};
73   	
74   	/** single clique, stating that at most one of the binary variables can be fixed to the corresponding value */
75   	struct SCIP_Clique
76   	{
77   	   SCIP_VAR**            vars;               /**< variables in the clique */
78   	   SCIP_Bool*            values;             /**< values of the variables in the clique */
79   	   int                   nvars;              /**< number of variables in the clique */
80   	   int                   size;               /**< size of vars and values arrays */
81   	   int                   startcleanup;       /**< clean up position to start with */
82   	   int                   index;              /**< the index of the clique in the cliquetable cliques array */
83   	   unsigned int          id:30;              /**< unique identifier of clique */
84   	   unsigned int          eventsissued:1;     /**< were the IMPLADDED events on the variables already issued? */
85   	   unsigned int          equation:1;         /**< is the clique an equation or an inequality? */
86   	};
87   	
88   	/** list of cliques for a single variable */
89   	struct SCIP_CliqueList
90   	{
91   	   SCIP_CLIQUE**         cliques[2];         /**< cliques the variable fixed to FALSE/TRUE is member of */
92   	   int                   ncliques[2];        /**< number of cliques the variable fixed to FALSE/TRUE is member of */
93   	   int                   size[2];            /**< size of cliques arrays */
94   	};
95   	
96   	/** collection of cliques */
97   	struct SCIP_CliqueTable
98   	{
99   	   SCIP_HASHTABLE*       hashtable;          /**< hash table holding all cliques */
100  	   SCIP_HASHMAP*         varidxtable;        /**< mapping from binary variable to their corresponding node indices */
101  	   SCIP_DISJOINTSET*     djset;              /**< disjoint set (union find) data structure to maintain component information */
102  	   SCIP_CLIQUE**         cliques;            /**< cliques stored in the table */
103  	   SCIP_Longint          nentries;           /**< number of entries in the whole clique table */
104  	   int                   ncliques;           /**< number of cliques stored in the table */
105  	   int                   size;               /**< size of cliques array */
106  	   int                   ncreatedcliques;    /**< number of ever created cliques */
107  	   int                   ncleanupfixedvars;  /**< number of fixed variables when the last cleanup was performed */
108  	   int                   ncleanupaggrvars;   /**< number of aggregated variables when the last cleanup was performed */
109  	   int                   ndirtycliques;      /**< number of cliques stored when the last cleanup was performed */
110  	   int                   ncliquecomponents;  /**< number of connected components in clique graph */
111  	   SCIP_Bool             incleanup;          /**< is this clique table currently performing cleanup? */
112  	   SCIP_Bool             compsfromscratch;   /**< must the connected components of the clique graph be recomputed from scratch? */
113  	};
114  	
115  	#ifdef __cplusplus
116  	}
117  	#endif
118  	
119  	#endif
120