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
24 function [x,copt] = transhipment(adj,cost,lb,ub,supply,useGlpk=0)
25  addpath("../chap16") ;
26  nnodes = rows(adj) ;
27  narcs = max(max(adj)) ;
28  if (columns(adj) != nnodes)
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 
63  [tadj,tcost,tsupply] = transhipmentTransform(adj,cost,lb,ub,supply) ;
64  incidenceMatrix = incidenceMatrix(tadj);
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.
function incidenceMatrix(in adj)
Provide the incidence matrix a a network.
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