mt_T2.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_T2_H__
#define __MT_T2_H__
#include "EGlib.h"
#include "mt_gomory.h"
#include "mt_cplex_cbk.h"
#include "mt_cutpool.h"
#include "mt_tableau.h"
/** @file 
 * @ingroup MTgomory */
/** @addtogroup MTgomory */
/** @{ */
/* ========================================================================= */
/** @brief compute the best cuts found using T2 sets as a base, where
 * \f[
T2_n=\left\{x\in\mathbb{R}^n:
\begin{matrix}
R1:&-x_1 & \leq 0\\
R2:& x_1-x_2 & \leq 1\\
R3:& x_1+x_2-x_3 & \leq 2\\
\vdots & \vdots & \vdots\\
Rn:& x_1+\ldots+x_{n-1}-x_n&\leq n-1\\
R(n+1):& x_1+\ldots+x_{n-1}+x_n&\leq n\\
\end{matrix}\right\} \f], and where we try all possible 
 * \f$n!2^n\f$ reorientation of the axis and permutation of the rows.
 * 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. 
 * @param tb tableau description to use.
 * @param lp description of the current node LP.
 * @param f fractional values asociated with the tableau.
 * @param work array of length at least ncols+1 to be used as working space.
 * @param cuth cutheap to store the best cuts found in the process
 * @param extcut array of length ncols to store extended cut while processing
 * @param cut_style if 0, produce cut for cuts derived with exactly tb->nrows 
 * rows, if 1, also try with smaller values up to 2.
 * @return zero on success, non-zero otherwise.
 * */
int MTt2Cut(const MTrowmatrix_t*const tb, 
            MTlp_t*const lp, 
            MTcutHeap_t*const cuth,
            const double*const f,
            double*const extcut,
            double*const work,
            const int cut_style);
/* ========================================================================= */
/** @brief Interface for the CPLEX-callback for the #MTt2Cut function.
 * @param env as returned by CPXopenCPLEX function.
 * @param cbdata A pointer passed from the optimization routine to the
 * user-written callback that identifies the problem being optimized. The only 
 * purpose of this pointer is to pass it to the callback information routines.
 * @param wherefrom An integer value indicating where in the optimization this
 * function was called. It has the value CPX_CALLBACK_MIP_CUT.
 * @param cbhandle A pointer to user private data.
 * @param useraction_p A pointer to an integer indicating the action for ILOG
 * CPLEX to take at the completion
 * of the user callback. The table summarizes possible actions.
 * - 0 CPX_CALLBACK_DEFAULT Use cuts as added
 * - 1 CPX_CALLBACK_FAIL Exit optimization
 * - 2 CPX_CALLBACK_SET Use cuts as added
 * */
int MTt2_ccbk(CPXCENVptr env,
              void*cbdata,
              int wherefrom,
              void*cbhandle,
              int*useraction_p);
/** @} */
/* end of mt_T2.h */
/* ========================================================================= */
#endif

---