Sophia Wrede

A Combinatorial Branch-and-Bound Algorithm for the Capacitated Facility Location Problem under Strict Customer Preferences

  • Christina Büsing
  • Felix Engelhardt
  • Sophia Wrede
    • Categories Bilevel Optimization, Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    This work proposes a combinatorial branch-and-bound (B&B) algorithm for the capacitated facility location problem under strict customer preferences (CFLP-SCP). We use combinatorial insights into the problem structure to do preprocessing, model branching implications, enforce feasibility or prove infeasibility in each node, select variables and derive primal and dual bounds in each node of the B&B … Read more

    Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Timo Gersing
  • Sophia Wrede
    • Categories Combinatorial Optimization Tags , , ,

    Single-source capacitated facility location problems are well studied in the operations research literature, yet classic problems often lack practicability by disregarding the customers’ perspective: An authority that assigns customers to open facilities deprives customers from choosing facilities according to their individual preferences. In reality, this can render solutions infeasible, as customers may deviate to their … Read more

    Minimum-Peak-Cost Flows Over Time

  • Mariia Anapolska
  • Christina Büsing
  • Felix Engelhardt
  • Timo Gersing
  • Sabrina Schmitz
  • Sophia Wrede
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    Peak cost is a novel objective for flows over time that describes the amount of workforce necessary to run a system. We focus on minimising peak costs in the context of maximum temporally repeated flows and formulate the corresponding MPC-MTRF problem. First, we discuss the limitations that emerge when restricting the solution space to integral … Read more

    Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the … Read more