Optimization: principles and algorithms, by Michel Bierlaire
gomory.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 26.3: Gomory cuts for linear optimization. Implementation of algorithm 26.3 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2604gomory.m
5 %> @note Tested with \ref run2513gomory.m
6 %> @note Calls \ref twoPhasesSimplex
7 %>
8 %> @author Michel Bierlaire
9 %> @date Tue Apr 14 10:07:55 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap26
12
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
15 %> \f]
16 %> subject to
17 %> \f[ Ax = b \f]
18 %> and
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
27
28 function [xopt, iter] = gomory(A,b,c)
30  [m,n] = size(A) ;
31  if (m != size(b))
32  error("The number of rows in A and b do not match") ;
33  endif
34  if (n != size(c))
35  error("The number of columns in A and do not match the size of c") ;
36  endif
37
38  iter = 0;
39  while (1)
40  iter = iter + 1 ;
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
43  [mm,nn] = size(A) ;
44  [x,copt,finaltableau,feasible,bounded] = twoPhasesSimplex(A,b,c) ;
45  if (bounded == 0)
46  error("Unbounded problem detected\n") ;
47  endif
48  % If some constraints have been detected to be redundant, the size may have changed
49  [tm,tn] = size(finaltableau) ;
50  tm -= 1 ;
51  tn -= 1 ;
52  lastcol = finaltableau(1:tm,tn+1) ;
53  fractional = find(min(ceil(lastcol)-lastcol,lastcol-floor(lastcol)) > sqrt(eps)) ;
54  if (isempty(fractional))
55  xopt = x(1:n) ;
56  return ;
57  endif
58  i = fractional(1) ;
59  gamma = floor(finaltableau(i,1:tn)) ;
60  bplus = floor(finaltableau(i,tn+1)) ;
61
62  A = [ A zeros(mm,1) ; gamma 1] ;
63  b = [ b ; bplus] ;
64  c = [ c ; 0] ;
65 endwhile
66
67
68 endfunction
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...