Optimization: principles and algorithms, by Michel Bierlaire
transhipment.m
Go to the documentation of this file.
1 %> \file
2 %> Solve a transhipment problem with bound constraints
3 %>
4 %> @note Tested with runTransportationTrans.m
5 %> @note Tested with runMaxFlowTrans.m
6 %> @note Tested with runAssignmentTrans.m
7 %> @note Calls \ref transhipmentTransform
8 %> @note Calls \ref incidenceMatrix
9 %> @note Calls \ref twoPhasesSimplex
10 %>
11 %> @author Michel Bierlaire
12 %> @date Sat Apr 11 11:46:00 2015
13 %> @ingroup Algorithms
14 %> @ingroup chap22
15
16 %> Solve the transhipment problem with bound constraints
17 %> @param adj the adjacency matrix of the network (dim m x m)
18 %> @param cost the cost vector (dim n)
19 %> @param lb the vector of lower bounds (dim n)
20 %> @param ub the vector of upper bounds (dim n)
21 %> @param supply the vector of supply (dim m)
22 %> @param useGlpk if not 0, solve the linear problem using the glpk routine from Octave. (Default: 0)
23 %> @return cycle flow a simple cycle flow
29  error("Adjacency matrix must be square") ;
30  endif
31  if (length(cost) != narcs)
32  error("cost vector has incorrect size") ;
33  endif
34  if (length(lb) != narcs)
35  error("lb vector has incorrect size") ;
36  endif
37
38  if (length(ub) != narcs)
39  error("ub vector has incorrect size") ;
40  endif
41
42  for i=1:narcs
43  if lb(i) > ub(i)
44  error("Incompatible bounds") ;
45  endif
46  end
47  if (length(supply) != nnodes)
48  error("supply vector has incorrect size") ;
49  endif
50
51  if (sum(supply) != 0.0)
52  error("Infeasible supply/demand vector. Must sum up to 0") ;
53  endif
54
55  if (useGlpk != 0)
57  [nconstraints, nvariables] = size(incidenceMatrix) ;
58  ctype = repmat('S',1,nconstraints) ;
59  [x, copt, errnum, extra] = glpk(cost,incidenceMatrix,supply,lb,ub,ctype) ;
60  return ;
61  else
62
65  [xext,copt,opttable,feasible,bounded] = twoPhasesSimplex(incidenceMatrix,tsupply,tcost) ;
66  if (feasible == 0)
67  printf("Problem is infeasible\n") ;
68  return ;
69  endif
70  if (bounded == 0)
71  printf("Problem is unbounded\n") ;
72  return ;
73  endif
74  x = xext(1:narcs) ;
75  x += lb;
76  endif
77  endfunction
78
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 transhipment(in adj, in cost, in lb, in ub, in supply, in useGlpk)
Solve the transhipment problem with bound constraints.