cons_rowcuts.cpp

Go to the documentation of this file.

/* $Id: cons_rowcuts.cpp 1223 2017-04-20 10:41:34Z stefan $
 *
 * @file   cons_rowcuts.c
 * @ingroup CONSHDLRS 
 * @brief  constraint handler for rowcuts constraints
 *         enables separation of convexification cuts during SCIP solution procedure
 * @author Pietro Belotti
 * @author Timo Berthold
 * @license This file is licensed under the Eclipse Public License (EPL)
 * 
 * This file is licensed under the Eclipse Public License (EPL)
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/

#include <assert.h>

#include "CouenneConfig.h"
#ifdef COIN_HAS_SCIP

#include "cons_rowcuts.h"
#include "scip/cons_linear.h"
#include "scip/scip.h"

#include "CouenneProblem.hpp"

/* constraint handler properties */
#define CONSHDLR_NAME          "rowcuts"
#define CONSHDLR_DESC          "adds row cuts generated by Couenne in a Branch-and-Check fashion"
#define CONSHDLR_SEPAPRIORITY         0 
#define CONSHDLR_ENFOPRIORITY  -9999999 
#define CONSHDLR_CHECKPRIORITY -9999999 
#define CONSHDLR_SEPAFREQ            -1 
#define CONSHDLR_PROPFREQ            -1 
#define CONSHDLR_EAGERFREQ          100 
#define CONSHDLR_MAXPREROUNDS         0 
#define CONSHDLR_DELAYSEPA        FALSE 
#define CONSHDLR_DELAYPROP        FALSE 
#define CONSHDLR_DELAYPRESOL      FALSE 
#define CONSHDLR_NEEDSCONS        FALSE 
#define DEFAULT_MAXCUTTINGROUNDS     5 
using namespace Couenne;

/*
 * Data structures
 */

struct SCIP_ConshdlrData
{
   CouenneCutGenerator*  cutgenerator;       /* CouenneCutGenerator for linearization cuts */
   OsiSolverInterface*   milp;               /* Couenne's MILP relaxation of Couenne's MINLP */
   int                   maxcuttingrounds;   /* how many rounds of cuts should be applied at most */
   int                   ncuttingrounds;     /* how many rounds of cuts have been applied already */
};


/*
 * Local methods
 */

/* tries to find violated linearization cuts and adds them to SCIP */
static
SCIP_RETCODE checkRowcuts(
   SCIP*                 scip,               
   SCIP_CONSHDLR*        conshdlr,           
   SCIP_RESULT*          result,             
   SCIP_Bool             addcons             
   )
{
   SCIP_CONSHDLRDATA* conshdlrdata;
   CouenneProblem* problem;
   OsiCuts cs;
   SCIP_Real* sol;
   SCIP_VAR** vars;
   int nvars;
   int i;

   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(result != NULL);

   /* get constraint handler data */
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);

   /* get Couenne problem data */
   problem = conshdlrdata->cutgenerator-> Problem ();

   /* get variable data, create sol */
   nvars = SCIPgetNVars(scip);
   vars = SCIPgetVars(scip);
   sol = new SCIP_Real [nvars];
   SCIP_CALL( SCIPgetSolVals(scip, NULL, nvars, vars, sol) );

   /* store solution into MILP data structure */
   conshdlrdata -> milp -> setColSolution(sol);

   /* let Couenne generate linearization cuts */
   problem -> domain () -> push (problem -> nVars (), sol, 
                                 problem -> domain () -> current () -> lb (), 
                                 problem -> domain () -> current () -> ub ());
   conshdlrdata -> cutgenerator -> genRowCuts (*(conshdlrdata->milp), cs, 0, NULL);
   problem -> domain () -> pop  ();

   if( !addcons )
   {
      *result = (cs.sizeRowCuts() == 0) ? SCIP_FEASIBLE : SCIP_INFEASIBLE;
      return SCIP_OKAY;
   }
   
   for( i = 0; i < cs.sizeRowCuts(); i++ ) 
   {
      CoinPackedVector row;

      SCIP_CONS* cons;
      SCIP_VAR** vars;

      char consname[SCIP_MAXSTRLEN];  
      SCIP_Real* vals;
      int* idxs;

      SCIP_Real lhs;
      SCIP_Real rhs;

      int nvals;
      int j;

      /* get the row corresponding to the cut */
      lhs = cs.rowCut(i).lb();
      rhs = cs.rowCut(i).ub();      
      row = cs.rowCut(i).row();

      /* get row data */
      nvals = row.getNumElements();
      idxs = row.getIndices();
      vals = row.getElements(); 
      
      (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "rowcut", i);

      /* create an empty linear constraint */
      SCIP_CALL_ABORT( SCIPcreateConsLinear(scip, &cons, consname, 0, NULL, NULL, lhs, rhs, 
            TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );

      /* get SCIP variable array */
      vars = SCIPgetVars(scip);      

      /* add variables to constraint */
      for( j = 0; j < nvals; j++ )
      {
         SCIP_CALL( SCIPaddCoefLinear(scip, cons, vars[idxs[j]], vals[j]) );
      }
      
      /* add constraint to SCIP */
      SCIP_CALL( SCIPaddCons(scip, cons) );
#if 0
       SCIP_CALL( SCIPprintCons(scip,cons,NULL) );
#endif
      SCIP_CALL( SCIPreleaseCons(scip, &cons) );        

      *result = SCIP_CONSADDED;
   }
   
   /* store cuts to MILP data structure */
   if (cs.sizeRowCuts ()) {
      conshdlrdata -> milp -> applyCuts (cs);
   }

   return SCIP_OKAY;
}

/*
 * Callback methods of constraint handler
 */

#define conshdlrCopyRowcuts NULL

static
SCIP_DECL_CONSFREE(consFreeRowcuts)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;

   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(scip != NULL);

   /* get constraint handler data */
   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   
   /* free constraint handler data */
   SCIPfreeMemory(scip, &conshdlrdata);
   SCIPconshdlrSetData(conshdlr, NULL);

   return SCIP_OKAY;
}

#define consInitRowcuts NULL

#define consExitRowcuts NULL

#define consInitpreRowcuts NULL

#define consExitpreRowcuts NULL

#define consInitsolRowcuts NULL

#define consExitsolRowcuts NULL

#define consDeleteRowcuts NULL

#define consTransRowcuts NULL

#define consInitlpRowcuts NULL

#define consSepalpRowcuts NULL

#define consSepasolRowcuts NULL

static
SCIP_DECL_CONSENFOLP(consEnfolpRowcuts)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;

   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(nconss == 0 && conss == NULL); /* there should be no constraints */
   assert(result != NULL);


   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   if( conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
   {
      SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
      conshdlrdata->ncuttingrounds++;
   }

   /* we want to accept all solutions, even if we added a constraint that cuts them off */
   *result = SCIP_FEASIBLE;

   return SCIP_OKAY;
}

static
SCIP_DECL_CONSENFOPS(consEnfopsRowcuts)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;

   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(nconss == 0 && conss == NULL); /* there should be no constraints */
   assert(result != NULL);


   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);

   if( conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
   {
      SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
      conshdlrdata->ncuttingrounds++;
   }

   /* we want to accept all solutions, even if we added a constraint that cuts them off */
   *result = SCIP_FEASIBLE;

   return SCIP_OKAY;
}

static
SCIP_DECL_CONSCHECK(consCheckRowcuts)
{  /*lint --e{715}*/
   SCIP_CONSHDLRDATA* conshdlrdata;

   assert(scip != NULL);
   assert(conshdlr != NULL);
   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
   assert(nconss == 0 && conss == NULL); /* there should be no constraints */
   assert(result != NULL);


   conshdlrdata = SCIPconshdlrGetData(conshdlr);
   assert(conshdlrdata != NULL);
   if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
   {
      SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
      conshdlrdata->ncuttingrounds++;
   }

   *result = SCIP_FEASIBLE;

   return SCIP_OKAY;
}

#define consPropRowcuts NULL

#define consPresolRowcuts NULL

#define consRespropRowcuts NULL

static
SCIP_DECL_CONSLOCK(consLockRowcuts)
{  /*lint --e{715}*/
   assert(cons == NULL);

   return SCIP_OKAY;
}

#define consActiveRowcuts NULL

#define consDeactiveRowcuts NULL

#define consEnableRowcuts NULL

#define consDisableRowcuts NULL

#define consPrintRowcuts NULL

#define consCopyRowcuts NULL

#define consParseRowcuts NULL

/*
 * constraint specific interface methods
 */

SCIP_RETCODE SCIPincludeConshdlrRowcuts(
   SCIP*                 scip,               
   CouenneCutGenerator*  cutgenerator,       
   OsiSolverInterface*   milp                
   )
{
   SCIP_CONSHDLRDATA* conshdlrdata;

   /* create rowcuts constraint handler data */
   SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
   conshdlrdata->cutgenerator = cutgenerator;
   conshdlrdata->milp = milp;
   conshdlrdata->ncuttingrounds = 0;

#if SCIP_VERSION >= 400
   /* include constraint handler */
   SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
         CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
         CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS,
         CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_NEEDSCONS,
         SCIP_PROPTIMING_BEFORELP, SCIP_PRESOLTIMING_NONE,
         conshdlrCopyRowcuts,
         consFreeRowcuts, consInitRowcuts, consExitRowcuts,
         consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
         consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
         consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, NULL, consEnfopsRowcuts, consCheckRowcuts,
         consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
         consActiveRowcuts, consDeactiveRowcuts,
         consEnableRowcuts, consDisableRowcuts, NULL,
         consPrintRowcuts, consCopyRowcuts, consParseRowcuts, NULL, NULL, NULL,
         conshdlrdata) );
#elif SCIP_VERSION >= 320
   /* include constraint handler */
   SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
         CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
         CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS,
         CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_NEEDSCONS,
         SCIP_PROPTIMING_BEFORELP, SCIP_PRESOLTIMING_NONE,
         conshdlrCopyRowcuts,
         consFreeRowcuts, consInitRowcuts, consExitRowcuts,
         consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
         consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
         consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, consEnfopsRowcuts, consCheckRowcuts,
         consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
         consActiveRowcuts, consDeactiveRowcuts,
         consEnableRowcuts, consDisableRowcuts, NULL,
         consPrintRowcuts, consCopyRowcuts, consParseRowcuts, NULL, NULL, NULL,
         conshdlrdata) );
#elif SCIP_VERSION >= 300
   /* include constraint handler */
   SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
         CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
         CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS,
         CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_DELAYPRESOL, CONSHDLR_NEEDSCONS,
         SCIP_PROPTIMING_BEFORELP,
         conshdlrCopyRowcuts,
         consFreeRowcuts, consInitRowcuts, consExitRowcuts,
         consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
         consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
         consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, consEnfopsRowcuts, consCheckRowcuts,
         consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
         consActiveRowcuts, consDeactiveRowcuts,
         consEnableRowcuts, consDisableRowcuts, NULL,
         consPrintRowcuts, consCopyRowcuts, consParseRowcuts, NULL, NULL,
         conshdlrdata) );
#elif SCIP_VERSION >= 210
   /* include constraint handler */
   SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
         CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
         CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS, 
         CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_DELAYPRESOL, CONSHDLR_NEEDSCONS,
         SCIP_PROPTIMING_BEFORELP,
         conshdlrCopyRowcuts,
         consFreeRowcuts, consInitRowcuts, consExitRowcuts, 
         consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
         consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
         consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, consEnfopsRowcuts, consCheckRowcuts, 
         consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
         consActiveRowcuts, consDeactiveRowcuts, 
         consEnableRowcuts, consDisableRowcuts, NULL,
         consPrintRowcuts, consCopyRowcuts, consParseRowcuts,
         conshdlrdata) );
#else
   /* include constraint handler */
   SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
         CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
         CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS,
         CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_DELAYPRESOL, CONSHDLR_NEEDSCONS,
         conshdlrCopyRowcuts,
         consFreeRowcuts, consInitRowcuts, consExitRowcuts,
         consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
         consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
         consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, consEnfopsRowcuts, consCheckRowcuts,
         consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
         consActiveRowcuts, consDeactiveRowcuts,
         consEnableRowcuts, consDisableRowcuts,
         consPrintRowcuts, consCopyRowcuts, consParseRowcuts,
         conshdlrdata) );
#endif

   /* add rowcuts constraint handler parameters */
   SCIP_CALL( SCIPaddIntParam(scip,
         "constraints/" CONSHDLR_NAME "/maxcuttingrounds",
         "how many rounds of cuts should be applied at most?",
         &conshdlrdata->maxcuttingrounds, FALSE, DEFAULT_MAXCUTTINGROUNDS, -1, INT_MAX, NULL, NULL) );

   return SCIP_OKAY;
}

#endif