mt_cplex.ex.c

Go to the documentation of this file.

/* MTgomory "multi tableau gomory cut" provides an implementation for gomory
 * cuts derived from multiple tableau rows in the spirit of the work of
 * Andersen et al (IPCO 2007), Cornuejols (es presented in George Nemhauser
 * Birthday Conference in Atlanta 2007) and Gomory (presented in the same
 * conference).
 *
 * Copyright (C) 2007 Daniel Espinoza.
 * 
 * This library 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 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library 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 library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
/* ========================================================================= */
#include "EGlib.h"
#include "MTgomory.h"
#include <signal.h>
/** @file 
 * @ingroup MTgomory */
/** @addtogroup MTgomory */
/** @{ */
/* ========================================================================= */
/** @name static parameters for the main program */
/*@{*/
/** @brief CPLEX option file name */
static char options[1024]="cplex.opt";
/** @brief input problem file */
static char problem[1024] = "";
/** @brief global cplex environment */
static CPXENVptr env = 0;
/** @brief global lp pointer */
static CPXLPptr  lp = 0;
/** @brief max cuts per node */
static int max_cuts_per_node = 1000;
/** @brief max cuts per round */
static int max_cuts_per_round = 10;
/** @brief cuts at root only */
static int cuts_at_root_only = 1;
/** @brief cut selection strategy */
static MTcutSelection_t cut_selection = MTcsDefault; 
/** @brief cut dominance check enable */
static int cut_dominance = 0;
/** @brief maximum number of tableau-rows to use */
static int max_tableau_rows = 5;
/** @brief use callback cuts */
static int use_cuts = 1;
/** @brief use solve callback */
static int use_solve_cbk = 0;
/** @brief cut generation strategy */
static int cut_style = 1;
/** @brief maximum running time */
static double max_rtime = INT_MAX;
/** @brief maximum memory usage */
static unsigned long memlimit = UINT_MAX;
/*@}*/
/* ========================================================================= */
static void sighandler(int s)
{
  switch(s)
  {
    case SIGXCPU:
      fprintf(stderr,"TIME_LIMIT_REACHED (ending now)\n");
      exit(EXIT_FAILURE);
    default:
      fprintf(stderr,"Unknown signal %d (ending now)\n",s);
      exit(EXIT_FAILURE);
  }
}
/* ========================================================================= */
/** @brief function to handle resource usage limits */
static int mem_limits(void)
{
  int rval = 0;
  struct rlimit mlim;
  rval = getrlimit(RLIMIT_CPU,&mlim);
  CHECKRVAL(rval);
  fprintf(stderr, "Cur rtime limit %ld, trying to set to %lg\n", mlim.rlim_cur, max_rtime);
  if(max_rtime > mlim.rlim_max) max_rtime = (double)mlim.rlim_max;
  mlim.rlim_cur = (rlim_t)max_rtime;
  rval = setrlimit(RLIMIT_CPU,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "New rtime limit %ld (%.3lg)\n", mlim.rlim_cur, max_rtime);
  rval = getrlimit(RLIMIT_DATA,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "Cur data limit %ld,%ld (soft,hard)\n", mlim.rlim_cur, 
          mlim.rlim_max);
  mlim.rlim_cur = memlimit;       
  rval = setrlimit(RLIMIT_DATA,&mlim);        
  TESTERRNOIF(rval);
  rval = getrlimit(RLIMIT_DATA,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "New data limit %ld,%ld (soft,hard)\n", mlim.rlim_cur, 
          mlim.rlim_max);
  rval = getrlimit(RLIMIT_AS,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "Cur address space limit %ld,%ld (soft,hard)\n", 
          mlim.rlim_cur, mlim.rlim_max);
  mlim.rlim_cur = memlimit; 
  rval = setrlimit(RLIMIT_AS,&mlim);        
  TESTERRNOIF(rval);
  rval = getrlimit(RLIMIT_AS,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "New address space limit %ld,%ld (soft,hard)\n", 
          mlim.rlim_cur, mlim.rlim_max);
  mlim.rlim_cur = 0;
  rval = setrlimit(RLIMIT_CORE,&mlim);        
  TESTERRNOIF(rval);
  rval = getrlimit(RLIMIT_CORE,&mlim);
  TESTERRNOIF(rval);
  fprintf(stderr, "New core dump space limit %ld,%ld (soft,hard)\n", 
          mlim.rlim_cur, mlim.rlim_max);
  /* set signal handler for SIGXCPU */
  signal(SIGXCPU,sighandler);
  return rval;
}
/* ========================================================================= */
/** @brief usage function */
void usage(char*const prog)
{
  fprintf(stderr,"Usage: %s [options]\n",prog);
  fprintf(stderr,"Options:\n");
  fprintf(stderr,"\t-c n Choose cut-generation procedure: 0 = none, \n"
                 "\t     1 = MTgomory, 2 = T1, 3 = T2. Default %d\n", 
                 use_cuts);
  fprintf(stderr,"\t-d n enable (=1) or not (=0) cut dominance check,\n"
                 "\t     default %d\n", cut_dominance);
  fprintf(stderr,"\t-f s file name of the problem to be optimized\n");
  fprintf(stderr,"\t-h   print this help and exit\n");
  fprintf(stderr,"\t-m n maximum memory usage allowed, default %lu\n", 
          memlimit);
  fprintf(stderr,"\t-n n maximum number of cuts to add at a given node in the\n"
                 "\t     B&B tree, default %d\n", max_cuts_per_node);
  fprintf(stderr,"\t-N n maximum number of cuts to add per round, default %d\n",
          max_cuts_per_round);
  fprintf(stderr,"\t-o s file name of the cplex option file, default %s\n",
          "cplex.opt");
  fprintf(stderr,"\t-r n add cuts only at the root node, default %d\n",
          cuts_at_root_only);
  fprintf(stderr,"\t-R n maximum running time allowed, default %lf\n",
          max_rtime);
  fprintf(stderr,"\t-s n cut selection strategy, %d for violation, %d for \n"
                 "\t     1/L_inf, %d for 1/L_2, %d for raw score, default %d\n", 
                 MTcsVIOL, MTcsINVLINF, MTcsINVL2, MTcsRAW, cut_selection);
  fprintf(stderr,"\t-S n use (1) solve callback or not (0), default %d\n",
                  use_solve_cbk); 
  fprintf(stderr,"\t-T n cut generation style 0 for one round, 1 for multiple\n"
                 "\t     rounds on the same set of best tableau rows, default %d\n",
                 cut_style);
  fprintf(stderr,"\t-t n maximum number of tableau to use while generating \n"
                 "\t     MTgomory cuts, default %d\n", max_tableau_rows);
}
/* ========================================================================= */
/** @brief parsing parameters function, also read problem and options file */
int parseargs(int argc,char**argv)
{
  int has_problem=0;
  int c,rval;
  FILE* infile = 0;
  while((c=getopt(argc,argv,"f:ho:c:d:T:t:r:R:m:n:N:s:S:")) != EOF)
  {
    switch(c)
    {
      case 'h':
        usage(argv[0]);
        exit(0);
        break;
      case 'S':
        use_solve_cbk = atoi(optarg);
        break;
      case 's':
        cut_selection = atoi(optarg);
        break;
      case 'r':
        cuts_at_root_only = atoi(optarg);
        break;
      case 'R':
        max_rtime = strtod(optarg,0);
        break;
      case 'o':
        strncpy(options,optarg,(size_t)1023);
        break;
      case 'm':
        memlimit = strtoul(optarg,0,10);
        break;
      case 'n':
        max_cuts_per_node = atoi(optarg);
        break;
      case 'N':
        max_cuts_per_round = atoi(optarg);
        break;
      case 'T':
        cut_style = atoi(optarg);
        break;
      case 't':
        max_tableau_rows = atoi(optarg);
        break;
      case 'f':
        strncpy(problem,optarg,(size_t)1023);
        has_problem=1;
        break;
      case 'd':
        cut_dominance = atoi(optarg);
        break;
      case 'c':
        use_cuts = atoi(optarg);
        break;
      default:
        usage(argv[0]);
        return 1;
    }
  }
  FTESTG((rval = !has_problem),CLEANUP,"Should provide a problem name");
  /* display configuration */
  fprintf(stderr,"\tCplex option file        : %s\n",options);
  fprintf(stderr,"\tProblem file             : %s\n",problem);
  fprintf(stderr,"\tUsing multi-tableau cuts : %s\n",use_cuts == 1? "gomory": (use_cuts==2? "T1":(use_cuts==3 ? "T2":(use_cuts==4? "SL":"no"))));
  fprintf(stderr,"\tMax tableau              : %d\n",max_tableau_rows);
  fprintf(stderr,"\tMax cuts per node        : %d\n",max_cuts_per_node);
  fprintf(stderr,"\tMax cuts per round       : %d\n",max_cuts_per_round);
  fprintf(stderr,"\tCuts only at root        : %s\n",cuts_at_root_only ? "yes":"no");
  fprintf(stderr,"\tCuts Style               : %d\n",cut_style);
  fprintf(stderr,"\tCuts Selection Strategy  : %d\n",cut_selection);
  fprintf(stderr,"\tCut dominance check      : %d\n",cut_dominance);
  fprintf(stderr,"\tUse Solve Callback       : %s\n",use_solve_cbk ? "yes":"no");
  /* now we read option file */ 
  infile = EGsfopen(options,"r");
  rval = MTread_cplex_options(env,infile);
  CHECKRVALG(rval,CLEANUP);
  fclose(infile);
  /* set hard limits */
  rval = mem_limits();
  CHECKRVALG(rval,CLEANUP);
  /* now we are ready to roll! */
CLEANUP:
  if(rval) usage(argv[0]);
  return rval;
}
/* ========================================================================= */
/** @brief this function reads a problem file, set the cut-callback, and call
 * the MIP solver */
int main (int argc, char**argv)
{
  int rval = 0;
  int solstat;
  double objval,objbound;
  MTgomory_ccbk_t data;
  MTns_ccbk_t ns_data;
  EGtimer_t timer;
  /* initialize data */
  EGtimerReset(&timer);
  EGtimerStart(&timer);
  env = CPXopenCPLEX (&rval);
  MTcplexCHECKRVALG(env,rval,CLEANUP);
  MTgomory_ccbk_init(&data);
  MTns_ccbk_init(&ns_data);
  /* parse arguments and read option file */
  rval = parseargs(argc,argv);
  CHECKRVALG(rval,CLEANUP);
  MTccbkSetCuts(&data,use_cuts);
  MTccbkSetCutsAtRoot(&data,cuts_at_root_only);
  MTccbkSetCutDominance(&data,cut_dominance);
  MTccbkSetCutSel(&data,cut_selection);
  MTccbkSetCutStyle(&data,cut_style);
  MTccbkSetMaxNodeCuts(&data,max_cuts_per_node);
  MTccbkSetMaxRows(&data,max_tableau_rows);
  MTccbkSetMaxRoundCuts(&data,max_cuts_per_round);
  /* now we load the problem in memory */
  lp = CPXcreateprob (env, &rval, problem);
  MTcplexCHECKRVALG(env,rval,CLEANUP);
  rval = CPXreadcopyprob (env, lp, problem, 0);
  MTcplexCHECKRVALG(env,rval,CLEANUP);
  /* add node solve callback */
  if(use_solve_cbk)
  {
    rval = CPXsetsolvecallbackfunc(env,MTnode_solve,&ns_data);
    MTcplexCHECKRVALG(env,rval,CLEANUP);
  }
  /* add the callback */
  switch(use_cuts)
  {
    case 1:
      rval = CPXsetcutcallbackfunc(env,MTgomory_ccbk,&data);
      MTcplexCHECKRVALG(env,rval,CLEANUP);
      break;
    case 2:
      rval = CPXsetcutcallbackfunc(env,MTt1_ccbk,&data);
      MTcplexCHECKRVALG(env,rval,CLEANUP);
      break;
    case 3:
      rval = CPXsetcutcallbackfunc(env,MTt2_ccbk,&data);
      MTcplexCHECKRVALG(env,rval,CLEANUP);
      break;
    case 4:
      rval = CPXsetcutcallbackfunc(env,MTsl_ccbk,&data);
      MTcplexCHECKRVALG(env,rval,CLEANUP);
      break;
    case 0:
      rval = CPXsetcutcallbackfunc(env,MTgomory_ccbk,&data);
      MTcplexCHECKRVALG(env,rval,CLEANUP);
      break;
    default:
      FTESTG((rval=1),CLEANUP,"Unknown cut selection %d",use_cuts);
      usage(argv[0]);
      break;
  }
  /* Optimize the problem and obtain solution */
  rval = CPXmipopt (env, lp);
  EGtimerStop(&timer);
  MTcplexCHECKRVALG(env,rval,CLEANUP);
  solstat = CPXgetstat (env, lp);
  fprintf (stderr,"Solution status %d.\n", solstat);
  rval = CPXgetbestobjval (env, lp, &objbound);
  MTcplexCHECKRVALG(env,rval,CLEANUP);
  if(solstat == CPXMIP_OPTIMAL || solstat == CPXMIP_OPTIMAL_TOL)
  {
    rval = CPXgetobjval (env, lp, &objval);
    MTcplexCHECKRVALG(env,rval,CLEANUP);
  }
  else objval = objbound;
  fprintf (stderr,"Objective value %.10lg bound %.10lg GAP %10lg\nTime %.2lf\n", objval,objbound,100*fabs((objval-objbound)/(fabs(objbound)<1.0?1.0:objbound)), timer.time);
  MTccbk_info_display(&(data.info),stderr);
  MTccbk_display_sumary(stderr);
  if(use_solve_cbk) MTns_ccbk_display(&ns_data);
CLEANUP:

  /* free all allocated memory */
  MTgomory_ccbk_clear(&data);
  MTns_ccbk_clear(&ns_data);
  /* free problem and close cplex */
  if(lp)
  {
    rval = CPXfreeprob(env,&lp);
    lp = 0;
    MTcplexCHECKRVALG(env,rval,CLEANUP);
  }
  if(env)
  {
    rval = CPXcloseCPLEX(&env);
    env=0;
    MTcplexCHECKRVALG(env,rval,CLEANUP);
  }
  return rval;

}

/* ========================================================================= */
/** @} */
/* end of mt_cplex.ex.c */

---