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)
18 %> @return [tadj,tcost,tsupply] transformed adjacency matrix, transformed cost, transformed supply
19 function [tadj,tcost,tsupply] = transhipmentTransform(adj,cost,lb,ub,supply)
20  addpath("../chap21") ;
21 
22  nnodes = rows(adj) ;
23  narcs = max(max(adj)) ;
24  if (columns(adj) != nnodes)
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 
46  arcs = prepareNetwork(adj) ;
47 
48  tadj = zeros(narcs+nnodes,narcs+nnodes) ;
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 
65  tadj(nnodes+m,j) = m ;
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.
function prepareNetwork(in adj)
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...
Copyright 2015-2016 Michel Bierlaire