2 %> Algorithm 26.3: Gomory cuts
for linear optimization. Implementation of algorithm 26.3 of \cite Bier15-book
4 %> @note Tested with \ref run2604gomory.m
5 %> @note Tested with \ref run2513gomory.m
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 10:07:55 2015
10 %> @ingroup Algorithms
13 %> Solve an integer optimization problem by generating valid inequalities
using a Gomory cut:
14 %> \f[ \min_{x \in \mathbb{R}^n} c^T x
19 %> \f[ x \in \mathbb{N}^n \f]
20 %> where \f$A\in\mathbb{R}^{m\times n}\f$, \f$ b\in\mathbb{R}^m\f$ and
21 %> \f$c\in \mathbb{R}^n\f$.
22 %> @param A the constraint matrix
23 %> @param b the constraint right hand side
24 %> @param c the cost vector
for the objective
function 25 %> @
return xopt: an optimal solution
26 %> @
return iter: number of iterations
28 function [xopt, iter] =
gomory(A,b,c)
29 addpath(
"../chap16") ;
32 error(
"The number of rows in A and b do not match") ;
35 error(
"The number of columns in A and do not match the size of c") ;
41 % m and n are the dimension of the original problem
42 % mm and nn are the dimension of the current problem including the cuts
46 error(
"Unbounded problem detected\n") ;
48 % If some constraints have been detected to be redundant, the size may have changed
49 [tm,tn] = size(finaltableau) ;
52 lastcol = finaltableau(1:tm,tn+1) ;
53 fractional = find(min(ceil(lastcol)-lastcol,lastcol-floor(lastcol)) > sqrt(eps)) ;
54 if (isempty(fractional))
59 gamma = floor(finaltableau(i,1:tn)) ;
60 bplus = floor(finaltableau(i,tn+1)) ;
62 A = [ A zeros(mm,1) ; gamma 1] ;
function twoPhasesSimplex(in A, in b, in c)
Solve a linear optimization problem in standard form using the tableau simplex with two phases subje...
function gomory(in A, in b, in c)
Solve an integer optimization problem by generating valid inequalities using a Gomory cut: subject t...