Titulo Estágio
A branch-and-bound for the cardinality constrained rectangular knapsack problem
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS/DEI
Enquadramento
For quadratic knapsack problems (QKP), in contrast to classical knapsack problems, the profit of a selection of objects is not only determined by the individual profits, but also by profits generated by pairwise combinations of objects. This can be used to model the fact that two objects may complement one another such that their profit is increased if both of them are selected.
The cardinality constrained rectangular knapsack problem (CCRKP) [1] is a particular case of the QKP, where the profit matrix is built by the matrix multiplication of two vectors, given a constraint on the number of objects to choose. The name "rectangular knapsack problem" is motivated by the special structure of the profit matrix, since every coefficient can be interpreted as the area of a rectangle. This optimization problem arises in the computation of optimal solutions to multi-objective optimization problems by maximizing the corresponding hypervolume indicator.
The CCRKP is NP-hard and only an approximation algorithm with constant factor is reported in the literature for the particular case of having only positive coefficients [1]. No exact algorithms are known for this problem. Algorithmic advances to this problem are particularly relevant and have potential strong impact in the optimization community since they would provide more insight into innovative solution approaches for multiobjective optimization problems.
Objetivo
The goal of this thesis is to develop branch-and-bound procedures to solve the CCRKP to optimality. Efficient upper and lower bound procedures are already reported in Schulze [1]. Other bounds should be considered within this problem, e.g., based on the linear programming relaxation of the CCRKP, as well as other branching strategies and variable orderings.
The student should experimentally evaluate their performance on a wide range of instances. The code should be integrated with a known linear programming solver, such as SCIP or GLPK, to derive bounds based on linear programming. Other problem variants should be considered if time allows.
Plano de Trabalhos - Semestre 1
- Literature review: Notions of combinatorial optimization, branch-and-bound, quadratic knapsack problems, CCRKP
- Development of upper and lower bounds procedures for the CCRKP
- Preliminary experimental evaluation
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Development of a branch-and-bound for the CCRKP
- Integration with linear programming solver
- Experimental evaluation
- Study of particular variants
- Writing of the final report
Condições
This MSc project is for students that would like to deepen his knowledge on algorithms and combinatorial optimization. Good marks on programming and mathematical/optimization courses is a requirement. The MSc student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
This project is co-supervised by Dr. Britta Schulze, from the Working Group Optimization and Approximation, School of Mathematics and Natural Sciences, University of Wuppertal. This project arises as a task on the FCT/DAAD bilateral research collaboration project "Multi-Objective Network Optimization for Engineering and Management Support". Within the scope of this project, it might be possible to fund a short visit to the University of Wuppertal.
References
[1] B. Schulze, New Perspectives on Multi-objective Knapsack Problems, PhD thesis, University of Wuppertal, 2017.
[2] D. Pisinger. The quadratic knapsack problem - a survey. Discrete Applied Mathematics, 155(5):623-648, 2007
Orientador
Luís Paquete
paquete@dei.uc.pt 📩