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   heuristics.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  methods commonly used by primal heuristics
28   	 * @author Gregor Hendel
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_HEURISTICS_H__
34   	#define __SCIP_HEURISTICS_H__
35   	
36   	#include "scip/def.h"
37   	#include "scip/type_scip.h"
38   	#include "scip/type_heur.h"
39   	#include "scip/type_misc.h"
40   	#include "scip/type_retcode.h"
41   	#include "scip/type_sol.h"
42   	#include "scip/type_var.h"
43   	
44   	#ifdef __cplusplus
45   	extern "C" {
46   	#endif
47   	
48   	/**@defgroup PublicSpecialHeuristicMethods Special Methods
49   	 * @ingroup PublicHeuristicMethods
50   	 * @brief  methods commonly used by primal heuristics
51   	 *
52   	 * @{
53   	 */
54   	
55   	/** performs a diving within the limits of the @p diveset parameters
56   	 *
57   	 *  This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
58   	 *  name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
59   	 *  is applied at every node in the tree, whereas probing LPs might be solved less frequently.
60   	 *
61   	 *  Starting from the current LP solution, the algorithm selects candidates which maximize the
62   	 *  score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
63   	 *  and propagates the bound change on this candidate.
64   	 *
65   	 *  The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
66   	 *  or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
67   	 *  or the last node is proven to be infeasible. It optionally backtracks and tries the
68   	 *  other branching direction.
69   	 *
70   	 *  After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
71   	 *  solved, and the old candidates are replaced by the new LP candidates.
72   	 *
73   	 *  @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
74   	 *
75   	 *  @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
76   	 *        is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
77   	 *
78   	 *  @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
79   	 *        call will be executed, @see SCIPgetLastDiveNode().
80   	 */
81   	SCIP_EXPORT
82   	SCIP_RETCODE SCIPperformGenericDivingAlgorithm(
83   	   SCIP*                 scip,               /**< SCIP data structure */
84   	   SCIP_DIVESET*         diveset,            /**< settings for diving */
85   	   SCIP_SOL*             worksol,            /**< non-NULL working solution */
86   	   SCIP_HEUR*            heur,               /**< the calling primal heuristic */
87   	   SCIP_RESULT*          result,             /**< SCIP result pointer */
88   	   SCIP_Bool             nodeinfeasible,     /**< is the current node known to be infeasible? */
89   	   SCIP_Longint          iterlim,            /**< nonnegative iteration limit for the LP solves, or -1 for dynamic setting */
90   	   int                   nodelimit,          /**< nonnegative probing node limit or -1 if no limit should be used */
91   	   SCIP_Real             lpresolvedomchgquot, /**< percentage of immediate domain changes during probing to trigger LP resolve or -1
92   	                                                   if diveset specific default should be used */
93   	   SCIP_DIVECONTEXT      divecontext         /**< context for diving statistics */
94   	   );
95   	
96   	/** get a sub-SCIP copy of the transformed problem */
97   	SCIP_EXPORT
98   	SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(
99   	   SCIP*                 sourcescip,         /**< source SCIP data structure */
100  	   SCIP*                 subscip,            /**< sub-SCIP used by the heuristic */
101  	   SCIP_HASHMAP*         varmap,             /**< a hashmap to store the mapping of source variables to the corresponding
102  	                                              *   target variables */
103  	   const char*           suffix,             /**< suffix for the problem name */
104  	   SCIP_VAR**            fixedvars,          /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
105  	   SCIP_Real*            fixedvals,          /**< array of fixing values for target SCIP variables, or NULL */
106  	   int                   nfixedvars,         /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
107  	   SCIP_Bool             uselprows,          /**< should the linear relaxation of the problem defined by LP rows be copied? */
108  	   SCIP_Bool             copycuts,           /**< should cuts be copied (only if uselprows == FALSE) */
109  	   SCIP_Bool*            success,            /**< was the copying successful? */
110  	   SCIP_Bool*            valid               /**< pointer to store whether the copying was valid, or NULL */
111  	   );
112  	
113  	/** adds a trust region neighborhood constraint to the @p targetscip
114  	 *
115  	 *  a trust region constraint measures the deviation from the current incumbent solution \f$x^*\f$ by an auxiliary
116  	 *  continuous variable \f$v \geq 0\f$:
117  	 *  \f[
118  	 *    \sum\limits_{j\in B} |x_j^* - x_j| = v
119  	 *  \f]
120  	 *  Only binary variables are taken into account. The deviation is penalized in the objective function using
121  	 *  a positive \p violpenalty.
122  	 *
123  	 *  @note: the trust region constraint creates an auxiliary variable to penalize the deviation from
124  	 *  the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name
125  	 *  'trustregion_violationvar'
126  	 */
127  	SCIP_EXPORT
128  	SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(
129  	   SCIP*                 scip,               /**< the SCIP data structure */
130  	   SCIP*                 subscip,            /**< SCIP data structure of the subproblem */
131  	   SCIP_VAR**            subvars,            /**< variables of the subproblem, NULL entries are ignored */
132  	   SCIP_Real             violpenalty         /**< the penalty for violating the trust region */
133  	   );
134  	
135  	/** @} */
136  	
137  	#ifdef __cplusplus
138  	}
139  	#endif
140  	
141  	#endif
142