00001 /* MTgomory "multi tableau gomory cut" provides an implementation for gomory 00002 * cuts derived from multiple tableau rows in the spirit of the work of 00003 * Andersen et al (IPCO 2007), Cornuejols (es presented in George Nemhauser 00004 * Birthday Conference in Atlanta 2007) and Gomory (presented in the same 00005 * conference). 00006 * 00007 * Copyright (C) 2007 Daniel Espinoza. 00008 * 00009 * This library is free software; you can redistribute it and/or modify it 00010 * under the terms of the GNU Lesser General Public License as published by the 00011 * Free Software Foundation; either version 2.1 of the License, or (at your 00012 * option) any later version. 00013 * 00014 * This library is distributed in the hope that it will be useful, but 00015 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 00016 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 00017 * License for more details. 00018 * 00019 * You should have received a copy of the GNU Lesser General Public License 00020 * along with this library; if not, write to the Free Software Foundation, 00021 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 * */ 00023 /* ========================================================================= */ 00024 #ifndef __MT_T1_H__ 00025 #define __MT_T1_H__ 00026 #include "EGlib.h" 00027 #include "mt_gomory.h" 00028 #include "mt_cplex_cbk.h" 00029 #include "mt_cutpool.h" 00030 #include "mt_tableau.h" 00031 /** @file 00032 * @ingroup MTgomory */ 00033 /** @addtogroup MTgomory */ 00034 /** @{ */ 00035 /* ========================================================================= */ 00036 /** @brief compute the best cuts found using T1 sets as a base, where 00037 * \f[ 00038 T1_n=\left\{ x\in\mathbb{R}^n: x_i\geq 0, \sum\limits_{i=1}^n x_i\leq n \right\},\f] 00039 * and where we try all possible \f$2^n\f$ reorientation of the 00040 * axis. 00041 * Note that we assume that all variables are continuous, and that the tableau 00042 * represent the (vectorial) equation 00043 * \f[\vec{x} = \vec{f}+\frac12\vec{1} +\sum\limits_{i\in I}s_i\vec{r_i}, \f] 00044 * where \f$\displaystyle\vec{x}\in\mathbb{Z}^m\f$, 00045 * \f$\displaystyle\vec{f}\in\left]-\frac12,\frac12\right[^m\f$, 00046 * \f$\displaystyle\vec{r_i}\in\mathbb{R}^m,\forall i\in I\f$, 00047 * \f$s\displaystyle _i\in\mathbb{R}_+,\forall i\in I\f$; and where \f$\displaystyle m=\f$ nrows and 00048 * \f$\displaystyle |I|=\f$ ncols. 00049 * @param tb tableau description to use. 00050 * @param lp description of the current node LP. 00051 * @param f fractional values asociated with the tableau. 00052 * @param work array of length at least ncols+1 to be used as working space. 00053 * @param cuth cutheap to store the best cuts found in the process 00054 * @param extcut array of length ncols to store extended cut while processing 00055 * @param cut_style if 0, produce cut for cuts derived with exactly tb->nrows 00056 * rows, if 1, also try with smaller values up to 2. 00057 * @return zero on success, non-zero otherwise. 00058 * */ 00059 int MTt1Cut(const MTrowmatrix_t*const tb, 00060 MTlp_t*const lp, 00061 MTcutHeap_t*const cuth, 00062 const double*const f, 00063 double*const extcut, 00064 double*const work, 00065 const int cut_style); 00066 /* ========================================================================= */ 00067 /** @brief Interface for the CPLEX-callback for the #MTt1Cut function. 00068 * @param env as returned by CPXopenCPLEX function. 00069 * @param cbdata A pointer passed from the optimization routine to the 00070 * user-written callback that identifies the problem being optimized. The only 00071 * purpose of this pointer is to pass it to the callback information routines. 00072 * @param wherefrom An integer value indicating where in the optimization this 00073 * function was called. It has the value CPX_CALLBACK_MIP_CUT. 00074 * @param cbhandle A pointer to user private data. 00075 * @param useraction_p A pointer to an integer indicating the action for ILOG 00076 * CPLEX to take at the completion 00077 * of the user callback. The table summarizes possible actions. 00078 * - 0 CPX_CALLBACK_DEFAULT Use cuts as added 00079 * - 1 CPX_CALLBACK_FAIL Exit optimization 00080 * - 2 CPX_CALLBACK_SET Use cuts as added 00081 * */ 00082 int MTt1_ccbk(CPXCENVptr env, 00083 void*cbdata, 00084 int wherefrom, 00085 void*cbhandle, 00086 int*useraction_p); 00087 /** @} */ 00088 /* end of mt_T1.h */ 00089 /* ========================================================================= */ 00090 #endif 00091