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   cutsel_hybrid.h
26   	 * @ingroup CUTSELECTORS
27   	 * @brief  hybrid cut selector
28   	 * @author Leona Gottwald
29   	 * @author Felipe Serrano
30   	 * @author Mark Turner
31   	 *
32   	 * The hybrid cut selector scores cuts by using a weighted sum of the efficacy, directed cutoff distance, objective
33   	 * parallelism, and integer support of the cuts. Afterwards, it selects the cuts using the score and filtering for
34   	 * parallelism after selecting each cut.
35   	 *
36   	 * If a cut is given by \f$ a^T x \leq b \f$, then
37   	 *  - the efficacy is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$;
38   	 *  - the directed cutoff distance is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$
39   	 *    restricted to the line segment joining the LP solution to the currently best primal solution; therefore, it is only
40   	 *    defined when a primal solution is available;
41   	 *  - the objective parallelism is how parallel the vector \f$ a \f$ is w.r.t. the objective function \f$ c \f$. That
42   	 *    is, the objective parallelism is given by \f$ \frac{a^T c}{\|a\| \|c\|} \f$. Notice that the vectors are parallel
43   	 *    when this formula returns 1;
44   	 *  - the integer support of a cut is the ratio between the number of nonzero integer columns and the number of nonzero
45   	 *    columns.
46   	 *
47   	 * These features of a cut can be recovered and/or computed with the functions @ref SCIPgetCutEfficacy(), @ref
48   	 * SCIPgetCutLPSolCutoffDistance(), @ref SCIPgetRowObjParallelism(), and @ref SCIPgetRowNumIntCols(), @ref
49   	 * SCIProwGetNNonz().
50   	 *
51   	 * The filtering step works as follows.
52   	 * After computing the scores, these are divided in two groups: good scores and bad scores.  Any score larger or equal
53   	 * to 90% of the largest score is considered a good score.
54   	 *
55   	 * First, the forced cuts --- cuts that are going to enter the LP no matter what --- are used to filter the non-forced
56   	 * cuts. This means that for each forced cut, @p fcut, the parallelism between @p fcut and
57   	 * every non-forced cut, @p cut, is computed (the parallelism between two cuts \f$ a^T x \leq b \f$ and \f$ d^T x \leq e\f$
58   	 * is \f$ \frac{a^T d}{\|a\| \|d\|} \f$).
59   	 * If the score of cut is good, then cut is dropped if its parallelism with @p fcut is larger or equal than the maximum
60   	 * between \f$ \frac{1}{2} \f$ and 1 - minimum orthogonality.
61   	 * If the score of cut is not good, then cut is dropped if its parallelism with @p fcut is larger or equal than 1 - minimum
62   	 * orthogonality.
63   	 *
64   	 * @note The minimum orthogonality is a parameter that can be set, as well as the weights for the score.
65   	 *
66   	 * @note In the case of no primal solution, the weight assigned to the directed cutoff distance is transfered to the
67   	 * efficacy.
68   	 */
69   	
70   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
71   	
72   	#ifndef __SCIP_CUTSEL_HYBRID_H__
73   	#define __SCIP_CUTSEL_HYBRID_H__
74   	
75   	
76   	#include "scip/scip.h"
77   	
78   	#ifdef __cplusplus
79   	extern "C" {
80   	#endif
81   	
82   	/** creates the hybrid separator and includes it in SCIP
83   	 *
84   	 * @ingroup CutSelectorIncludes
85   	 */
86   	SCIP_EXPORT
87   	SCIP_RETCODE SCIPincludeCutselHybrid(
88   	   SCIP*                 scip                /**< SCIP data structure */
89   	   );
90   	
91   	/**@addtogroup CUTSELECTORS
92   	 *
93   	 * @{
94   	 */
95   	
96   	/** perform a cut selection algorithm for the given array of cuts
97   	 *
98   	 *  This is the selection method of the hybrid cut selector which uses a weighted sum of the
99   	 *  efficacy, parallelism, directed cutoff distance, and the integral support.
100  	 *  The input cuts array gets resorted s.t the selected cuts come first and the remaining
101  	 *  ones are the end.
102  	 */
103  	SCIP_EXPORT
104  	SCIP_RETCODE SCIPselectCutsHybrid(
105  	   SCIP*                 scip,               /**< SCIP data structure */
106  	   SCIP_ROW**            cuts,               /**< array with cuts to perform selection algorithm */
107  	   SCIP_ROW**            forcedcuts,         /**< array with forced cuts */
108  	   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator for tie-breaking, or NULL */
109  	   SCIP_Real             goodscorefac,       /**< factor of best score among the given cuts to consider a cut good
110  	                                              *   and filter with less strict settings of the maximum parallelism */
111  	   SCIP_Real             badscorefac,        /**< factor of best score among the given cuts to consider a cut bad
112  	                                              *   and discard it regardless of its parallelism to other cuts */
113  	   SCIP_Real             goodmaxparall,      /**< maximum parallelism for good cuts */
114  	   SCIP_Real             maxparall,          /**< maximum parallelism for non-good cuts */
115  	   SCIP_Real             dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
116  	   SCIP_Real             efficacyweight,     /**< weight of efficacy in cut score calculation */
117  	   SCIP_Real             objparalweight,     /**< weight of objective parallelism in cut score calculation */
118  	   SCIP_Real             intsupportweight,   /**< weight of integral support in cut score calculation */
119  	   int                   ncuts,              /**< number of cuts in cuts array */
120  	   int                   nforcedcuts,        /**< number of forced cuts */
121  	   int                   maxselectedcuts,    /**< maximal number of cuts from cuts array to select */
122  	   int*                  nselectedcuts       /**< pointer to return number of selected cuts from cuts array */
123  	   );
124  	
125  	/** @} */
126  	
127  	#ifdef __cplusplus
128  	}
129  	#endif
130  	
131  	#endif
132