Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme
Date
2007-03
Authors
Visagie, Stephan E.
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
In this dissertation original algorithms are introduced to solve separable resource allocation problems
(RAPs) with increasing nonlinear functions in the objective function, and lower and upper bounds on
each variable. Algorithms are introduced in three special cases. The first case arises when the objective
function of the RAP consists of the sum of convex functions and all the variables for these functions
range over the same interval. In the second case RAPs with the sum of convex functions in the objective
function are considered, but the variables of these functions can range over different intervals. In the
last special case RAPs with an objective function comprising the sum of convex and concave functions
are considered. In this case the intervals of the variables can range over different values.
In the first case two new algorithms, namely the fraction and the slope algorithm are presented to solve
the RAPs adhering to the conditions of the case. Both these algorithms yield far better solution times
than the existing branch and bound algorithm.
A new heuristic and three new algorithms are presented to solve RAPs falling into the second case. The
iso-bound heuristic yields, on average, good solutions relative to the optimal objective function value in
faster times than exact algorithms. The three algorithms, namely the iso-bound algorithm, the branch
and cut algorithm and the iso-bound branch and cut algorithm also yield considerably beter solution
times than the existing branch and bound algorithm. It is shown that, on average, the iso-bound branch
and cut algorithm yields the fastest solution times, followed by the iso-bound algorithm and then by die
branch and cut algorithm.
In the third case the necessary and sufficient conditions for optimality are considered. From this, the
conclusion is drawn that search techniques for points complying with the necessary conditions will take
too long relative to branch and bound techniques. Thus three new algorithms, namely the KL, SKL and
IKL algorithms are introduced to solve RAPs falling into this case. These algorithms are generalisations
of the branch and bound, branch and cut, and iso-bound algorithms respectively. The KL algorithm
was then used as a benchmark. Only the IKL algorithm yields a considerable improvement on the KL
algorithm.
Description
Thesis (PhD (Logistics))--University of Stellenbosch, 2007.
Keywords
Algoritme, Knapsack problem (Mathematics), Computer algorithms, Mathematical optimization, Convex programming, Dissertations -- Logistics, Theses -- Logistics