Optimization: principles and algorithms, by Michel Bierlaire
vertexEnumeration.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 16.1: Vertex enumeration Implementation of algorithm 16.1 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run1604.m
5 %> @note Tested with \ref runBoundConstraints.m
6 %>
7 %> @author Michel Bierlaire
8 %> @date Sun Mar 22 10:53:32 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap16
11
12 %> Applies the vertex enumeration algorithm to solve \f$\min_x c^Tx\f$ subject to \f$Ax=b\f$ and \f$x \geq 0\f$ , where \f$A \in \mathbb{R}^{m\times n}\f$, \f$b \in \mathbb{R}^m\f$, and \f$c \in \mathbb{R}^n\f$.
13 %> @param A the constraint matrix
14 %> @param b the constraint right hand side
15 %> @param c the cost vector for the objective function
16 %> @return [solution,optvalue]
17 %> @return solution: an optimal solution
18 %> @return optvalue: the value of the objective function at the optimal solution
19 function [solution,optvalue] = vertexEnumeration(A,b,c)
20  [m,n] = size(A) ;
21
22  if (m != size(b))
23  error("The number of rows in A and b do not match") ;
24  endif
25  if (n != size(c))
26  error("The number of columns in A and do not match the size of c") ;
27  endif
28  optvalue = realmax ;
29
30  enumerate = nchoosek(1:n,m) ;
31  for i = enumerate'
32  B = A(:,i) ;
33  [x, R] = linsolve(B,b) ;
34  if (R > 0)
35  xfull = zeros(n,1) ;
36  xfull(i) = x ;
37  printf("%e\t",xfull) ;
38  if (all(x >= 0))
39  f = c(i)' * x ;
40  printf("%e\n",f) ;
41  if (f < optvalue)
42  solution = xfull ;
43  optvalue = f ;
44  endif
45  else
46  printf("Infeasible\n") ;
47  endif
48  endif
49  endfor
50 endfunction
function vertexEnumeration(in A, in b, in c)
Applies the vertex enumeration algorithm to solve subject to and , where , , and ...