CLAUTIAUX, François; DETIENNE, Boris; GUILLOT, Gaël

doi:10.1016/j.ejor.2020.12.036

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

CLAUTIAUX, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]

DETIENNE, Boris
Reformulations based algorithms for Combinatorial Optimization [Realopt]

GUILLOT, Gaël
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Idioma

Article de revue

Este ítem está publicado en

European Journal of Operational Research. 2021-09-01, vol. 293, n° 2

Elsevier

Resumen en inglés

In this paper, we address the temporal knapsack problem (TKP). In this generalization of the classical knapsack problem, selected items enter and leave the knapsack at fixed dates. We solve the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature.< Leer menos

Palabras clave en inglés

Temporal knapsack

Exact algorithm

Lagrangian Relaxation

Successive Sublimation Dynamic Programming method

Metadatos

Compartir este ítem

Licencia de uso del documento

An iterative dynamic programming approach for the temporal knapsack problem

Idioma

Este ítem está publicado en

Resumen en inglés

Palabras clave en inglés

URI

DOI

Orígen

Centros de investigación