Valentina Cacchiani

A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph

  • Andrea Bettinelli
  • Valentina Cacchiani
  • Enrico Malaguti
    • Categories Combinatorial Optimization Tags , , , ,

    We study the Knapsack Problem with Conflict Graph (KPCG), an extension of the 0-1 Knapsack Problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new Branch-and-Bound approach to … Read more

    Single-Commodity Robust Network Design with Finite and Hose Demand Sets

  • Valentina Cacchiani
  • Frauke Liers
  • Andrea Lodi
  • Michael Juenger
  • Daniel Schmidt
    • Categories Branch and Cut Algorithms, Network Optimization, Robust Optimization Tags , , ,

    We study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of … Read more

    Approaches to a real-world train timetabling problem in a railway node

  • Valentina Cacchiani
  • Fabio Furini
  • Martin Philip Kidd
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , ,

    We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a … Read more