mt_gomory.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 
 * */
/* ========================================================================= */

/** @defgroup MTgomory Multiple Tableau Gomory Cuts
 *
 * This code present an implementation of some of the ideas on generating cuts
 * from multiple tableau rows at once. It has a basic cut-separation code, and
 * a cut-callback implementation for CPLEX */

/* ========================================================================= */
/** @mainpage MTgomory Home Page
 *
 * @section Introduction
<P>The bleding edge of this code can be found at <A HREF=https://conexo.dii.uchile.cl/SVN/COding/trunk/MTgomory TARGET=_top>this direction</A>.</P>
<P>A stable version can be found at <A HREF=https://conexo.dii.uchile.cl/SOurce/MTgomory.tar.bz2 TARGET=_top>this direction</A>.</P>
 */

/* ========================================================================= */
/** @file 
 * @ingroup MTgomory */
/** @addtogroup MTgomory */
/** @{ */
#ifndef __MT_GOMORY_H__
#define __MT_GOMORY_H__

/* ========================================================================= */
/** @brief Version String of the program */
extern const char MTversion[1024];

/* ========================================================================= */
/** @brief Given a set of tableau rows in column format, return the asociated
 * multi-tableau gomory cut.
 * Note that we assume that all variables are continuous, and that the tableau
 * represent the (vectorial) equation 
 * \f[\vec{x} = \vec{f}+\frac12\vec{1} +\sum\limits_{i\in I}s_i\vec{r_i}, \f]
 * where \f$\displaystyle\vec{x}\in\mathbb{Z}^m\f$,
 * \f$\displaystyle\vec{f}\in\left]-\frac12,\frac12\right[^m\f$, 
 * \f$\displaystyle\vec{r_i}\in\mathbb{R}^m,\forall i\in I\f$,
 * \f$s\displaystyle _i\in\mathbb{R}_+,\forall i\in I\f$; and where \f$\displaystyle m=\f$ nrows and
 * \f$\displaystyle |I|=\f$ ncols. 
 * The returned constraint is \f$\displaystyle \sum\limits_{i\in I}s_ib_i\geq 1\f$ where
 * \f$ \displaystyle b_i=\f$ cutval[i], \f$\displaystyle \forall i\in I\f$. And
 * where the set used to cut is \f$\displaystyle L=\left\{x:c\sigma x\leq c_o
 * ,\forall\sigma\in\mathrm{diag}\left(\{-1,1\}^{m}\right)\right\}\f$ and \f$\displaystyle
 * c=\f$ base, \f$\displaystyle c_o = \frac12\sum\limits_{i=1}^mc_i\f$, where we assume that \f$c_i\neq 0\forall i=1,\ldots,m\f$.
 * Finally, note that \f$\displaystyle b_i=\max\limits_{\sigma:c\sigma r_i>0}\left\{\frac{c\sigma r_i}{c_o-c\sigma f}\right\}\f$.
 * @param nrows number of rows in the tableau description
 * @param ncols number of variables in the tableau description
 * @param rowval array of values of the tableau.
 * @param rowind array of column-indices for the corresponding value in rowval.
 * @param rowbeg array of length nrows+1 storing the position in which position
 * of rowval the j-th row non-zero coefficient beggins, and in position
 * nrows it is stored the number of non-zeros in the description.
 * @param f fractional value asociated to the tableau.
 * @param cutval array of length ncols storing the coefficient for each
 * variable in the cut (the array is assumed to have length at least ncols).
 * @param base array of length nrows, where each part coefficient is assumed to
 * be non-zero.
 * @param work array of length at least ncols+1 to be used as working space.
 * @return zero on succes, non-zero otherwise.
 * */
int MTgomoryCut(const int nrows, 
                const int ncols,
                const double*const rowval,
                const int*const rowind,
                const int*const rowbeg,
                const double*const f,
                const double*const base,
                double*const cutval,
                double*const work);

/* ========================================================================= */
/** @brief verbose level for the module */
#define MT_VERB_LVL 100

/* ========================================================================= */
/** @brief debug level for the module */
#define MT_DEBUG_LVL 100

/* ========================================================================= */
/** @brief tolerance level for zero, i.e. all absolute values bellow 
 * #MT_ZERO_TOL are considered as zero. */
#define MT_ZERO_TOL 0x1p-20

/* ========================================================================= */
/** @} */
/* end of mt_gomory.h */
#endif

---