\'n Algoritme vir die minimum van die konkawe knapsakprobleem

Abstract

This paper addresses the problem of resource allocation among activities where the cost of each is described by a concave function. There is a single linear constraint (limited resource) and each activity has an upper and lower bound (maximum and minimum resource allocations). The objective is to minimise the sum of the functions. The problem with convex functions is well-studied and since a local minimum is also global, this problem was tamed early by Luss and Gupta [Luss H & Gupta SK, 1975, Allocation of effort resources among competing activities, Operations Research, 23, pp. 360–366], and by Bitran and Hax [Bitran GR & Hax AC, 1979, On the solution of convex knapsack problems with bounded variables, pp. 357–367 in Prékopa A (Ed.), Survey of Mathematical Programming]. In contrast the minimisation of a sum of concave functions has received less attention and then the emphasis has often been on an objective function which is nonseparable quadratic, and on the complexity of finding a true local minimiser (e.g. Moré and Vavasis [Moré JJ & Vavasis SS, 1991, On the solution of concave knapsack problems, Mathematical Programming, 49, pp. 397–411]). We are concerned with the computational problem of finding the global optimum for a (separable) sum of nondecreasing general concave functions and the approach is via the Kuhn- Tucker necessary conditions. These are improved by using the result that a minimiser must be an extreme point, which means that all but one variable (at most) is at an upper or lower bound. (Moré and Vavasis base their CKP algorithm on this property.) The improved necessary conditions form the basis of the method of greatest differences (GVA), our algorithm to improve a feasible solution. A greedy heuristic to produce a first feasible solution is also proposed. Using four groups of 10 instances, each from the four classes of concave functions of Luss and Gupta, one thousand different runs for incremental values of the resource were made for both the CKP and our GVA. While the CKP often found a globally suboptimal answer for functions which intersect, the GVA found the correct answer in all 16 000 runs. This is no guarantee that a method based on necessary conditions will always find the global maximum but the GVA is numerically promising and it masters a class of problems that the CKP does not. The greedy first feasible solution was found to be optimal more frequently (64% to 49%, and 73% to 40%) than that proposed by Moré and Vavasis. The GVA does not depend on the kind of function, requiring only that the functions be nondecreasing and concave. With minor alterations it can be used for the maximisation of the sum of nondecreasing convex functions. It is much faster than dynamic programming on problems with up to 10 functions and should be superior when tested on large problems.

Key words: Resource allocation problem, nonlinear knapsack problem, nonconvex optimisation.



Opsomming

Hierdie artikel beskrywe die hulpbrontoekenningsprobleem van aktiwiteite waar die koste van elkeen gegee word deur 'n konkawe funksie. Daar is 'n enkele line^ere beperking en elke aktiwiteit het 'n bo- en ondergrens. Die doelwit is die minimering van die som van die kostefunksies. Die probleem waar die doelfunksies konveks is, is baie goed bestudeer. In teenstelling hiermee het die minimering van die som van konkawe doelfunksies baie minder aandag in die literatuur gekry en die klem was dikwels op 'n doelfunksie wat nieskeibaar en kwadraties is, en op die kompleksiteit om die plaaslike minimum te verkry. Die enigste algoritme wat hierdie probleem oplos is die CVA-algoritme van Moré en Vavasis [Moré JJ & Vavasis SS, 1991, On the solution of concave knapsack problems, Mathematical Programming, 49, pp. 397–411]. Die probleem om die globale minimum vir 'n som van niedalende algemene konkawe funksies te verkry, word hier aangepak. Die benadering is via die Kuhn-Tucker nodige voorwaardes. Hierdie metode is verbeter deur die resultaat te gebruik dat by die algehele minimum hoogstens een funksie nie by sy onder- of bogrens is nie. Hierdie verbeterde nodige voorwaarde vorm die basis van die nuwe algoritme wat die uitvoerbare oplossing verbeter, naamlik die grootste verskille algoritme (GVA). Deur gebruik te maak van 10 voorkomste elk van die vier klasse van konkawe funksies van Luss en Gupta [Luss H & Gupta SK, 1975, Allocation of effort resources among competing activities, Operations Research, 23, pp. 360–366], is een duisend verskillende lopies met inkrementele waardes vir die hulpbron gedoen met die CKP en GVA algoritmes. Terwyl die CKP verskeie kere 'n globale suboptimale antwoord vir funksies wat mekaar sny gekry het, het die GVA die korrekte optimale antwoord in al 16 000 lopies verkry. Dit is egter nie 'n waarborg dat 'n metode wat gebaseer is op die nodige voorwaardes altyd die globale optimum sal verkry nie, maar die GVA is numeries baie belowend en dit spreek 'n klas van probleme aan wat die CKP metode nie doen nie. Die GVA is nie afhanklik van die tipe funksies nie — daar word net vereis dat die funksies niedalend en konkaaf moet wees. Met klein aanpassings kan die metode ook gebruik word vir die maksimering van die som van niedalende konvekse funksies.

Sleutelwoorde: Hulpbrontoekenningsprobleem, nieline^ere knapsakprobleem, niekonvekse optimering.

ORiON Vol.21(1) 2005: 13-31