mt_tableau.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 "mt_tableau.h"
#include "EGlib.h"
/** @file 
 * @ingroup MTgomory */
/** @addtogroup MTgomory */
/** @{ */

/* ========================================================================= */
int MTwriteRTableau(FILE*out,
                    const int nrows, 
                    const int ncols,
                    const double*const rowval,
                    const int*const rowind,
                    const int*const rowbeg,
                    const double*const f)
{
  int i = 0;
  fprintf(out,"TYPE: ROW_TABLEAU\n");
  fprintf(out,"NROWS: %d #rows in the tableau\n",nrows);
  fprintf(out,"NCOLS: %d #columns in the tableau\n",ncols);
  fprintf(out,"NZ: %d #number of non-zeros in the description\n",
          rowbeg[nrows]);
  fprintf(out,"ROWVAL_SECTION\n#what follows is the index and value "
              "information in the format\n#row_ind row_val\n");
  for(i = 0 ; i < rowbeg[nrows] ; i++) 
    fprintf(out,"%d %.5lf\n",rowind[i], rowval[i]);
  fprintf(out,"ROWBEG_SECTION\n#what follows is the rowbeg and f_i "
          "value asociated with each tableau, in the format\n"
          "#row_beg f_i\n");
  for(i = 0 ; i < nrows ; i++)
    fprintf(out,"%d %.5lf\n",rowbeg[i],f[i]);
  return 0; 
}

/* ========================================================================= */
int MTreadRTableau(FILE*input,
                    int*const nrows, 
                    int*const ncols,
                    double**const rowval,
                    int**const rowind,
                    int**const rowbeg,
                    double**const f)
{
  const char delim[3] = " :";
  const char coment[3] = "%#";
  int rval = 0, has_nrows=0, has_ncols=0, has_type=0, has_val=0, has_beg=0, has_nz=0, todo=1, i, nz=0, argc;
  char str[2048],*argv[1024];
  /* basic set-up */
  *nrows = *ncols = 0;
  *rowind = *rowbeg = 0;
  *rowval = 0;
  /* start reading from file */
  while(todo)
  {
    rval = EGioReadLine(str, (size_t)2048, input);
    CHECKRVALG(rval,CLEANUP);
    TESTG((rval = feof(input)||ferror(input)), CLEANUP, 
          "File ended prematurelly, or has errors");
    EGioNParse(str, 1024, delim, coment, &argc, argv);
    /* skip empty lines */
    if(!argc) continue;
    /* process each key-word accorsingly */
    if(strncmp(argv[0],"TYPE", (size_t)33)==0)
    {
      TESTG((rval=has_type),CLEANUP,"TYPE keyword repeated in file");
      TESTG((rval=(argc!=2)),CLEANUP,"TYPE has not 2 tokens");
      TESTG((rval=(strncmp(argv[1],"ROW_TABLEAU", (size_t)33)!=0)),
            CLEANUP, "Unknown file type %s, expected ROW_TABLEAU",
            argv[1]);
      has_type = 1;
    }
    else if(strncmp(argv[0],"NCOLS", (size_t)33)==0)
    {
      TESTG((rval=has_ncols),CLEANUP,"NCOLS keyword repeated in file");
      TESTG((rval=(argc!=2)),CLEANUP,"NCOLS has not 2 tokens");
      *ncols = atoi(argv[1]);
      TESTG((rval=(*ncols < 1)),CLEANUP, "NCOLS should be positive,"
            " is %d\n", *ncols);
      has_ncols = 1;
    }
    else if(strncmp(argv[0],"NZ", (size_t)33)==0)
    {
      TESTG((rval=has_nz),CLEANUP,"NZ keyword repeated in file");
      TESTG((rval=(argc!=2)),CLEANUP,"NZ has not 2 tokens");
      nz = atoi(argv[1]);
      TESTG((rval=(nz < 1)),CLEANUP, "NZ should be positive,"
            " is %d\n", nz);
      has_nz = 1;
      *rowval = EGsMalloc(double,nz);
      *rowind = EGsMalloc(int,nz);
    }
    else if(strncmp(argv[0],"ROWVAL_SECTION", (size_t)33)==0)
    {
      TESTG((rval=has_val),CLEANUP,"ROWVAL_SECTION keyword repeated in file");
      TESTG((rval=(argc!=1)),CLEANUP,"ROWVAL_SECTION has not 1 token");
      TESTG((rval=!has_nz),CLEANUP, "ROWVAL_SECTION without NZ");
      TESTG((rval=!has_ncols),CLEANUP, "ROWVAL_SECTION without NCOLS");
      for( i = 0 ; i < nz ; i++)
      {
        do
        {
          rval = EGioReadLine(str,(size_t)2048,input);
          CHECKRVALG(rval,CLEANUP);
          TESTG((rval = feof(input)||ferror(input)), CLEANUP, 
                "File ended prematurelly, or has errors");
          EGioNParse(str,1024,delim,coment,&argc,argv);
        }while(!argc);
        TESTG((rval=(argc!=2)),CLEANUP,"in ROWVAL_SECTION, line has "
              "not 2 tokens");
        (*rowind)[i] = atoi(argv[0]);
        (*rowval)[i] = strtod(argv[1],0);
      }
      has_val = 1;
    }
    else if(strncmp(argv[0],"ROWBEG_SECTION", (size_t)33)==0)
    {
      TESTG((rval=has_beg),CLEANUP,"ROWBEG_SECTION keyword repeated in file");
      TESTG((rval=(argc!=1)),CLEANUP,"ROWBEG_SECTION has not 1 token");
      TESTG((rval=!has_nrows),CLEANUP, "ROWBEG_SECTION without NROWS");
      for( i = 0 ; i < *nrows ; i++)
      {
        do
        {
          rval = EGioReadLine(str,(size_t)2048,input);
          CHECKRVALG(rval,CLEANUP);
          TESTG((rval = feof(input)||ferror(input)), CLEANUP, 
                "File ended prematurelly, or has errors");
          EGioNParse(str,1024,delim,coment,&argc,argv);
        }while(!argc);
        TESTG((rval=(argc!=2)),CLEANUP,"in ROWBEG_SECTION, line has "
              "not 2 tokens");
        (*rowbeg)[i] = atoi(argv[0]);
        (*f)[i] = strtod(argv[1],0);
      }
      has_beg = 1;
    }
    else if(strncmp(argv[0],"NROWS", (size_t)33)==0)
    {
      TESTG((rval=has_nrows),CLEANUP,"NROWS keyword repeated in file");
      TESTG((rval=(argc!=2)),CLEANUP,"NROWS has not 2 tokens");
      *nrows = atoi(argv[1]);
      TESTG((rval=(*nrows < 1)),CLEANUP, "NROWS should be positive,"
            " is %d\n", *nrows);
      has_nrows = 1;
      *rowbeg = EGsMalloc(int,(*nrows)+1);
      *f = EGsMalloc(double,(*nrows));
    }
    /* update todo */
    todo = !( has_nz && has_ncols && has_nrows && has_type && 
              has_val && has_beg && has_nz); 
  }
  (*rowbeg)[(*nrows)]=nz;
  /* final set-up */
  CLEANUP:
  return rval;
}

/* ========================================================================= */
/** @} */
/* end of mt_tableau.h */

---