Ulrich Pferschy

Machine-learning-enhanced strategies to generate subtour elimination constraints for the symmetric traveling salesman problem

  • FB Akcay
  • Maxence Delorme
  • Ulrich Pferschy
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present a machine learning (ML) component designed to enhance the well-known branch-and-cut (B&C) framework for the symmetric traveling salesman problem (TSP) in which only the subtour elimination constraints (SECs) violated by previously found integer solutions are considered. The objective of the ML component is to identify which SECs, from a pool of candidates, will … Read more

    Optimization and Simulation for the Daily Operation of Renewable Energy Communities

  • Nathalie Frieß
  • Ulrich Pferschy
  • Joachim Schauer
  • Elias Feiner
  • Thomas Strametz
    • Categories Applications - Science and Engineering, Energy Tags , , ,

    Renewable Energy Communities (RECs) are an important building block for the decarbonization of the energy sector. The concept of RECs allows individual consumers to join together in local communities to generate, store, consume and sell renewable energy. A major benefit of this collective approach is a better match between supply and demand profiles, and thus, … Read more

    Planning a Zero-Emission Mixed-Fleet Public Bus System with Minimal Life Cycle Cost

  • Nathalie Frieß
  • Ulrich Pferschy
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , , ,

    The variety of available technology options for the operation of zero-emission bus systems gives rise to the problem of finding an optimal technology decision for bus operators. Among others, overnight charging, opportunity charging and hydrogen-based technology options are frequently pursued technological solutions. As their operating conditions are strongly influenced by the urban context, an optimal … Read more

    Integer Optimization with Penalized Fractional Values: The Knapsack Case

  • Enrico Malaguti
  • Michele Monaci
  • Ulrich Pferschy
  • Paolo Paronuzzi
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , ,

    We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of … Read more

    Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

  • Federico Della Croce
  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , ,

    We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more

    Improved dynamic programming and approximation results for the knapsack problem with setups

  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to … Read more

    Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem

  • Oswin Aichholzer
  • Anja Fischer
  • Frank Fischer
  • J. Fabian Meier
  • Ulrich Pferschy
  • Alexander Pilz
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more

    Approximation of Knapsack Problems with Conflict and Forcing Graphs

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories 0-1 Programming, Approximation Algorithms, Graphs and Matroids

    We study the classical 0-1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be … Read more

    On the shortest path game

  • Andreas Darmann
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Game Theory, Graphs and Matroids Tags , , ,

    In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (agents/players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in … Read more

    Generating subtour constraints for the TSP from pure integer solutions

  • Ulrich Pferschy
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and nonnegative real edge distances d, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is … Read more