Optimization guided lower and upper bounds for the resource investment problem

Andreas Drexl and Alf Kimms

No 481, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: The resource investment problem deals with the issue of providing resources to a project such that a given deadline can be met. The objective is to make the resources available in the cheapest possible way. For each resource, expenses depend on the maximum amount required during the course of the project. In this paper we develop two lower bounds for this NP-hard problem using Lagrangean relaxation and column generation techniques, respectively. Both procedures are capable of yielding feasible solutions as well. Hence, we also have two optimization guided heuristics. A computational study consisting of a set of 3210 instances compares both approaches and allows insight into the performance. E.g., for the instances from Möhring's test set it turns out that in 56% of the cases the heuristic solution derived on the basis of Lagrangean relaxation is optimal. Using column generation, the gap between the lower bound and the optimum objective function value is below 5% in 50% of the cases, it is below 10% in 71% of the cases, and it is below 20% in all cases.

Keywords: resource investment problem; Lagrangean relaxation; column generation; lower bounds; upper bounds (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147584/1/manuskript_481.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:cauman:481

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().