Seminar 5th July 2010 3:30 p.m. University of Southampton Building 2 Room 3041
Decomposition and Reformulation Applied to a Temporal Extension of the Knapsack Problem
Fabio Furini
University of Bologna
- Web page
- http://www.cormsis.soton.ac.uk/seminars/default.php
- Categories
- Optimisation
- Submitter
- Petrina Butler
CORMSIS Seminar
Centre for Operational Research, Management Science and Information Systems
Abstract
The Resource Allocation Problem (RAP) is an NP-hard problem which introduces a temporal dimension in classical Knapsack Problems. RAP seeks the most pro?table subset of n given tasks which are not allowed to exceed the the amount of usable resource at any time. Each task has a pre-determined pro?t, a start and a ?nish time and a resource requirement. A classical Integer Linear Programming (ILP) formulation from the literature models the problem by associating a binary variable to each task, in order to de?ne which tasks are selected. We propose a pseudo-compact reformulation in order to strengthen this descriptive model. The reformulation imposes the limit of resource usage by introducing new binary variables, each variable being associated to a feasible subset of tasks which are simultaneously active. These variables, whose number is exponential with respect to the problem size, are e?ciently managed by means of a column generation approach. The generation of new variables derives from the solution of a series of knapsack problems. The continuous relaxation of this model is systematically stronger than the relaxation of the descriptive model. Finally, in order to obtain integer solutions, we embed our column generation procedures in a branching scheme, where we branch on the binary variables of the original formulation. We conclude by presenting computational results on a set of random instances.
Contact
Katarzyna (Kasia) Bijak
CORMSIS Facilitator
Centre for Operational Research, Management Science and Information Systems
School of Management/School of Mathematics
02380 598964