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   cutsel_dynamic.h
17   	 * @ingroup CUTSELECTORS
18   	 * @brief  dynamic cut selector
19   	 * @author Christoph Graczyk
20   	 *
21   	 *  The dynamic cut selector is an extension of the hybrid cut selector to employ a dynamic range for the orthogonality
22   	 *  filtering, dependent on the efficacy ratio between cuts. It allows the user to specify a minimum efficacy gain in
23   	 *  percentage to filter cuts, which corresponds geometrically to the idealized shift from the LP solution adding only
24   	 *  the first cut to the intersection with the second cut.
25   	 *  In this way we can enforce a minimum orthogonality between cuts through the efficacy ratio. This should, in theory,
26   	 *  avoid the selection of cutting plane pairs that do not improve the lp solution, but only increase the number of cuts
27   	 *  in the lp.
28   	 *
29   	 *  The selector allows the user to specify a filtering strategy during cut selection ('d'ynamic- and 'f'ull dynamic),
30   	 *  which determines how the orthogonality filtering is applied.
31   	 *  In both cases, after a cut is selected, the remaining cuts are resorted by computing their relative efficacy to the
32   	 *  selected cut. The efficacy ratio is then used to filter the cuts based on the filtering strategy:
33   	 *  - 'd'ynamic-parallelism: The dynamic parallelism strategy filters cuts based on the efficacy ratio between cut
34   	 *  pairs. It only filters cuts that are not theoretically improving the efficacy of the pair given the first cut, i.e.,
35   	 *  the efficacy ratio is below the minimum efficacy gain in percentage, without calculating or resorting the cut array.
36   	 *
37   	 *  - 'f'ull dynamic parallelism: The full dynamic parallelism strategy filters cuts based on the efficacy ratio between
38   	 *  cut pairs by iteratively recomputing the score given the previously selected cut. This results in a set of cuts
39   	 *  that is a sequence of theoretically most effective almost orthogonal cuts, whereby almost orthogonal means that
40   	 *  the efficacy ratio is above the minimum efficacy gain in percentage.
41   	 */
42   	
43   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44   	
45   	#ifndef __SCIP_CUTSEL_DYNAMIC_H__
46   	#define __SCIP_CUTSEL_DYNAMIC_H__
47   	
48   	
49   	#include "scip/scip.h"
50   	
51   	#ifdef __cplusplus
52   	extern "C" {
53   	#endif
54   	
55   	/** creates the dynamic hybrid separator and includes it in SCIP
56   	 *
57   	 * @ingroup CutSelectorIncludes
58   	 */
59   	SCIP_EXPORT
60   	SCIP_RETCODE SCIPincludeCutselDynamic(
61   	   SCIP*                 scip                /**< SCIP data structure */
62   	   );
63   	
64   	/**@addtogroup CUTSELECTORS
65   	 *
66   	 * @{
67   	 */
68   	
69   	/** perform a cut selection algorithm for the given array of cuts
70   	 *
71   	 *  This is an extension of the hybrid cutselector to employ a dynamic range
72   	 *  when applying orthogonality filtering, dependent on the efficacy ratio between cuts.
73   	 *
74   	 *  The input cuts array should be resorted such that the selected cuts come first.
75   	 */
76   	SCIP_EXPORT
77   	SCIP_RETCODE SCIPselectCutsDynamic(
78   	    SCIP*                 scip,               /**< SCIP data structure */
79   	    SCIP_ROW**            cuts,               /**< array with cuts to perform selection algorithm */
80   	    SCIP_ROW**            forcedcuts,         /**< array with forced cuts */
81   	    SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator for tie-breaking, or NULL */
82   	    char                  filtermode,         /**< filtering strategy during cut selection (
83   	                                              *  'd'ynamic- and 'f'ull dynamic parallelism) */
84   	    SCIP_Real             mingain,            /**< minimum efficacy gain in percentage to filter cuts */
85   	    SCIP_Real             maxparall,          /**< maximal parallelism for all cuts that are not good */
86   	    SCIP_Real             dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
87   	    SCIP_Real             efficacyweight,     /**< weight of efficacy in cut score calculation */
88   	    SCIP_Real             objparalweight,     /**< weight of objective parallelism in cut score calculation */
89   	    SCIP_Real             intsupportweight,   /**< weight of integral support in cut score calculation */
90   	    int                   ncuts,              /**< number of cuts in cuts array */
91   	    int                   nforcedcuts,        /**< number of forced cuts */
92   	    int                   maxselectedcuts,    /**< maximal number of cuts from cuts array to select */
93   	    int*                  nselectedcuts      /**< pointer to return number of selected cuts from cuts array */
94   	  );
95   	
96   	/** @} */
97   	
98   	#ifdef __cplusplus
99   	}
100  	#endif
101  	
102  	#endif
103