mt_types.h

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 
 * */
/* ========================================================================= */
#ifndef __MT_TYPES_H__
#define __MT_TYPES_H__
#include "cplex.h"
#include "EGlib.h"
/** @file 
 * @ingroup MTgomory */
/** @addtogroup MTgomory */
/** @{ */
/* ========================================================================= */
/** @brief formulation description for a problem */
typedef struct
{
  int nrows;    /**< @brief number of rows */
  int ncols;    /**< @brief number of cols */
  int nz;       /**< @brief number of non-zeros */
  int rspace;   /**< @brief row space reserved */
  int nzspace;  /**< @brief non-zero space reserved */
  int cspace;   /**< @brief col space reserved */
  char* sense;  /**< @brief sense of rows, size #MTlp_t::rspace */
  double*rhs;   /**< @brief rhs of rows, size #MTlp_t::rspace */ 
  char*rtype;   /**< @brief array of dize #MTlp_t::rspace */
  int*rstat;    /**< @brief array of size #MTlp_t::rspace */
  int*matbeg;   /**< @brief matbeg, size #MTlp_t::rspace +1 */
  char*ctype;   /**< @brief array of size #MTlp_t::cspace */
  int*cstat;    /**< @brief array of size #MTlp_t::cspace */
  int*matind;   /**< @brief matind, size #MTlp_t::nzspace */
  double*matval;/**< @brief matval, size #MTlp_t::nzspace */
  double*ub;    /**< @brief upper bounds, size #MTlp_t::cspace */
  double*lb;    /**< @brief lower bounds, size #MTlp_t::cspace */
  char** colnames;/**< @brief column names, size #MTlp_t::cspace */
  char* ccspace;/**< @brief column char array, size #MTlp_t::ccsz */
  int ccsz;     /**< @brief column char array size */
  char** rownames;/**< @brief row names, size #MTlp_t::rspace */
  char* rcspace;/**< @brief row char array, size #MTlp_t::rcsz */
  int rcsz;     /**< @brief row char array size */  
} MTlp_t;
/* ========================================================================= */
/** @brief structure holding a compresed matrix in row form */
typedef struct
{
  int nz;         /**< @brief number of non-zeros in the matrix */
  int nrows;      /**< @brief number of rows in the matrix */
  int ncols;      /**< @brief number of columns in the matrix */
  int nzspace;    /**< @brief space reserved for non-zeros */
  int rspace;     /**< @brief space reserved for rows */
  int cspace;     /**< @brief space reserved for columns */
  double*rowval;  /**< @brief where we store the values in the matrix, length nzspace */
  int*rowbeg;     /**< @brief where each row begins (length rspace+1, since 
                       rowbeg[nrows] store the end of the last row) */ 
  int*rowind;     /**< @brief which column is asociated with the asociated
                       position, length nzspace */
} MTrowmatrix_t;
/* ========================================================================= */
/** @brief structure to hold a solution to an LP */
typedef struct MTsol_t
{
  int cspace;         /**< @brief column space */
  int rspace;         /**< @brief row space */
  int ncols;          /**< @brief number of columns */
  int nrows;          /**< @brief number of rows */
  double*x;           /**< @brief X values */
  double*slack;       /**< @brief slack values */
  double*pseudocost;  /**< @brief pseudocost values */
} MTsol_t;

/* ========================================================================= */
/** @brief structure holding basic calllback information, used to control
 * callback behavior and statistic */
typedef struct MTccbk_info_t
{
  size_t node_cnt;    /**< @brief ID of last node visited */
  size_t node_cuts;/**< @brief counter of cuts added at the current node */
  size_t added_cuts;/**< @brief total added cuts */
  double root_val;/**< @brief store the best root value seen */
  int root_only;  /**< @brief if non-zero, add cuts at root node only */
  int use_cuts;   /**< @brief if non-zero, allow the cut process */ 
  size_t max_cuts;    /**< @brief maximum number of cuts to add per node */
  int max_cpr;    /**< @brief maximum number of cuts to add in each round of cut generation */
  int max_rows;   /**< @brief maximum number of row-tableaus to use */
  int cut_style;  /**< @brief how we add cuts, 1 for adding cuts for 1-k 
                        tableaus-rows, 0 for adding cuts only for k tableaus-rows */
} MTccbk_info_t;
/* ========================================================================= */
/** @brief information for node solve callback */
typedef struct
{
  double xdiff;   /**< @brief accumulated difference between solutions */
  size_t loops;   /**< @brief rounds of extra LP optimization performed */
  size_t ncalls;  /**< @brief count number of calls to the function */
  size_t nzrd;    /**< @brief number of zero reduced costs found */
  size_t csz;     /**< @brief size of col-related arrays */
  size_t rsz;     /**< @brief size of row-related arrays */
  char* rfix;     /**< @brief U for fixed at upper bound, L for fixed at lower
                        bound, F for free (not fixed)  */
  char* cfix;     /**< @brief U for fixed at upper bound, L for fixed at lower
                        bound, F for free (not fixed)  */
  double*dj;      /**< @brief space of reduced costs */
  double*pi;      /**< @brief space for dual solution */
  int*rstat;      /**< @brief used to store current basis */
  int*cstat;      /**< @brief used to store current basis */
  int*matind;     /**< @brief matind for constraints */
  double*matval;  /**< @brief matval for constraints */
  double*oobj;    /**< @brief dual LP norms */
  double*lb;      /**< @brief LP lower bounds */
  double*ub;      /**< @brief LP upper bounds */
  double*x0;      /**< @brief Initial LP solution */
  double*x1;      /**< @brief final LP solution */
  char*sense;     /**< @brief LP inequalities sense */
} MTns_ccbk_t;
/* ========================================================================= */
/** @brief structure to hold a cut */ 
typedef struct
{
  double rhs;       /**< @brief rhs of the inequality */
  double violation; /**< @brief violation */
  double min_abs;   /**< @brief minimum absolute value in the cut */
  double max_abs;   /**< @brief maximum absolute value in the cut */
  double* cutval;   /**< @brief values of the cut */
  int* cutind;      /**< @brief indices of non-zeros */
  double score;     /**< @brief internal score of the cut, it is defined as 1/|a|_2, but is computed over the raw cut. */
  int nzspace;      /**< @brief space for non-zeros */
  int nz;           /**< @brief actual non-zeros */
  char sense;       /**< @brief sense of the inequality */
  char form;        /**< @brief type of inequality stored 0 for complemented cuts, 1 for uncomplemented cuts */
} MTcut_t;
/* ========================================================================= */
/** @brief basic conector for the cut heap */
typedef struct
{
  dbl_EGeHeapCn_t hcn;  /**< @brief heap connector */
  EGeList_t lcn;        /**< @brief list connector for free slots */
  MTcut_t cut;          /**< @brief compressed cut structure */
} MTcutHeapCn_t;
/* ========================================================================= */
/** @brief types of cut score functions */
typedef enum 
{
  MTcsRAW         /**< @brief use raw cut score */,
  MTcsVIOL        /**< @brief cut violation */,
  MTcsINVLINF     /**< @brief \f$\displaystyle rhs/\|a\|_{\inf} \f$ for 
                       \f$ax\geq rhs\f$ inequalities, and as 
                       \f$\displaystyle -rhs/\|a\|_{\inf}\f$ for 
                       \f$ax\leq rhs\f$ inequalities.*/,
  MTcsINVL2       /**< @brief \f$\displaystyle rhs^2/\|a\|_2 \f$ for 
                       \f$ax\geq rhs\f$ inequalities, and as 
                       \f$\displaystyle -rhs^2/\|a\|_2\f$ for 
                       \f$ax\leq rhs\f$ inequalities.*/,
  MTcsDefault = MTcsRAW
} MTcutSelection_t;
/* ========================================================================= */
/** @brief configuration strucutre for #MTcutHeap_t */
typedef struct 
{
  MTcutSelection_t cut_score; /**< @brief selection type for cuts */
  int dominance_check;        /**< @brief if set to one, check for dominated 
                                   cuts within the heap */
} MTcutHeapControl_t;
/* ========================================================================= */
/** @brief simple structure (based on heaps) that holds up to certain number of
 * cuts, and keep (acording to a criteria) the best ones. */
typedef struct 
{
  dbl_EGeHeap_t heap;       /**< @brief where we store the cuts according to a 
                                 given score, defined by #MTcutHeap_t::control */
  EGeList_t free_cn;        /**< @brief list of free heap connectors */
  MTcutHeapCn_t* all_cn;    /**< @brief where we store all heap connectors */
  MTcut_t* next_free;       /**< @brief pointer to the next unused cut */
  size_t all_sz;            /**< @brief size of MTcutHeap_t::all_cn */
  MTcutHeapControl_t control;/**< @brief for controlling the behavior of related
                                 functions */
} MTcutHeap_t;
/* ========================================================================= */
/** @brief structure holding the working information for the all callbacks
 * function */
typedef struct 
{
  int rowsz;      /**< @brief reserved row-space in the structure */
  int colsz;      /**< @brief reserved col-space in the structure */
  double*work;    /**< @brief array of size #MTgomory_ccbk_t::colsz+1 */
  double*extcut;  /**< @brief array of size #MTgomory_ccbk_t::colsz */
  double*base;    /**< @brief array of size #MTgomory_ccbk_t::rowsz */
  double*f;       /**< @brief array of size #MTgomory_ccbk_t::rowsz */
  MTsol_t sol;    /**< @brief current node solution */
  MTcut_t cut;    /**< @brief structure to hold a resulting cut */
  MTrowmatrix_t tb;/**< @brief store the current tableau (extended format, 
                       with logicals included) */
  MTlp_t lp;      /**< @brief LP description of the node */
  MTccbk_info_t info;/**< @brief Basic callback control */
  MTcutHeap_t cuth;/**< @brief structure holding a cut-heap for acumulation */
} MTgomory_ccbk_t;
/* ========================================================================= */
/** @} */
/* end of mt_types.h */
#endif

---