Branch-and-refine for solving time-expanded MILP formulations

• Published in: Computers & operations research 2023-01, Vol.149, p.106043, Article 106043
• Main Authors: Gnegel, Fabian, Fügenschuh, Armin
• Format: Article
• Language: English
• Subjects: Branch-and-bound; Graph refinement; Shortest path problem with time windows; Traveling salesman problem with time windows
• ISSN: 0305-0548; 1873-765X
• DOI: 10.1016/j.cor.2022.106043

One of the standard approaches for solving discrete optimization problems which include the aspect of time, such as the traveling salesman problem with time windows or the shortest path problem with time windows is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is, that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion, that might contain time infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation is time feasible an optimal solution can be derived from it and the algorithm terminates. In this work we present new ideas, that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms, which are based on graph refinement. More precisely we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm we present numerical results on its application to the shortest path problem with time windows and the traveling salesman problem with time windows. •Introduces a general algebraic framework for refinement algorithms.•Provides proofs of convergence for these algorithms.•An application to the shortest path problem with time windows.•An application to the traveling salesman problem with time windows.