Optimization: principles and algorithms, by Michel Bierlaire
Functions
gomory.m File Reference

Algorithm 26.3: Gomory cuts for linear optimization. More...

Go to the source code of this file.

Functions

function gomory (in A, in b, in c)
 Solve an integer optimization problem by generating valid inequalities using a Gomory cut:

\[ \min_{x \in \mathbb{R}^n} c^T x \]

subject to

\[ Ax = b \]

and

\[ x \in \mathbb{N}^n \]

where $A\in\mathbb{R}^{m\times n}$, $ b\in\mathbb{R}^m$ and $c\in \mathbb{R}^n$. More...

 

Detailed Description

Algorithm 26.3: Gomory cuts for linear optimization.

Implementation of algorithm 26.3 of [1]

Note
Tested with run2604gomory.m
Tested with run2513gomory.m
Calls twoPhasesSimplex
Author
Michel Bierlaire
Date
Tue Apr 14 10:07:55 2015

Definition in file gomory.m.

Function Documentation

function gomory ( in  A,
in  b,
in  c 
)

Solve an integer optimization problem by generating valid inequalities using a Gomory cut:

\[ \min_{x \in \mathbb{R}^n} c^T x \]

subject to

\[ Ax = b \]

and

\[ x \in \mathbb{N}^n \]

where $A\in\mathbb{R}^{m\times n}$, $ b\in\mathbb{R}^m$ and $c\in \mathbb{R}^n$.

Parameters
Athe constraint matrix
bthe constraint right hand side
cthe cost vector for the objective function
Returns
xopt: an optimal solution
iter: number of iterations
Copyright 2015-2016 Michel Bierlaire