branch_empty.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program                         */
/*          GCG --- Generic Column Generation                                */
/*                  a Dantzig-Wolfe decomposition based extension            */
/*                  of the branch-cut-and-price framework                    */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University       */
/*                         Zuse Institute Berlin (ZIB)                       */
/*                                                                           */
/* This program is free software; you can redistribute it and/or             */
/* modify it under the terms of the GNU Lesser General Public License        */
/* as published by the Free Software Foundation; either version 3            */
/* of the License, or (at your option) any later version.                    */
/*                                                                           */
/* This program is distributed in the hope that it will be useful,           */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of            */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             */
/* GNU Lesser General Public License for more details.                       */
/*                                                                           */
/* You should have received a copy of the GNU Lesser General Public License  */
/* along with this program; if not, write to the Free Software               */
/* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   branch_empty.c
 * @brief  branching rule for the original problem while real branching is applied in the master
 * @author Marcel Schmickerath
 * @author Martin Bergner
 * @author Christian Puchert
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
/*#define SCIP_DEBUG*/
#include <assert.h>
#include <string.h>
 
#include "branch_empty.h"
#include "relax_gcg.h"
#include "gcg.h"
#include "branch_orig.h"
#include "cons_masterbranch.h"
#include "cons_origbranch.h"
#include "scip/branch_allfullstrong.h"
#include "scip/branch_fullstrong.h"
#include "scip/branch_inference.h"
#include "scip/branch_mostinf.h"
#include "scip/branch_leastinf.h"
#include "scip/branch_pscost.h"
#include "scip/branch_random.h"
#include "scip/branch_relpscost.h"
#include "scip/cons_varbound.h"
#include "type_branchgcg.h"
 
#define BRANCHRULE_NAME          "empty"
#define BRANCHRULE_DESC          "branching rule for the original problem while real branching is applied in the master"
#define BRANCHRULE_PRIORITY      1000000
#define BRANCHRULE_MAXDEPTH      -1
#define BRANCHRULE_MAXBOUNDDIST  1.0
 
 
/*
 * Callback methods for enforcing branching constraints
 */
 
/** copy default SCIP branching rules in order to solve restrictions of the original problem as a subSCIP without
 *  Dantzig-Wolfe decomposition
 */
static
SCIP_RETCODE includeSCIPBranchingRules(
   SCIP*                 scip
)
{
   assert(scip != NULL);
 
   SCIP_CALL( SCIPincludeBranchruleAllfullstrong(scip) );
   SCIP_CALL( SCIPincludeBranchruleFullstrong(scip) );
   SCIP_CALL( SCIPincludeBranchruleInference(scip) );
   SCIP_CALL( SCIPincludeBranchruleMostinf(scip) );
   SCIP_CALL( SCIPincludeBranchruleLeastinf(scip) );
   SCIP_CALL( SCIPincludeBranchrulePscost(scip) );
   SCIP_CALL( SCIPincludeBranchruleRandom(scip) );
   SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
 
   return SCIP_OKAY;
}
 
/** for a new branch-and-bound node on the master problem
 *  add an original branching constraint that holds the branching decision to the corresponding node in the original problem
 */
static
SCIP_RETCODE createOrigbranchConstraint(
   SCIP*                 scip,
   SCIP_NODE*            childnode,
   SCIP_CONS*            masterbranchchildcons
)
{
   char* consname;
   SCIP_BRANCHRULE* branchrule;
   GCG_BRANCHDATA* branchdata;
   SCIP_CONS* origcons;
   SCIP_CONS** origbranchconss;
   int norigbranchconss;
 
   int i;
 
   assert(scip != NULL);
   assert(masterbranchchildcons != NULL);
 
   /* get name and branching information from the corresponding masterbranch constraint */
   consname = GCGconsMasterbranchGetName(masterbranchchildcons);
   branchrule = GCGconsMasterbranchGetBranchrule(masterbranchchildcons);
   branchdata = GCGconsMasterbranchGetBranchdata(masterbranchchildcons);
 
   /* create an origbranch constraint and add it to the node */
   SCIPdebugMessage("Create original branching constraint %s\n", consname);
   SCIP_CALL( GCGcreateConsOrigbranch(scip, &origcons, consname, childnode,
            GCGconsOrigbranchGetActiveCons(scip), branchrule, branchdata) );
   if( branchdata == NULL )
   {
      SCIPdebugMessage("origbranch with no branchdata created\n");
   }
   SCIP_CALL( SCIPaddConsNode(scip, childnode, origcons, NULL) );
 
   /* add those constraints to the node that enforce the branching decision in the original problem */
   origbranchconss = GCGconsMasterbranchGetOrigbranchConss(masterbranchchildcons);
   norigbranchconss = GCGconsMasterbranchGetNOrigbranchConss(masterbranchchildcons);
   for( i = 0; i < norigbranchconss; ++i )
   {
      SCIP_CALL( SCIPaddConsNode(scip, childnode, origbranchconss[i], NULL) );
   }
 
   /* notify the original and master branching constraint about each other */
   GCGconsOrigbranchSetMastercons(origcons, masterbranchchildcons);
   GCGconsMasterbranchSetOrigcons(masterbranchchildcons, origcons);
 
   SCIP_CALL( SCIPreleaseCons(scip, &origcons) );
 
   /* release array of original branching constraints */
   SCIP_CALL( GCGconsMasterbranchReleaseOrigbranchConss(GCGgetMasterprob(scip), scip, masterbranchchildcons) );
 
   return SCIP_OKAY;
}
 
/* apply a branching decision on the original variables to the corresponding node */
static
SCIP_RETCODE applyOriginalBranching(
   SCIP*                 scip,
   SCIP_NODE*            childnode,
   SCIP_CONS*            masterbranchchildcons
   )
{
   GCG_BRANCHDATA* branchdata;
   SCIP_VAR* boundvar;
   GCG_BOUNDTYPE boundtype;
   SCIP_Real newbound;
 
   /* get branching decision */
   branchdata = GCGconsMasterbranchGetBranchdata(masterbranchchildcons);
   assert(branchdata != NULL);
   boundvar = GCGbranchOrigGetOrigvar(branchdata);
   boundtype = GCGbranchOrigGetBoundtype(branchdata);
   newbound = GCGbranchOrigGetNewbound(branchdata);
 
   assert(boundvar != NULL);
   assert(boundtype == GCG_BOUNDTYPE_LOWER || boundtype == GCG_BOUNDTYPE_UPPER || boundtype == GCG_BOUNDTYPE_FIXED);
 
   if( boundtype == GCG_BOUNDTYPE_LOWER || boundtype == GCG_BOUNDTYPE_FIXED )
   {
      SCIP_CALL( SCIPchgVarLbNode(scip, childnode, boundvar, newbound) );
   }
 
   if( boundtype == GCG_BOUNDTYPE_UPPER || boundtype == GCG_BOUNDTYPE_FIXED )
   {
      SCIP_CALL( SCIPchgVarUbNode(scip, childnode, boundvar, newbound) );
   }
 
   if( GCGvarGetBlock(boundvar) == -1 )
   {
      SCIP_CALL( GCGconsMasterbranchAddCopiedVarBndchg(GCGgetMasterprob(scip), masterbranchchildcons,
         boundvar, boundtype, newbound) );
   }
 
   return SCIP_OKAY;
}
 
/** creates branch-and-bound nodes in the original problem corresponding to those in the master problem */
static
SCIP_RETCODE createBranchNodesInOrigprob(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_RESULT*          result              /**< result pointer */
)
{
   SCIP* masterscip;
   SCIP_BRANCHRULE* branchrule;
   SCIP_CONS* masterbranchcons;
   int nchildnodes;
   SCIP_Bool enforcebycons;
 
   int i;
 
   assert(scip != NULL);
   assert(result != NULL);
 
   *result = SCIP_DIDNOTRUN;
 
   /* get master problem */
   masterscip = GCGgetMasterprob(scip);
   assert(masterscip != NULL);
 
   /* get masterbranch constraint at the current node */
   masterbranchcons = GCGconsMasterbranchGetActiveCons(masterscip);
 
   /* @todo: Why should this happen? */
   if( masterbranchcons == NULL )
      return SCIP_OKAY;
 
   /* get the children of the current node */
   nchildnodes = GCGconsMasterbranchGetNChildconss(masterbranchcons);
 
   /* check if the focus node of the master problem has children */
   if( nchildnodes <= 0 && SCIPgetStage(masterscip) != SCIP_STAGE_SOLVED && SCIPgetNChildren(masterscip) >= 1 )
   {
      SCIP_NODE* child;
 
      SCIPdebugMessage("create dummy child in origprob, because there is also a child in the master\n");
 
      /* create dummy child */
      SCIP_CALL( SCIPcreateChild(scip, &child, 0.0, SCIPgetLocalTransEstimate(scip)) );
 
      *result = SCIP_BRANCHED;
      return SCIP_OKAY;
   }
 
   if( nchildnodes <= 0 )
   {
      SCIPdebugMessage("node cut off, since there is no successor node\n");
 
      *result = SCIP_CUTOFF;
      return SCIP_OKAY;
   }
 
   SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/enforcebycons", &enforcebycons) );
 
   /* for each child, create a corresponding node in the original problem as well as an origbranch constraint */
   for( i = 0; i < nchildnodes; ++i )
   {
      SCIP_NODE* childnode;
      SCIP_CONS* masterbranchchildcons = GCGconsMasterbranchGetChildcons(masterbranchcons, i);
      assert(masterbranchchildcons != NULL);
 
      /* create a child node and an origbranch constraint holding the branching decision */
      SCIP_CALL( SCIPcreateChild(scip, &childnode, 0.0, SCIPgetLocalTransEstimate(scip)) );
      SCIP_CALL( createOrigbranchConstraint(scip, childnode, masterbranchchildcons) );
 
      /* get branching rule */
      branchrule = GCGconsMasterbranchGetBranchrule(masterbranchchildcons);
 
      /* If a branching decision on an original variable was made, apply it */
      if( !enforcebycons && branchrule != NULL && strcmp(SCIPbranchruleGetName(branchrule), "orig") == 0 )
      {
         SCIP_CALL( applyOriginalBranching(scip, childnode, masterbranchchildcons) );
      }
 
      /* @fixme: this should actually be an assertion */
      if( SCIPnodeGetNumber(GCGconsOrigbranchGetNode(GCGconsOrigbranchGetActiveCons(scip))) != SCIPnodeGetNumber(GCGconsMasterbranchGetNode(GCGconsMasterbranchGetActiveCons(GCGgetMasterprob(scip)))) )
      {
   #ifdef SCIP_DEBUG
         SCIPwarningMessage(scip, "norignodes = %lld; nmasternodes = %lld\n",
            SCIPnodeGetNumber(GCGconsOrigbranchGetNode(GCGconsOrigbranchGetActiveCons(scip))),
            SCIPnodeGetNumber(GCGconsMasterbranchGetNode(GCGconsMasterbranchGetActiveCons(GCGgetMasterprob(scip)))));
   #endif
      }
   }
 
   *result = SCIP_BRANCHED;
 
   assert(nchildnodes > 0);
 
   return SCIP_OKAY;
}
 
 
/** copy method for empty branching rule */
static
SCIP_DECL_BRANCHCOPY(branchCopyEmpty)
{
   assert(branchrule != NULL);
   assert(scip != NULL);
 
   /* SubSCIPs are solved with SCIP rather than GCG;
    * therefore, only the default SCIP branching rules are included into the subSCIP.
    */
   SCIP_CALL( includeSCIPBranchingRules(scip) );
 
   return SCIP_OKAY;
}
 
/** destructor of branching rule to free user data (called when SCIP is exiting) */
#define branchFreeEmpty NULL
 
/** initialization method of branching rule (called after problem was transformed) */
#define branchInitEmpty NULL
 
/** deinitialization method of branching rule (called before transformed problem is freed) */
#define branchExitEmpty NULL
 
/** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
#define branchInitsolEmpty NULL
 
/** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
#define branchExitsolEmpty NULL
 
/** branching execution method for fractional LP solutions */
static
SCIP_DECL_BRANCHEXECLP(branchExeclpEmpty)
{  /*lint --e{715}*/
   assert(branchrule != NULL);
   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
   assert(scip != NULL);
   assert(result != NULL);
 
   SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
 
   return SCIP_OKAY;
}
 
/** branching execution method relaxation solutions */
static
SCIP_DECL_BRANCHEXECEXT(branchExecextEmpty)
{  /*lint --e{715}*/
   assert(branchrule != NULL);
   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
   assert(scip != NULL);
   assert(result != NULL);
 
   SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
 
   return SCIP_OKAY;
}
 
/** branching execution method for not completely fixed pseudo solutions */
static
SCIP_DECL_BRANCHEXECPS(branchExecpsEmpty)
{  /*lint --e{715}*/
   assert(branchrule != NULL);
   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
   assert(scip != NULL);
   assert(result != NULL);
 
   SCIP_CALL( createBranchNodesInOrigprob(scip, result) );
 
   return SCIP_OKAY;
}
 
 
/*
 * branching specific interface methods
 */
 
/** creates the empty branching rule and includes it in SCIP */
SCIP_RETCODE SCIPincludeBranchruleEmpty(
   SCIP*                 scip                /**< SCIP data structure */
)
{
   SCIP_BRANCHRULEDATA* branchruledata;
 
   /* create inference branching rule data */
   branchruledata = NULL;
 
   /* include branching rule */
   SCIP_CALL( SCIPincludeBranchrule(scip, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
      BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST,
      branchCopyEmpty, branchFreeEmpty, branchInitEmpty, branchExitEmpty, branchInitsolEmpty,
      branchExitsolEmpty, branchExeclpEmpty, branchExecextEmpty, branchExecpsEmpty,
      branchruledata) );
 
   return SCIP_OKAY;
}