Optimization: principles and algorithms, by Michel Bierlaire
knapsackExact.m
Go to the documentation of this file.
1 %> \file
2 %> Solves the knapsack problem using integer optimization. See section 25.2.1 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2702.m
5 %>
6 %> @author Michel Bierlaire
7 %> @date Tue Apr 14 10:27:36 2015
8 %> @ingroup Algorithms
9 %> @ingroup chap25
10 
11 function xopt = knapsackExact(u,w,capacity)
12  [n,shouldBeOne] = size(u) ;
13  if (shouldBeOne != 1)
14  error("A column vector is expected for u") ;
15  endif
16  [nw,shouldBeOne] = size(w) ;
17  if (shouldBeOne != 1)
18  error("A column vector is expected for w") ;
19  endif
20  if (nw != n)
21  error("The two vectors must have the same size")
22  endif
23 
24  ctype = "U" ;
25  vtype = repmat('I',1,n) ;
26  lb = zeros(n,1) ;
27  ub = ones(n,1) ;
28  [xopt, fmin, errnum, extra] = glpk (-u, w', capacity, lb, ub, ctype, vtype) ;
29 endfunction
function knapsackExact(in u, in w, in capacity)
Copyright 2015-2016 Michel Bierlaire