mt_gomory.c File Reference

Detailed Description

Definition in file mt_gomory.c.

#include <math.h>
#include "EGlib.h"
#include "mt_gomory.h"
#include "mt_tableau.h"

Include dependency graph for mt_gomory.c:

Go to the source code of this file.

Functions

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)

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
$\vec{x} = \vec{f}+\frac12\vec{1} +\sum\limits_{i\in I}s_i\vec{r_i},$
where $\displaystyle\vec{x}\in\mathbb{Z}^m$ , $\displaystyle\vec{f}\in\left]-\frac12,\frac12\right[^m$ , $\displaystyle\vec{r_i}\in\mathbb{R}^m,\forall i\in I$ , $s\displaystyle _i\in\mathbb{R}_+,\forall i\in I$ ; and where $\displaystyle m=$ nrows and $\displaystyle |I|=$ ncols. The returned constraint is $\displaystyle \sum\limits_{i\in I}s_ib_i\geq 1$ where $\displaystyle b_i=$ cutval[i], $\displaystyle \forall i\in I$ . And where the set used to cut is $\displaystyle L=\left\{x:c\sigma x\leq c_o ,\forall\sigma\in\mathrm{diag}\left(\{-1,1\}^{m}\right)\right\}$ and $\displaystyle c=$ base, $\displaystyle c_o = \frac12\sum\limits_{i=1}^mc_i$ , where we assume that $c_i\neq 0\forall i=1,\ldots,m$ . Finally, note that $\displaystyle b_i=\max\limits_{\sigma:c\sigma r_i>0}\left\{\frac{c\sigma r_i}{c_o-c\sigma f}\right\}$ .

Generated on Mon Oct 26 09:16:42 2009 for MTgomory by

1.4.6


Functions
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)
	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 $\vec{x} = \vec{f}+\frac12\vec{1} +\sum\limits_{i\in I}s_i\vec{r_i},$ where $\displaystyle\vec{x}\in\mathbb{Z}^m$ , $\displaystyle\vec{f}\in\left]-\frac12,\frac12\right[^m$ , $\displaystyle\vec{r_i}\in\mathbb{R}^m,\forall i\in I$ , $s\displaystyle _i\in\mathbb{R}_+,\forall i\in I$ ; and where $\displaystyle m=$ nrows and $\displaystyle \|I\|=$ ncols. The returned constraint is $\displaystyle \sum\limits_{i\in I}s_ib_i\geq 1$ where $\displaystyle b_i=$ cutval[i], $\displaystyle \forall i\in I$ . And where the set used to cut is $\displaystyle L=\left\{x:c\sigma x\leq c_o ,\forall\sigma\in\mathrm{diag}\left(\{-1,1\}^{m}\right)\right\}$ and $\displaystyle c=$ base, $\displaystyle c_o = \frac12\sum\limits_{i=1}^mc_i$ , where we assume that $c_i\neq 0\forall i=1,\ldots,m$ . Finally, note that $\displaystyle b_i=\max\limits_{\sigma:c\sigma r_i>0}\left\{\frac{c\sigma r_i}{c_o-c\sigma f}\right\}$ .