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 branch_fullstrong.h 26 * @ingroup BRANCHINGRULES 27 * @brief full strong LP branching rule 28 * @author Tobias Achterberg 29 * 30 * The full strong branching rule applies strong branching to every fractional variable of the LP solution 31 * at the current node of the branch-and-bound search. The rule selects the candidate 32 * which will cause the highest gain of the dual bound in the created sub-tree among all branching variables. 33 * 34 * For calculating the gain, a look-ahead is performed by solving the child node LPs which will result 35 * from branching on a variable. 36 * 37 * For a more mathematical description and a comparison between the strong branching rule and other branching rules 38 * in SCIP, we refer to 39 * 40 * @par 41 * Tobias Achterberg@n 42 * Constraint Integer Programming@n 43 * PhD Thesis, Technische Universität Berlin, 2007@n 44 * 45 * 46 */ 47 48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 49 50 #ifndef __SCIP_BRANCH_FULLSTRONG_H__ 51 #define __SCIP_BRANCH_FULLSTRONG_H__ 52 53 54 #include "scip/def.h" 55 #include "scip/type_result.h" 56 #include "scip/type_retcode.h" 57 #include "scip/type_scip.h" 58 #include "scip/type_var.h" 59 60 #ifdef __cplusplus 61 extern "C" { 62 #endif 63 64 /** creates the full strong LP branching rule and includes it in SCIP 65 * 66 * @ingroup BranchingRuleIncludes 67 */ 68 SCIP_EXPORT 69 SCIP_RETCODE SCIPincludeBranchruleFullstrong( 70 SCIP* scip /**< SCIP data structure */ 71 ); 72 73 /**@addtogroup BRANCHINGRULES 74 * 75 * @{ 76 */ 77 78 /** 79 * Selects a variable from a set of candidates by strong branching 80 * 81 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 82 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 83 * 84 * @note The variables in the lpcands array must have a fractional value in the current LP solution 85 */ 86 SCIP_EXPORT 87 SCIP_RETCODE SCIPselectVarStrongBranching( 88 SCIP* scip, /**< original SCIP data structure */ 89 SCIP_VAR** lpcands, /**< branching candidates */ 90 SCIP_Real* lpcandssol, /**< solution values of the branching candidates */ 91 SCIP_Real* lpcandsfrac, /**< fractional values of the branching candidates */ 92 SCIP_Bool* skipdown, /**< should down branchings be skipped? */ 93 SCIP_Bool* skipup, /**< should up branchings be skipped? */ 94 int nlpcands, /**< number of branching candidates */ 95 int npriolpcands, /**< number of priority branching candidates */ 96 int ncomplete, /**< number of branching candidates without skip */ 97 int* start, /**< starting index in lpcands */ 98 int maxproprounds, /**< maximum number of propagation rounds to be performed during strong 99 * branching before solving the LP (-1: no limit, -2: parameter settings) */ 100 SCIP_Bool probingbounds, /**< should valid bounds be identified in a probing-like fashion during 101 * strong branching (only with propagation)? */ 102 SCIP_Bool forcestrongbranch, /**< should strong branching be applied even if there is just a single candidate? */ 103 int* bestcand, /**< best candidate for branching */ 104 SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */ 105 SCIP_Real* bestup, /**< objective value of the up branch for bestcand */ 106 SCIP_Real* bestscore, /**< score for bestcand */ 107 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */ 108 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */ 109 SCIP_Real* provedbound, /**< proved dual bound for current subtree */ 110 SCIP_RESULT* result /**< result pointer */ 111 ); 112 113 /** @} */ 114 115 #ifdef __cplusplus 116 } 117 #endif 118 119 #endif 120