EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3448. On mines, flows and investments: a new algorithm for the precedence constrained continuous knapsack problem.

Invited abstract in session TA-52: Mixed Integer Optimization I, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Valerio Dose
Department of Computer, Control and Management Engineering, Sapienza University of Rome
2. Fabio Furini
DIAG, La Sapienza
3. Marco Locatelli
Department of Engineering and Architecture, University of Parma

Abstract

Imagine a student who must obtain a certain amount of credits to graduate and needs to choose which courses to take. Naturally, they would like some of them more than others, but it may be the case that to attend a course they are required to complete also some of the less preferred ones. Thus, what is the best plan to employ?

This is an example of a precedence constrained knapsack problem in combinatorial optimization. In this talk we will introduce some continuous relaxations of this problem which have applications in the mining industry, and can be suitably used to model other investment planning problems.

We will present a new algorithm to compute a solution, which is devised studying the behavior of the classical primal simplex algorithm when applied to the LP formulation. This reveals one of the very few examples of a simplex algorithm with an underlying combinatorial structure.

Keywords

Status: accepted

Back to the list of papers