branch_multinode.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   branch_multinode.c
 * @brief  mutlinode branching rule for the set-partitioning part in cycle clustering application.
 * @author Leon Eifler
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
#include <assert.h>
 
#include "branch_multinode.h"
 
#include "probdata_cyc.h"
#include "scip/branch_relpscost.h"
 
 
#define BRANCHRULE_NAME            "multinode"
#define BRANCHRULE_DESC            "multinode branching creates a child for every variable of a setpartitioning constraint"
#define BRANCHRULE_PRIORITY        10000000
#define BRANCHRULE_MAXDEPTH        -1
#define BRANCHRULE_MAXBOUNDDIST    1.0
 
/*
 * Local methods
 */
 
/* put your local methods here, and declare them static */
 
/** get the branching candidates viable for multinode branching */
static
SCIP_RETCODE getBranchCands(
   SCIP*                 scip,               /**< SCIP data structure */
   SCIP_VAR**            branchcands,        /**< the address of the branching candidates */
   SCIP_Real*            branchcandssol,     /**< pointer to solution values of the candidates */
   SCIP_Real*            branchcandsfrac,    /**< pointer to fractionalities of the candidates */
   int*                  ncands              /**< number of branching candidates */
   )
{
   SCIP_VAR*** binvars;
   int nbins;
   int ncluster;
   int i;
   int k;
 
   nbins = SCIPcycGetNBins(scip);
   ncluster = SCIPcycGetNCluster(scip);
   binvars = SCIPcycGetBinvars(scip);
 
   /* all binvars that are in the lp, and have fractional values are viable candidates */
   for( i = 0; i < nbins; ++i )
   {
      for( k = 0; k < ncluster; ++k )
      {
         if( SCIPvarGetStatus(binvars[i][k]) ==  SCIP_VARSTATUS_COLUMN
            && !SCIPisFeasIntegral(scip, SCIPvarGetLPSol(binvars[i][k])) )
         {
            (branchcands)[*ncands] = binvars[i][k];
            (branchcandssol)[*ncands] = SCIPvarGetLPSol(binvars[i][k]);
            (branchcandsfrac)[*ncands] = MAX(1-(branchcandssol)[*ncands], (branchcandssol)[*ncands]);
            (*ncands)++;
         }
      }
   }
 
   return SCIP_OKAY;
}
 
/** branch on a selected bin -> Create at most |Cluster| children */
static
SCIP_RETCODE branchOnBin(
   SCIP*                 scip,               /**< SCIP data structure */
   int                   row,                /**< the row in the binvar-matrix (not lp-row) to be branched on */
   SCIP_RESULT*          result              /**< pointer to store result of branching */
   )
{
   SCIP_VAR*** binvars;
   SCIP_Bool* branched;
   SCIP_Real priority;
   SCIP_Real estimate;
   SCIP_Real minestzero = SCIP_INVALID;
   SCIP_Real tmp;
   SCIP_NODE* node;
   int ncands = 0;
   int k;
   int ncluster;
 
   binvars = SCIPcycGetBinvars(scip);
   ncluster = SCIPcycGetNCluster(scip);
   assert(NULL != binvars[row]);
 
   SCIP_CALL( SCIPallocClearBufferArray(scip, &branched, ncluster) );
 
   /* check all candidates */
   for( k = 0; k < ncluster; ++k )
   {
      if( (SCIPvarGetStatus(binvars[row][k]) == SCIP_VARSTATUS_LOOSE ||
         SCIPvarGetStatus(binvars[row][k]) == SCIP_VARSTATUS_COLUMN) &&
         !SCIPisZero(scip, SCIPvarGetLPSol(binvars[row][k])) && !SCIPisEQ(scip, SCIPvarGetLPSol(binvars[row][k]), 1.0) )
      {
         ncands++;
         priority = SCIPcalcNodeselPriority(scip, binvars[row][k], SCIP_BRANCHDIR_UPWARDS, 1.0);
         estimate = SCIPcalcChildEstimate(scip, binvars[row][k], 1.0);
         tmp = SCIPcalcChildEstimate(scip, binvars[row][k], 0.0);
         minestzero = MIN(tmp, minestzero);
 
         /* branch all viable candidates upwards */
         SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) );
         SCIP_CALL( SCIPchgVarLbNode(scip, node, binvars[row][k], 1.0) );
 
         branched[k] = TRUE;
 
         *result = SCIP_BRANCHED;
         if( ncands > 2 )
            break;
      }
   }
 
   /* create one child, were all the before upwards branched variables are now set to 0. Only do so if at least one
    * upwards branching was done and if not all the variables were branched upwards
    */
   if( ncands > 0 && ncands < ncluster )
   {
      SCIP_CALL( SCIPcreateChild(scip, &node, (SCIP_Real)ncands, minestzero) );
      for( k = 0; k < ncluster; ++k )
      {
         if( branched[k] )
         {
            SCIP_CALL( SCIPchgVarUbNode(scip, node, binvars[row][k], 0.0) );
         }
      }
   }
 
   SCIPfreeBufferArray(scip, &branched);
 
   return SCIP_OKAY;
}
 
/*
 * Callback methods of branching rule
 */
 
/** branching execution method for fractional LP solutions */
static
SCIP_DECL_BRANCHEXECLP(branchExeclpMultinode)
{  /*lint --e{715}*/
   int i;
   int k;
   int nbins;
   int ncluster;
   int ncands;
 
   SCIP_Real* score;
   SCIP_Real max;
   int maxrow;
   SCIP_VAR*** binvars;
   SCIP_VAR** branchcands;
   SCIP_Real* branchcandssol;
   SCIP_Real* branchcandsfrac;
 
   binvars = SCIPcycGetBinvars(scip);
   nbins = SCIPcycGetNBins(scip);
   ncluster = SCIPcycGetNCluster(scip);
   *result = SCIP_DIDNOTRUN;
 
   assert(nbins > 0);
   assert(ncluster > 0 && ncluster <= nbins);
 
   SCIP_CALL( SCIPallocClearBufferArray(scip, &score, nbins) );
   SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcands, (SCIP_Longint) nbins * ncluster) );
   SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcandssol, (SCIP_Longint) nbins * ncluster) );
   SCIP_CALL( SCIPallocClearBufferArray(scip, &branchcandsfrac, (SCIP_Longint) nbins * ncluster) );
 
   ncands = 0;
   /* get the candidates */
   SCIP_CALL( getBranchCands( scip, branchcands, branchcandssol, branchcandsfrac, &ncands) );
   if( ncands != 0 )
   {
      /* compute the relpcost for the candidates */
      SCIP_CALL( SCIPexecRelpscostBranching(scip, branchcands, branchcandssol, branchcandsfrac, ncands, FALSE,  result) );
 
      assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM);
 
      if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM )
      {
         maxrow = -1;
         max = -SCIPinfinity(scip);
 
         /* compute the best candidate from pseudocostscore */
         for( i = 0; i < nbins; ++i )
         {
            score[i] = 0;
 
            for( k = 0; k < ncluster; ++k )
            {
               /* Do not branch on variables that are already fixed locally */
               if( SCIPisEQ(scip, SCIPvarGetUbLocal(binvars[i][k]), SCIPvarGetLbLocal(binvars[i][k])) )
               {
                  score[i] = -SCIPinfinity(scip);
                  break;
               }
 
               if( SCIPvarGetStatus(binvars[i][k]) == SCIP_VARSTATUS_COLUMN &&
                  !SCIPisZero(scip, SCIPvarGetLPSol(binvars[i][k])) &&
                  !SCIPisEQ(scip, SCIPvarGetLPSol(binvars[i][k]), 1.0) )
               {
                  score[i] += SCIPgetVarPseudocostScore(scip, binvars[i][k], SCIPvarGetLPSol(binvars[i][k]));
               }
            }
 
            if( SCIPisLT(scip, max, score[i]) && !SCIPisInfinity(scip, -score[i]) )
            {
               max = score[i];
               maxrow = i;
            }
         }
 
         if( -1 != maxrow )
         {
            SCIP_CALL( branchOnBin(scip, maxrow, result) );
         }
      }
   }
 
   /* free memory */
   SCIPfreeBufferArray(scip, &score);
   SCIPfreeBufferArray(scip, &branchcands);
   SCIPfreeBufferArray(scip, &branchcandssol);
   SCIPfreeBufferArray(scip, &branchcandsfrac);
 
   return SCIP_OKAY;
}
 
/*
 * branching rule specific interface methods
 */
 
/** creates the mutlinode branching rule and includes it in SCIP */
SCIP_RETCODE SCIPincludeBranchruleMultinode(
   SCIP*                 scip                /**< SCIP data structure */
   )
{
   SCIP_BRANCHRULEDATA* branchruledata;
   SCIP_BRANCHRULE* branchrule;
 
   branchruledata = NULL;
 
   /* include branching rule */
   /* use SCIPincludeBranchruleBasic() plus setter functions if you want to set callbacks one-by-one
    * and your code should compile independent of new callbacks being added in future SCIP versions
    */
   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
      BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
 
   assert(branchrule != NULL);
 
   /* set non fundamental callbacks via setter functions */
   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMultinode) );
 
   return SCIP_OKAY;
}