MLMarco E. Lübbecke

Marco E. Lübbecke

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Marco E. Lübbecke has a total of 143 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The Multi-Stop Station Location Problem: Exact Approaches

    by Erik Mühmer, Miriam Ganz, Marco E. Lübbecke, Felix J. L. Willamowski

    The multi-stop station location problem (MSLP) is motivated by infrastructure planning for range-limited transportation services such as electric intercity buses. We study this foundational infrastructure-siting and routing problem in which a fixed set of ordered trips must be made feasible under vehicle-range limits by installing shared stations and, if necessary, allowing detours between consecutive planned stops. We present an arc-based mixed-integer linear program (MILP) and two pattern-based reformulations, one based on complete trip paths and one based on trip segment paths. The latter yields shortest path pricing problems, and both are combined in a nested approach. For the pattern-based reformulations, we develop branch-price-and-cut algorithms with a problem-specific primal heuristic, branching strategies, and, for the segment-based formulation, additional cutting planes. On synthetic benchmarks derived from TSPLIB, the pattern-based approaches are more scalable than the compact MILP, and the nested approach performs best overall, solving 82.4% of all instances to optimality within the time limit. On a GTFS-based intercity bus instance with 1644 nodes and 2408 trips, the nested approach proves optimality in 40.06 hours. These results show that exact methods can solve the MSLP beyond toy instances on public-data transportation networks.

  • Open Access

    Branch-and-price strikes back for the k-vertex cut problem

    by Fabio Ciccarelli, Fabio Furini, Christopher Hojny, Marco Lübbecke

    Given an undirected graph, the k-vertex cut problem (k-VCP) asks for a minimum-cost set of vertices whose removal yields at least k connected components in the resulting graph. The k-VCP is an important problem in network optimization, with applications in infrastructure protection and epidemic containment. We present a new extended integer linear programming (ILP) formulation that unifies and strengthens existing models and serves as the foundation for a new branch-and-price algorithm for the k-VCP. An in-depth theoretical study enables us to devise algorithmic components such as tailored branching rules that preserve the structure of the pricing problems, as well as valid inequalities and symmetry-handling techniques. We also show that our new model dominates all previous ILP formulations of the k-VCP in terms of their linear relaxations, which theoretically justifies the computational effectiveness of our approach. Extensive computational experiments against state-of-the-art methods demonstrate substantially improved performance, both in terms of instances solved to proven optimality and running times. On the full benchmark of 608 instances, our algorithm consistently outperforms all competitors and is able to solve 73 previously unsolved instances within the time limit of one hour.

  • Open Access

    Branch-and-Price

    by Jacques Desrosiers, Marco Lübbecke, Guy Desaulniers, Jean Bertrand Gauthier


  • Open Access

    The SCIP Optimization Suite 10.0

    by Christopher Hojny, Mathieu Besançon, Ksenia Bestuzheva, Sander Borst, João Dionísio, Johannes Ehls, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Adrian Göß, et al.

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in SCIP Optimization Suite 10.0. The updates in SCIP 10.0 include a new solving mode for exactly solving rational mixed-integer linear programs, a new presolver for detecting implied integral variables, a novel cut-based conflict analysis and separator for flower inequalities, two new heuristics, a novel tool for explaining infeasibility, a new interface for nonlinear solvers as well as improvements in symmetry handling, branching strategies, and SCIP's Benders' decomposition framework. SCIP Optimization Suite 10.0 also includes new and improved features in the the presolving library PaPILO, the parallel framework UG, and the decomposition framework GCG. Moreover, the SCIP Optimization Suite 10.0 contains MIP-DD, the first open-source delta debugger for mixed-integer programming solvers. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.


  • Top Cited Papers
    Open Access

    Enabling Research through the SCIP Optimization Suite 8.0

    by Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al.

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP . The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP ’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP ’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP .


  • An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs

    by Zachary Steever, Chase Murray, Junsong Yuan, Mark Karwan, Marco Lübbecke

    Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are used to detect latent structural features therein. The resulting feature vectors are used to measure similarity between images and, consequently, MIPs. An introductory analysis examines a subset of the instances from strIPlib and MIPLIB 2017, two online repositories for MIP instances. Results indicate that structure-based comparisons may allow for relationships to be identified between MIPs from disparate application areas. Additionally, image-based comparisons reveal that ostensibly similar variations of an MIP model may yield instances with markedly different mathematical structures.Summary of Contribution: This paper presents a methodology for comparing mixed integer programs (MIPs) from any research domain based on the structure of the constraint coefficient matrices for one or more instances of a model. Specifically, computer vision and deep learning techniques are used to extract structural features and measure the similarity between these images. This process is agnostic to application area and instead focuses solely on mathematical structure. As a result, this methodology offers a fundamentally new way for operations researchers to view MIP similarity and highlights similarities between research problems that may have previously been viewed as unrelated.


  • Top Cited Papers
    Open Access

    MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library

    by Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al.

    We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.


  • Open Access

    Welcome to SN Operations Research Forum!

    by Marco Lübbecke, Panos M. Pardalos


  • Ship Traffic Optimization for the Kiel Canal

    by Elisabeth Lübbecke, Marco E. Lübbecke, Rolf H. Möhring

    In “Ship Traffic Optimization for the Kiel Canal,” Lübbecke, Lübbecke, and Möhring develop graph-based models and algorithms to solve a practical traffic scheduling problem. It arises in the operational planning of bidirectional traffic where vehicles can pass each other only at dedicated locations—e.g., vessels that navigate narrow waterways. The authors provide decision support for the particular planning problem at the German Kiel Canal, the world’s most frequented artificial waterway, but their findings generalize, e.g., to scheduling trains on a stretch of single tracks or collision-free routing of robot arms. Mathematically, these planning problems expose a rich combinatorial structure. Ideas from quickest path algorithms and job-shop scheduling are integrated to handle all practical constraints at a high level of detail. The modelling does not need any time or space discretization. The software tool developed during the study was also used to assess strategic options of enlarging the canal.