Optimization: principles and algorithms, by Michel Bierlaire
transhipmentTransform.m
Go to the documentation of this file.
1 %> \file
2 %> Transform a transhipment problem into a problem in standard form. Section 22.1 of \cite Bier15-book
3 %>
4 %> @note Calls \ref prepareNetwork
5 %> @note Called by \ref transhipment
6 %>
7 %> @author Michel Bierlaire
8 %> @date Sat Apr 11 11:48:27 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap22
11
12 %> Transform a transhipment problem with m nodes and n arcs into a problem in standard form
13 %> @param adj the adjacency matrix of the network (dim m x m)
14 %> @param cost the cost vector (dim n)
15 %> @param lb the vector of lower bounds (dim n)
16 %> @param ub the vector of upper bounds (dim n)
17 %> @param supply the vector of supply (dim m)
21
25  error("Adjacency matrix must be square") ;
26  endif
27  if (length(cost) != narcs)
28  error("cost vector has incorrect size") ;
29  endif
30  if (length(lb) != narcs)
31  error("lb vector has incorrect size") ;
32  endif
33
34  if (length(ub) != narcs)
35  error("ub vector has incorrect size") ;
36  endif
37
38  if (length(supply) != nnodes)
39  error("supply vector has incorrect size") ;
40  endif
41
42  if (sum(supply) != 0.0)
43  error("Infeasible supply/demand vector. Must sum up to 0") ;
44  endif
45
47
49  tsupply = [supply ; zeros(narcs,1)] ;
50  tcost = [cost ; zeros(narcs,1)] ;
51  for m=1:narcs
52  # transform first the lower bounds to
53  # zero using the change of variable
54  # where x is replaced by x - lb
55  ub(m) -= lb(m) ;
56  i = arcs(m,1) ;
57  j = arcs(m,2) ;
58  tsupply(i) -= lb(m) ;
59  tsupply(j) += lb(m) ;
60
61  # Insert the artificial nodes and
62  # artificial arcs for the slack
63  # variables.
64
66  tadj(nnodes+m,i) = narcs + m ;
67  tsupply(nnodes+m) = ub(m) ;
68  tsupply(i) -= ub(m) ;
69  endfor
70 endfunction
function transhipment(in adj, in cost, in lb, in ub, in supply, in useGlpk)
Solve the transhipment problem with bound constraints.
Identifies the upstream and downstream nodes of each arc.
function transhipmentTransform(in adj, in cost, in lb, in ub, in supply)
Transform a transhipment problem with m nodes and n arcs into a problem in standard form...