Stephen J. Maher – Optimization Online

Computational evaluation of cut-strengthening techniques in logic-based Benders’ decomposition

Published: 2023/02/26

Applications - OR and Management Sciences, Combinatorial Optimization, Scheduling benders' cuts, cut strengthening, Feasibility cuts, Irreducible cuts, logic-based benders decomposition, Optimality cuts

Cut-strengthening techniques have a significant impact on the computational effectiveness of the Logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific and thus, no … Read more

Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

Published: 2022/03/07, Updated: 2022/07/07

Stephen J. Maher

Elina Rönnberg

(Mixed) Integer Linear Programming branch-and-price, column generation, large-neighbourhood search, matheuristic

Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more

The SCIP Optimization Suite 8.0

Published: 2021/12/16, Updated: 2022/01/31

Jasper van Doornmalen

Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … Read more

An Overview of Nested Decomposition for Multi-Level Optimization Problems

Published: 2021/10/21

Stephen J. Maher

Ibrahim Muter

Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming branch-and-price, column generation, integer programming, multi-level decomposition, two-level decomposition

Nested multi-level structures are frequently encountered in many real-world optimization problems. Decomposition techniques are a commonly applied approach used to handle nested multi-level structures; however, the typical problem-specific focus of such techniques has led to numerous specialized formulations and solution methods. This lack of generalized results for nested multi-level optimization problems is addressed in this … Read more

A data-driven, variable-speed model for the train timetable rescheduling problem

Published: 2021/01/25

Stephen J. Maher

Edwin Reynolds

Transportation railway optimisation, speed profile, timetable rescheduling, variable-speed

Train timetable rescheduling — the practice of changing the routes and timings of trains in real-time to respond to delays — can help to reduce the impact of reactionary delay. There are a number of existing optimisation models that can be used to determine the best way to reschedule the timetable in any given traffic … Read more

A multicommodity flow model for rerouting and retiming trains in real-time to reduce reactionary delay in complex station areas

Published: 2020/05/29

Transportation branch-and-price, multicommodity flow, railway optimization, timetable rescheduling

By rerouting and retiming trains in real-time, the propagation of reactionary delay in complex station areas can be reduced. In this study, we propose a new optimisation model and solution algorithm that can be used to determine the best combination of route and schedule changes to make. Whilst several models have been proposed to tackle … Read more

The SCIP Optimization Suite 7.0

Published: 2020/03/30

Matthias Miltenberger

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming benders decomposition, branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization, presolving, steiner tree optimization, tree size estimation

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

Published: 2019/09/25

Stephen J. Maher

Ted K. Ralphs

Yuji Shinano

(Mixed) Integer Linear Programming, Integer Programming, Parallel Algorithms algorithm assessment, benchmarking, Branch-and-Bound, effectiveness, efficiency, performance, scalability

Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous … Read more

Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework

Published: 2019/09/24, Updated: 2019/09/25

Stephen J. Maher

Integer Programming, Optimization Software and Modeling Systems benders decomposition, branch-and-cut, constraint integer programming, mixed-integer programming, optimisation software

Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as … Read more

Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

Published: 2019/02/28

Marco E. Lübbecke

Stephen J. Maher

Jonas T. Witt

(Mixed) Integer Linear Programming benders decomposition, column generation, dantzig-wolfe reformulation, domain reduction

When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are … Read more