Marco E. Lübbecke
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:
Jacques Desrosiers
5 shared publications- Jacques Desrosiers
HEC Montréal and GERAD, Montréal, Canada H3T 2A7
5 shared publications - Jonas T. Witt
RWTH Aachen University
5 shared publications - Jean Bertrand Gauthier
HEC Montréal and GERAD, Montréal, Canada H3T 2A7
4 shared publications - Ambros Gleixner
Zuse Institute Berlin Takustr. 7 14195 Berlin Germany
3 shared publications - Christopher Hojny
Eindhoven University of Technology
3 shared publications
Latest Publications
- Open Access
- 25 July 2026
- Published by Elsevier in SSRN Electronic Journal
The Multi-Stop Station Location Problem: Exact Approaches
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.
- 25 July 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessThe Multi-Stop Station Location Problem: Exact Approaches
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
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 AccessBranch-and-price strikes back for the k-vertex cut problem
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
The SCIP Optimization Suite 10.0
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.
Open AccessThe SCIP Optimization Suite 10.0
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 PapersOpen Access
- 15 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (2) , 1-21
Enabling Research through the SCIP Optimization Suite 8.0
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 .
- 15 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (2) , 1-21
Top Cited PapersOpen AccessEnabling Research through the SCIP Optimization Suite 8.0
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 .
- 1 July 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (4) , 1849-1870
An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
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.
- 1 July 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 34 (4) , 1849-1870
An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
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 PapersOpen Access
- 7 January 2021
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 13 (3) , 443-490
MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
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.
- 7 January 2021
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 13 (3) , 443-490
Top Cited PapersOpen AccessMIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
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
- 5 February 2020
- Published by Springer Nature in Operations Research Forum
- Vol. 1 (1) , 1-3
Welcome to SN Operations Research Forum!
- 5 February 2020
- Published by Springer Nature in Operations Research Forum
- Vol. 1 (1) , 1-3
Open AccessWelcome to SN Operations Research Forum!
- 9 September 2019
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 12 (1) , 39-68
A branch-and-price algorithm for capacitated hypergraph vertex separation
- 9 September 2019
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 12 (1) , 39-68
A branch-and-price algorithm for capacitated hypergraph vertex separation
- 1 May 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 67 (3) , 791-812
Ship Traffic Optimization for the Kiel Canal
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.
- 1 May 2019
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 67 (3) , 791-812
Ship Traffic Optimization for the Kiel Canal
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.