• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation

Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016), Solving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulation, Information Processing Letters, 116, 5, p. 379-386. 10.1016/j.ipl.2016.01.008

Type
Article accepté pour publication ou publié
Date
2016
Journal name
Information Processing Letters
Volume
116
Number
5
Publisher
Elsevier
Pages
379-386
Publication identifier
10.1016/j.ipl.2016.01.008
Metadata
Show full item record
Author(s)
Caprara, Alberto
D.E.I. - University of Bologna.
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Malaguti, Enrico
D.E.I. - University of Bologna.
Traversi, Emiliano
Laboratoire d'Informatique de Paris-Nord [LIPN]
Abstract (EN)
The Temporal Knapsack Problem (TKP) is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. In this paper we solve the TKP using what we call a Recursive Dantzig–Wolfe Reformulation (DWR) method. The generic idea of Recursive DWR is to solve a Mixed Integer Program (MIP) by recursively applying DWR, i.e., by using DWR not only for solving the original MIP but also for recursively solving the pricing sub-problems. In a binary case (like the TKP), the Recursive DWR method can be performed in such a way that the only two components needed during the optimization are a Linear Programming solver and an algorithm for solving Knapsack Problems. The Recursive DWR allows us to solve Temporal Knapsack Problem instances through computation of strong dual bounds, which could not be obtained by exploiting the best-known previous approach based on DWR.
Subjects / Keywords
Combinatorial Problems; Temporal Knapsack Problem; Dantzig–Wolfe Reformulation; Mixed integer programs

Related items

Showing items related by title and author.

  • Thumbnail
    Automatic Dantzig–Wolfe reformulation of mixed integer programs 
    Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the Product Knapsack Problem 
    D’Ambrosio, Claudia; Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • Thumbnail
    Exact approaches for the knapsack problem with setups 
    Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018) Article accepté pour publication ou publié
  • Thumbnail
    A hybrid heuristic for the multi-activity tour scheduling problem 
    Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié
  • Thumbnail
    An exact algorithm for the Partition Coloring Problem 
    Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo