prop_sdpredcost.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/* This file is part of SCIPSDP - a solving framework for mixed-integer      */
/* semidefinite programs based on SCIP.                                      */
/*                                                                           */
/* Copyright (C) 2011-2013 Discrete Optimization, TU Darmstadt               */
/*                         EDOM, FAU Erlangen-Nürnberg                       */
/*               2014-2021 Discrete Optimization, TU Darmstadt               */
/*                                                                           */
/*                                                                           */
/* 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.*/
/*                                                                           */
/*                                                                           */
/* Based on SCIP - Solving Constraint Integer Programs                       */
/* Copyright (C) 2002-2021 Zuse Institute Berlin                             */
/* SCIP is distributed under the terms of the SCIP Academic Licence,         */
/* see file COPYING in the SCIP distribution.                                */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*#define SCIP_DEBUG*/

/* TODO: might want to add sdpsolvergaptol to parameters and only cut off / change bounds if values differ by more than gaptol, since
 * the primal variable values may only be exact up to gaptol
 */

#include "prop_sdpredcost.h"
#include "scip/def.h"                        /* for SCIP_Real, _Bool, ... */
#include "relax_sdp.h"                       /* to get relaxation value */
#include "sdpi/sdpi.h"                       /* to get values of primal variables */

#include <string.h>
#include <assert.h>                          /*lint !e451*/

/* turn off lint warnings for whole file: */
/*lint --e{788,818}*/

#define PROP_NAME                   "sdpredcost"
#define PROP_DESC                   "sdp reduced cost strengthening propagator"
#define PROP_TIMING                 SCIP_PROPTIMING_AFTERLPLOOP
#define PROP_PRIORITY               +1000000 
#define PROP_FREQ                   1        
#define PROP_DELAY                  FALSE    
#define DEFAULT_SDPRCBIN            TRUE     
#define DEFAULT_SDPRCINTCONT        TRUE     
struct SCIP_PropData
{
   /* these could also be freshly allocated for each node, but allocating them only once saves time */
   SCIP_Real*            lbvarvals;          
   SCIP_Real*            ubvarvals;          
   int                   nvars;              
   SCIP_Bool             forbins;            
   SCIP_Bool             forintconts;        
};

static
SCIP_RETCODE sdpRedcostFixingBinary(
   SCIP*                 scip,               
   SCIP_VAR*             var,                
   SCIP_Real             primallbval,        
   SCIP_Real             primalubval,        
   SCIP_Real             cutoffbound,        
   SCIP_Real             relaxval,           
   SCIP_RESULT*          result              
   )
{
   assert( scip != NULL );
   assert( var != NULL );
   assert( result != NULL );
   assert( ! SCIPisInfinity(scip, REALABS(cutoffbound)) );
   assert( ! SCIPisInfinity(scip, REALABS(relaxval)) );
   assert( SCIPisFeasGE(scip, cutoffbound, relaxval) );

   *result = SCIP_DIDNOTFIND;

   /* skip fixed binary variables */
   if ( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
      return SCIP_OKAY;

   /* check if variable can be fixed to zero */
   if ( SCIPisGT(scip, primallbval, cutoffbound - relaxval) )
   {
      SCIPdebugMsg(scip, "Variable <%s> fixed to zero.\n", SCIPvarGetName(var));
      SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
      *result = SCIP_REDUCEDDOM;

      /* check if we would also have to fix the variable to one, in that case, we can cut the node off, as there can't be a new optimal solution */
      if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
         *result = SCIP_CUTOFF;

      return SCIP_OKAY;
   }

   /* check if variable can be fixed to one */
   if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
   {
      SCIPdebugMsg(scip, "Variable <%s> fixed to one.\n", SCIPvarGetName(var));
      SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
      *result = SCIP_REDUCEDDOM;
      return SCIP_OKAY;
   }

   return SCIP_OKAY;
}

static
SCIP_RETCODE sdpRedcostFixingIntCont(
   SCIP*                 scip,               
   SCIP_VAR*             var,                
   SCIP_Real             primallbval,        
   SCIP_Real             primalubval,        
   SCIP_Real             cutoffbound,        
   SCIP_Real             relaxval,           
   SCIP_RESULT*          result              
   )
{
   SCIP_Real oldlb;
   SCIP_Real oldub;
   SCIP_Real newlb;
   SCIP_Real newub;

   assert( scip != NULL );
   assert( var != NULL );
   assert( result != NULL );
   assert( ! SCIPisInfinity(scip, REALABS(cutoffbound)) );
   assert( ! SCIPisInfinity(scip, REALABS(relaxval)) );
   assert( SCIPisFeasGE(scip, cutoffbound, relaxval) );

   *result = SCIP_DIDNOTFIND;

   oldlb = SCIPvarGetLbLocal(var);
   oldub = SCIPvarGetUbLocal(var);
   assert( SCIPisLE(scip, oldlb, oldub) );

   /* avoid fixed variables */
   if ( SCIPisFeasEQ(scip, oldlb, oldub) )
      return SCIP_OKAY;

   /* Compute new lower bound. Avoid division by 0 (checking > 0 is sufficient, as the variables are non-negative). The
    * new lower bound is only valid if the old upper bound is finite. */
   if ( ! SCIPisInfinity(scip, oldub) && SCIPisFeasPositive(scip, primalubval) )
   {
      newlb = oldub - (cutoffbound - relaxval) / primalubval;

      /* take the better value */
      newlb = MAX(oldlb, newlb);
      assert( ! SCIPisInfinity(scip, newlb) );
   }
   else
      newlb = oldlb;

   /* Compute new upper bound. Avoid division by 0 (checking > 0 is sufficient, as the variables are non-negative). The
    * new upper bound is only valid if the old lower bound is finite. */
   if ( ! SCIPisInfinity(scip, -oldlb) && SCIPisFeasPositive(scip, primallbval) )
   {
      newub = oldlb + (cutoffbound - relaxval) / primallbval;

      /* take the better value */
      newub = MIN(oldub, newub);
      assert( ! SCIPisInfinity(scip, -newub) );
   }
   else
      newub = oldub;

   /* check for infeasibility */
   if ( SCIPisFeasGT(scip, newlb, newub) )
   {
      SCIPdebugMsg(scip, "Node is infeasible. New bounds for variable <%s>: [%g, %g]!\n", SCIPvarGetName(var), newlb, newub);
      *result = SCIP_CUTOFF;
      return SCIP_OKAY;
   }

   /* try to tighten lower bound */
   if ( ! SCIPisInfinity(scip, -newlb) && SCIPisFeasGT(scip, newlb, oldlb) )
   {
      SCIPdebugMsg(scip, "Changing lower bound of variable <%s> from %g to %g.\n", SCIPvarGetName(var), oldlb, newlb);
      SCIP_CALL( SCIPchgVarLb(scip, var, newlb) );
      *result = SCIP_REDUCEDDOM;
   }

   /* try to tighten upper bound */
   if ( ! SCIPisInfinity(scip, newub) && SCIPisFeasLT(scip, newub, oldub) )
   {
      SCIPdebugMsg(scip, "Changing upper bound of variable <%s> from %g to %g.\n", SCIPvarGetName(var), oldub, newub);
      SCIP_CALL( SCIPchgVarUb(scip, var, newub) );
      *result = SCIP_REDUCEDDOM;
   }

   return SCIP_OKAY;
}

static
SCIP_DECL_PROPEXEC(propExecSdpredcost)
{/*lint --e{715}*/
   int v;
   int nvars;
   SCIP_VAR** vars;
   SCIP_RELAX* relax;
   SCIP_RESULT varresult;
   SCIP_Real cutoffbound;
   SCIP_Real relaxval;
   SCIP_Bool sdpsolved;
   SCIP_PROPDATA* propdata;
   SCIP_Bool success;

   assert( scip != NULL );
   assert( prop != NULL );
   assert( result != NULL );

   *result = SCIP_DIDNOTRUN;

   /* do not run if propagation w.r.t. objective is not allowed */
   if( ! SCIPallowWeakDualReds(scip) )
      return SCIP_OKAY;

   /* we can't run before the relaxator is properly initialized */
   if ( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
      return SCIP_OKAY;

   cutoffbound = SCIPgetCutoffbound(scip);
   if ( SCIPisInfinity(scip, cutoffbound) )
      return SCIP_OKAY;

   relax = SCIPfindRelax(scip, "SDP"); /* get SDP relaxation handler */
   assert( relax != NULL );

   /* we can only propagate if the SDP was solved in its original formulation */
   if ( ! SCIPrelaxSdpSolvedOrig(relax) )
      return SCIP_OKAY;

   /* we can only propagate for the last node for which the SDP was solved */
   if ( SCIPrelaxSdpGetSdpNode(relax) != SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
      return SCIP_OKAY;

   SCIP_CALL( SCIPrelaxSdpRelaxVal(relax, &sdpsolved, &relaxval) );
   if ( ! sdpsolved )
   {
      SCIPdebugMsg(scip, "Do not run propagation because SDP-relaxation was not solved properly.\n");
      return SCIP_OKAY;
   }

   /* avoid infinite relaxation objective values */
   if ( SCIPisInfinity(scip, REALABS(relaxval)) )
      return SCIP_OKAY;

   propdata = SCIPpropGetData(prop);
   assert( propdata != NULL );

   SCIPdebugMsg(scip, "Running propExecSdpredcost ...\n");
   *result = SCIP_DIDNOTFIND;

   nvars = SCIPgetNVars(scip);
   vars = SCIPgetVars(scip);

   /* make sure that data arrays have the right size */
   if ( nvars != propdata->nvars )
   {
      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->lbvarvals, propdata->nvars, nvars) );
      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->ubvarvals, propdata->nvars, nvars) );
      propdata->nvars = nvars;
   }
   SCIP_CALL( SCIPrelaxSdpGetPrimalBoundVars(scip, relax, vars, nvars, propdata->lbvarvals, propdata->ubvarvals, &success) );
   if ( ! success )
      return SCIP_OKAY;

   for (v = 0; v < nvars; v++)
   {
      if ( SCIPvarIsBinary(vars[v]) && propdata->forbins )
      {
         SCIP_CALL( sdpRedcostFixingBinary(scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );

         if ( varresult == SCIP_REDUCEDDOM )
            *result = SCIP_REDUCEDDOM;
      }
      else if ( ! SCIPvarIsBinary(vars[v]) && propdata->forintconts )
      {
         SCIP_CALL( sdpRedcostFixingIntCont(scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );

         if ( varresult == SCIP_REDUCEDDOM )
            *result = SCIP_REDUCEDDOM;
      }
   }

   return SCIP_OKAY;
}

static
SCIP_DECL_PROPFREE(propFreeSdpredcost)
{/*lint --e{715}*/
   SCIP_PROPDATA* propdata;

   propdata = SCIPpropGetData(prop);
   assert( propdata != NULL );
   SCIPfreeBlockMemory(scip, &propdata);

   SCIPpropSetData(prop, NULL);

   return SCIP_OKAY;
}

static
SCIP_DECL_PROPINITSOL(propInitsolSdpredcost)
{
   SCIP_PROPDATA* propdata;

   propdata = SCIPpropGetData(prop);
   assert(propdata != NULL);

   propdata->nvars = SCIPgetNVars(scip);
   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbvarvals), propdata->nvars) );
   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubvarvals), propdata->nvars) );

   return SCIP_OKAY;
}

static
SCIP_DECL_PROPEXITSOL(propExitsolSdpredcost)
{
   SCIP_PROPDATA* propdata;

   propdata = SCIPpropGetData(prop);
   assert( propdata != NULL );

   SCIPfreeBlockMemoryArrayNull(scip, &(propdata->lbvarvals), propdata->nvars);
   SCIPfreeBlockMemoryArrayNull(scip, &(propdata->ubvarvals), propdata->nvars);

   return SCIP_OKAY;
}

static
SCIP_DECL_PROPCOPY(propCopySdpredcost)
{
   assert( scip != NULL );
   assert( prop != NULL );
   assert( strcmp(SCIPpropGetName(prop), PROP_NAME) == 0 );

   /* call inclusion method of constraint handler */
   SCIP_CALL( SCIPincludePropSdpredcost(scip) );

   return SCIP_OKAY;
}

SCIP_RETCODE SCIPincludePropSdpredcost(
   SCIP*                 scip                
   )
{
   SCIP_PROPDATA* propdata = NULL;
   SCIP_PROP* prop;

   /* create propagator data */
   SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
   propdata->nvars = 0;
   propdata->lbvarvals = NULL;
   propdata->ubvarvals = NULL;

   /* include propagator */
   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
         propExecSdpredcost, propdata) );
   assert( prop != NULL );

   /* set optional callbacks via setter functions */
   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopySdpredcost) );
   SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolSdpredcost) );
   SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolSdpredcost) );
   SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSdpredcost) );

   /* add additional parameters */
   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/forbins", "Should SDP reduced cost fixing be executed for binary variables?",
         &(propdata->forbins), TRUE, DEFAULT_SDPRCBIN, NULL, NULL) );

   SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/forintconts", "Should SDP reduced cost fixing be executed for integer and continuous variables?",
         &(propdata->forintconts), TRUE, DEFAULT_SDPRCINTCONT, NULL, NULL) );

   return SCIP_OKAY;
}