1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 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 /**@file branch_stp.h 16 * @brief Steiner vertex branching rule 17 * @author Daniel Rehfeldt 18 * 19 * The Steiner branching rule implemented in this file is described in 20 * "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt. 21 * It removes includes and exludes Steiner vertices during branching. 22 * 23 */ 24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 25 26 #ifndef __SCIP_BRANCH_STP_H__ 27 #define __SCIP_BRANCH_STP_H__ 28 29 30 #include "scip/scip.h" 31 32 #ifdef __cplusplus 33 extern "C" { 34 #endif 35 36 #define BRANCH_STP_VERTEX_KILLED -1 37 #define BRANCH_STP_VERTEX_NONTERM 0 38 #define BRANCH_STP_VERTEX_TERM 1 39 40 41 /** parse constraint name and apply changes to graph or array */ 42 SCIP_RETCODE STPStpBranchruleParseConsname( 43 SCIP* scip, /**< SCIP data structure */ 44 int* vertexchgs, /**< array to store changes or NULL */ 45 GRAPH* graph, /**< graph to modify or NULL */ 46 const char* consname, /**< constraint name */ 47 SCIP_Bool deletehistory /**< delete history of graph? */ 48 ); 49 50 /** applies vertex changes caused by this branching rule, either on a graph or on an array */ 51 SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs( 52 SCIP* scip, /**< SCIP data structure */ 53 int* vertexchgs, /**< array to store changes or NULL */ 54 GRAPH* graph /**< graph to apply changes on or NULL */ 55 ); 56 57 /** applies vertex changes caused by this branching rule, either on a graph or on an array */ 58 void SCIPStpBranchruleInitNodeState( 59 const GRAPH* g, /**< graph data structure */ 60 int* nodestate /**< node state array */ 61 ); 62 63 /** creates the stp branching rule and includes it to SCIP */ 64 SCIP_RETCODE SCIPincludeBranchruleStp( 65 SCIP* scip /**< SCIP data structure */ 66 ); 67 68 #ifdef __cplusplus 69 } 70 #endif 71 72 #endif 73